Asp Forum - sampling using iterators

Leon

10/29/2008 6:29:00 PM

using
multimap<int,int>::iterator itlow = pq.lower_bound (x);
multimap<int,int>::iterator itup = pq.upper_bound (y);

I obtain lower and upper bound from the multimap, and having these two
iterators I would like to sample one element with uniform distribution.
It a way do to this using iterators? I can of course draw an integer and
loop over the sequence until I meet the drawn value, but it is not a
very nice solution. Can sample directly using iterators?

thanks

8 Answers

Victor Bazarov

10/29/2008 6:47:00 PM

Juha Nieminen

10/29/2008 11:13:00 PM

Leon wrote:
> using
> multimap<int,int>::iterator itlow = pq.lower_bound (x);
> multimap<int,int>::iterator itup = pq.upper_bound (y);
>
> I obtain lower and upper bound from the multimap, and having these two
> iterators I would like to sample one element with uniform distribution.
> It a way do to this using iterators? I can of course draw an integer and
> loop over the sequence until I meet the drawn value, but it is not a
> very nice solution. Can sample directly using iterators?

I don't really understand what do you mean by "sample". If you mean
that you want (constant-time) random access to the range above, that's
just not possible with multimap iterators, as they are not random access
iterators.

If you *really* need that (eg. for efficiency reasons) then one
solution might be to instead of using a multimap, use a regular map with
a vector (or deque) as element, so that each element with the same key
is put into the vector correspondent to that key. Then you can
random-access the vector when you need to.

(Of course the downside of this is that inserting and removing
elements is not, strictly speaking, O(lg n) anymore... But you can't
have everything at once.)

Leon

10/30/2008 2:26:00 AM

Juha Nieminen wrote:
> Leon wrote:
>> using
>> multimap<int,int>::iterator itlow = pq.lower_bound (x);
>> multimap<int,int>::iterator itup = pq.upper_bound (y);
>>
>> I obtain lower and upper bound from the multimap, and having these two
>> iterators I would like to sample one element with uniform distribution.
>> It a way do to this using iterators? I can of course draw an integer and
>> loop over the sequence until I meet the drawn value, but it is not a
>> very nice solution. Can sample directly using iterators?
>
> I don't really understand what do you mean by "sample". If you mean
> that you want (constant-time) random access to the range above, that's
> just not possible with multimap iterators, as they are not random access
> iterators.
>
> If you *really* need that (eg. for efficiency reasons) then one
> solution might be to instead of using a multimap, use a regular map with
> a vector (or deque) as element, so that each element with the same key
> is put into the vector correspondent to that key. Then you can
> random-access the vector when you need to.
>
> (Of course the downside of this is that inserting and removing
> elements is not, strictly speaking, O(lg n) anymore... But you can't
> have everything at once.)

Yes, since the iterator is not random for multimap I have to loop
anyway. Thanks!

Andrew Koenig

11/13/2008 9:54:00 PM

"Leon" <lew71@poczta.onet.pl> wrote in message
news:geaa1v$8fm$2@news.onet.pl...

> using
> multimap<int,int>::iterator itlow = pq.lower_bound (x);
> multimap<int,int>::iterator itup = pq.upper_bound (y);
>
> I obtain lower and upper bound from the multimap, and having these two
> iterators I would like to sample one element with uniform distribution. It
> a way do to this using iterators?

Assume you have a function nrand that takes an integer n and returns a
uniform random integer k such that 0 <= k < n.

Then I think this code will do what you want:

assert (itlow != itup); // necessary for a result to be possible

multimap<int,int>::iterator result;
int n = 0;
while (itlow != itup) {
if (nrand(++n) == 0)
result = itlow;
++itlow;
}

Note that the first call to nrand will be nrand(++n) with n initially 0,
which is effectively nrand(1). By definition, nrand(1) is always 0, so
result will always be initialized the first time through the loop.
Moreover, the loop will always execute at least once because of the assert.
Therefore, there is no risk that result might not be initialized.

James Kanze

11/14/2008 8:35:00 AM

On Oct 30, 12:13 am, Juha Nieminen <nos...@thanks.invalid> wrote:
> Leon wrote:
> > using
> > multimap<int,int>::iterator itlow = pq.lower_bound (x);
> > multimap<int,int>::iterator itup = pq.upper_bound (y);

> > I obtain lower and upper bound from the multimap, and having
> > these two iterators I would like to sample one element with
> > uniform distribution. It a way do to this using iterators?
> > I can of course draw an integer and loop over the sequence
> > until I meet the drawn value, but it is not a very nice
> > solution. Can sample directly using iterators?

> I don't really understand what do you mean by "sample". If you
> mean that you want (constant-time) random access to the range
> above, that's just not possible with multimap iterators, as
> they are not random access iterators.

> If you *really* need that (eg. for efficiency reasons) then
> one solution might be to instead of using a multimap, use a
> regular map with a vector (or deque) as element, so that each
> element with the same key is put into the vector correspondent
> to that key. Then you can random-access the vector when you
> need to.

He seems to be looking for a range (lower_bound and upper_bound
are called with different arguments), not just a single key.
But using a sorted vector, with the library functions
lower_bound and upper_bound, would definitely be a possible
solution. As you say, insertion would be more expensive, but a
lot depends on the other use he makes of the structure, and how
expensive copying or swapping the elements might be. (Using
lower_bound on a sorted vector is actually significantly faster
than map.lower_bound, at least with the implementations I've
tested.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

SFD

4/14/2011 9:31:00 PM

"His Highness the TibetanMonkey, the Beach Cruiser Philosopher"
<nolionnoproblem@yahoo.com> wrote in message
news:92f62f94-e391-44e5-b631-0d617e87cd80@x8g2000prh.googlegroups.com...
On Apr 14, 2:14 am, "SFD" <s...@127000.00> wrote:
> "His Highness the TibetanMonkey, the Beach Cruiser
> Philosopher"<comandante.ban...@yahoo.com> wrote in message
>
> news:acca4b01-80b7-48ae-a501-d11b6ba7f4f3@t16g2000vbi.googlegroups.com...
>
>
>
> > Very hard question for a Christian:
>
> > According to my philosophy, you must have a Beach Cruiser --flip-flops
> > and little else-- to enjoy the beach, and thus be a able to say
> > "Life's a Beach." I have a problem though:
>
> > MY PARK HAS MORE BUMS THAN BEACH BUMS...
>
> > which lowers the prestige for all, if you know what I mean. Well, it
> > also keeps the ladies away and that's very bad for a beach bum.
> > Actually it works as a DE FACTO Taliban restriction on women who are
> > afraid to come out.
>
> > If you are a Christian though you like to feed the bums at the nearby
> > church, and then say "Life's a Bitch." And I say, "Of course, it's a
> > bitch. You feed the problem!"
>
> > When you get up in the morning --says my wisdom-- you make it a beach
> > or a bitch, but you must avoid bums to keep the depression away. I
> > won't say, "AVOID CHRISTIANS," because that's just impossible.
>
> > I leave you know with perhaps the greatest of Beach Bum singers:
>
> >http://www.youtube.com/watch?v=C...
>
> > ------------------------------------------------------------------
>
> >http://webspawner.com/users/BANANA...
>
> It would appear that they have take-aways in heaven.
> The question is then, was Jesus a McDonalds fan?
> Did he survive only on Big Macs?
> Was he over weight?
> Did he not eat fruit and vegetables?
> According to the gospel he was a cheeseburger fan,
> as is proven on this
> link.http://www.youtube.com/watch?v=jBsPZV14I-k&feat...

>Jesus was a bum, but not a regular bum. He was something like a
>Christian bum --the first one in its kind.

>I'm not sure he lived on peanuts or banana because he only have to
>think of a dish for it appear in his plate. Was he a vegetarian? I
>think he would dismiss the burger and eat the cheese with the buns.

>If he had been alive today he would probably be a beach bum and go to
>the nudist beach. He'd be shy though, not like those hung guys walking
>up and down the beach. In other words, he would be hardly noticeable.

>One enduring question is WOULD HE WEAR UNDERWEAR?

.... he wouldn't have to - he could just imagine it.

The reason he had this wonderful "blessed" imagination is because he smoked
pot.

His Highness the TibetanMonkey, aka Comandante Banana

4/15/2011 2:10:00 AM

On Apr 14, 5:31 pm, "SFD" <s...@127000.00> wrote:
> "His Highness the TibetanMonkey, the Beach Cruiser Philosopher"<nolionnoprob...@yahoo.com> wrote in message
>
> news:92f62f94-e391-44e5-b631-0d617e87cd80@x8g2000prh.googlegroups.com...
> On Apr 14, 2:14 am, "SFD" <s...@127000.00> wrote:
>
>
>
> > "His Highness the TibetanMonkey, the Beach Cruiser
> > Philosopher"<comandante.ban...@yahoo.com> wrote in message
>
> >news:acca4b01-80b7-48ae-a501-d11b6ba7f4f3@t16g2000vbi.googlegroups.com...
>
> > > Very hard question for a Christian:
>
> > > According to my philosophy, you must have a Beach Cruiser --flip-flops
> > > and little else-- to enjoy the beach, and thus be a able to say
> > > "Life's a Beach." I have a problem though:
>
> > > MY PARK HAS MORE BUMS THAN BEACH BUMS...
>
> > > which lowers the prestige for all, if you know what I mean. Well, it
> > > also keeps the ladies away and that's very bad for a beach bum.
> > > Actually it works as a DE FACTO Taliban restriction on women who are
> > > afraid to come out.
>
> > > If you are a Christian though you like to feed the bums at the nearby
> > > church, and then say "Life's a Bitch." And I say, "Of course, it's a
> > > bitch. You feed the problem!"
>
> > > When you get up in the morning --says my wisdom-- you make it a beach
> > > or a bitch, but you must avoid bums to keep the depression away. I
> > > won't say, "AVOID CHRISTIANS," because that's just impossible.
>
> > > I leave you know with perhaps the greatest of Beach Bum singers:
>
> > >http://www.youtube.com/watch?v=C...
>
> > > ------------------------------------------------------------------
>
> > >http://webspawner.com/users/BANANA...
>
> > It would appear that they have take-aways in heaven.
> > The question is then, was Jesus a McDonalds fan?
> > Did he survive only on Big Macs?
> > Was he over weight?
> > Did he not eat fruit and vegetables?
> > According to the gospel he was a cheeseburger fan,
> > as is proven on this
> > link.http://www.youtube.com/watch?v=jBsPZV14I-k&feat...
> >Jesus was a bum, but not a regular bum. He was something like a
> >Christian bum --the first one in its kind.
> >I'm not sure he lived on peanuts or banana because he only have to
> >think of a dish for it appear in his plate. Was he a vegetarian? I
> >think he would dismiss the burger and eat the cheese with the buns.
> >If he had been alive today he would probably be a beach bum and go to
> >the nudist beach. He'd be shy though, not like those hung guys walking
> >up and down the beach. In other words, he would be hardly noticeable.
> >One enduring question is WOULD HE WEAR UNDERWEAR?
>
> ... he wouldn't have to - he could just imagine it.
>
> The reason he had this wonderful "blessed" imagination is because he smoked
> pot.

Or banana peels.

I just wonder why Christians make so much fuss about it.

I bet you the Tree of Knowledge was marijuana.

His Highness the TibetanMonkey, aka Comandante Banana

4/15/2011 1:33:00 PM

On Apr 15, 3:33 am, Jeanne Douglas <hlwd...@NOSPAMpacbell.net> wrote:
> In article
> <23a9f6ab-e865-4545-90e6-3076187f0...@v31g2000vbs.googlegroups.com>,
> Father Haskell <fatherhask...@yahoo.com> wrote:
>
>
>
> > On Apr 14, 10:16 pm, "His Highness the TibetanMonkey, the Beach
> > Cruiser Philosopher" <nolionnoprob...@yahoo.com> wrote:
> > > On Apr 14, 5:31 pm, "SFD" <s...@127000.00> wrote:
>
> > > > The reason he had this wonderful "blessed" imagination is because he
> > > > smoked
> > > > pot.
>
> > > Or banana peels.
>
> > > I just wonder why Christians make so much fuss about it.
>
> > > I bet you the Tree of Knowledge was marijuana.
>
> > > -----------------------------------------------------------
>
> > >http://webspawner.com/users/BANANA...
>
> > Moses was the first dope grower / dealer.
>
> > Ex. 30:23 Moreover, the Lord spake unto Moses, saying, Take
> > thou also unto thee principal spices, of pure myrrh five hundred
> > shekels, and of sweet cinnamon half so much, even 250 shekels,
> > and of qaneh-bosm 250 shekels. "Qaneh-bosm" obviously means
> > "cannabis" (weed with roots in Canaan?), and note that Moses is
> > breaking it into quarters.
>
> Now we see the difference between the intelligent and the stunted minds.
>
> I'd never heard this before, so of course I had to go looking for more
> info, and look at the site for the 1st hit:
>
> <http://www.cannabisculture.com/articles/109...
>
> It's a charming myth that's a little skewed from the classical
> Judeo-Christian mythology:
>
> "This article shows how the Old Testament Prophets were none other than
> ancient shamans, and that cannabis and other entheogens played a very
> prominent role in ancient Hebrew culture."
>
> How do they suppress their curiosity so much?

Was God himself high? Don't be surprised!

"GOD WANTS HERB"

The next direct reference to kaneh-bosm appears in Isaiah, where God
is reprimanding the Israelites for, among other things, not supplying
him with his due of the Holy Herb.

YOU HAVE NOT BROUGHT ANY KANEH FOR ME, OR LAVISHED ON ME THE FAT
OF YOUR SACRIFICES. BUT YOU HAVE BURDENED ME WITH YOUR SINS AND
WEARIED ME WITH YOUR OFFENCES.

ISAIAH 43:23-24

comp.lang.c++

sampling using iterators

Leon

Victor Bazarov

Juha Nieminen

Leon

Andrew Koenig

James Kanze

SFD

His Highness the TibetanMonkey, aka Comandante Banana

His Highness the TibetanMonkey, aka Comandante Banana

x Login to ForumsZone