sampling using iterators

Discussion in 'C++' started by Leon, Oct 29, 2008.

  1. Leon

    Leon Guest

    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
     
    Leon, Oct 29, 2008
    #1
    1. Advertising

  2. 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.)
     
    Juha Nieminen, Oct 29, 2008
    #2
    1. Advertising

  3. Leon

    Leon Guest

    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!
     
    Leon, Oct 30, 2008
    #3
  4. "Leon" <> wrote in message
    news:geaa1v$8fm$...

    > 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.
     
    Andrew Koenig, Nov 13, 2008
    #4
  5. Leon

    James Kanze Guest

    On Oct 30, 12:13 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.


    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:
    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
     
    James Kanze, Nov 14, 2008
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ALuPin

    Over-Sampling

    ALuPin, Mar 11, 2005, in forum: VHDL
    Replies:
    5
    Views:
    1,932
  2. Albretch
    Replies:
    0
    Views:
    312
    Albretch
    Nov 29, 2004
  3. steflhermitte
    Replies:
    1
    Views:
    840
    Kanenas
    Apr 21, 2005
  4. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Replies:
    1
    Views:
    498
    Kai-Uwe Bux
    May 8, 2005
  5. , India
    Replies:
    10
    Views:
    1,092
    James Kanze
    Aug 8, 2009
Loading...

Share This Page