Reverse iterator for a SortedSet ?

[Sasha]

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

 

[Mike Schilling]

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.

 

[ak]

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.

 

[Adam Jenkins]

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.