Reverse iterator for a SortedSet ?

Discussion in 'Java' started by Sasha, Jan 12, 2004.

  1. Sasha

    Sasha Guest

    Hi there,

    is there an efficient way I can get the n largest objects from a SortedSet
    (i.e. java.util.TreeSet), without modifying it ?

    If the TreeSet has m entries and I want n values, then (I think) you can get
    the n SMALLEST entries in O(n . lg m) steps. ie --

    Iterator i = sortedSet.iterator()
    for (int count = 0; i.hasNext() && count < n; count++) {
    Object o = i.next();

    // do stuff with the object
    }

    But if I don't want to actually modify or duplicate the set (it's extremely
    large), how can I get the n LARGEST values? I don't have a reference to any
    objects appropriate for tailSet(). I suppose what I really want is a reverse
    iterator -- any such beast?

    AFAIKS, duplicating the list and re-sorting (or successively removing the
    tail) will give O(m . lg m + n . lg m).

    Can anyone see what I've overlooked?

    Thanks,

    Sasha
    Sasha, Jan 12, 2004
    #1
    1. Advertising

  2. "Sasha" <> wrote in message
    news:4001f813$0$27240$...
    > Hi there,
    >
    > is there an efficient way I can get the n largest objects from a SortedSet
    > (i.e. java.util.TreeSet), without modifying it ?
    >
    > If the TreeSet has m entries and I want n values, then (I think) you can

    get
    > the n SMALLEST entries in O(n . lg m) steps. ie --
    >
    > Iterator i = sortedSet.iterator()
    > for (int count = 0; i.hasNext() && count < n; count++) {
    > Object o = i.next();
    >
    > // do stuff with the object
    > }
    >
    > But if I don't want to actually modify or duplicate the set (it's

    extremely
    > large), how can I get the n LARGEST values? I don't have a reference to

    any
    > objects appropriate for tailSet(). I suppose what I really want is a

    reverse
    > iterator -- any such beast?
    >
    > AFAIKS, duplicating the list and re-sorting (or successively removing the
    > tail) will give O(m . lg m + n . lg m).


    Well,

    last() will get you the last one.

    For any item X, headSet(X).last() will get you the one previous to X

    Discovering how expensive headSet(X) is is left an an exercise for the
    reader.
    Mike Schilling, Jan 12, 2004
    #2
    1. Advertising

  3. Sasha

    ak Guest

    > But if I don't want to actually modify or duplicate the set (it's
    extremely
    > large), how can I get the n LARGEST values?

    SortedSet.tailSet();

    > I don't have a reference to any
    > objects appropriate for tailSet().

    what you have then?

    > I suppose what I really want is a reverse
    > iterator -- any such beast?

    Iterator of TreeSet is in ascending order.
    If you want descending order, then you have to set your own comparator.

    ____________

    http://reader.imagero.com the best java image reader.
    ak, Jan 12, 2004
    #3
  4. Sasha

    Adam Jenkins Guest

    Mike Schilling wrote:
    > "Sasha" <> wrote in message
    > news:4001f813$0$27240$...
    >
    >>Hi there,
    >>
    >>is there an efficient way I can get the n largest objects from a SortedSet
    >>(i.e. java.util.TreeSet), without modifying it ?
    >>
    >>If the TreeSet has m entries and I want n values, then (I think) you can

    >
    > get
    >
    >>the n SMALLEST entries in O(n . lg m) steps. ie --
    >>
    >>Iterator i = sortedSet.iterator()
    >>for (int count = 0; i.hasNext() && count < n; count++) {
    >> Object o = i.next();
    >>
    >> // do stuff with the object
    >>}


    Actually, this should take just O(n) time for any reasonable implementation.


    > Well,
    >
    > last() will get you the last one.
    >
    > For any item X, headSet(X).last() will get you the one previous to X
    >
    > Discovering how expensive headSet(X) is is left an an exercise for the
    > reader.


    Ugly! Almost certainly, SortedSet is implemented on top of some kind of
    tree datastructure, so headSet(X) will take O(log n) time. However,
    this solution is pretty ugly since the set returned by headSet wraps the
    original set. So lets say I wanted to get the last 100 items in the
    set. Your solution would be something like:

    // get last 100 items from a set
    SortedSet theSet = ...;
    List lastItems = new LinkedList();
    SortedSet head = theSet;
    for (int i = 0; i < 100 && !head.isEmpty(); i++) {
    Object last = head.last();
    lastItems.add(last);
    head = head.headSet(last); // create another wrap level
    }

    By the time you got to the 100th item, "head" would be wrapping the
    original set 100 levels deep, so each method call on "head" would be
    being delegated 100 times to get to the original Set. Yech!

    The bottom line is SortedSet doesn't support a lastNItems functionality
    in an efficient way, but a random access List would. If you need this
    functionality, maybe you should use a List instead.
    Adam Jenkins, Jan 13, 2004
    #4
    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. Larry Coon

    Re-sorting a SortedSet

    Larry Coon, Jun 2, 2004, in forum: Java
    Replies:
    5
    Views:
    1,261
    Chris Smith
    Jun 5, 2004
  2. Timo Nentwig
    Replies:
    6
    Views:
    8,718
    el goog
    Feb 26, 2005
  3. dogbite
    Replies:
    4
    Views:
    691
    osmium
    Oct 10, 2003
  4. Alexander Stippler

    reverse iterator operator==

    Alexander Stippler, Dec 31, 2003, in forum: C++
    Replies:
    8
    Views:
    586
    John Ericson
    Jan 1, 2004
  5. John Carter

    Bug: SortedSet gives warning.

    John Carter, Mar 4, 2005, in forum: Ruby
    Replies:
    2
    Views:
    114
    John Carter
    Mar 4, 2005
Loading...

Share This Page