How to get the last 25 elements of a SortedSet?

Question

In Java I have a SortedSet that may have 100,000 elements. I would like to efficiently and elegantly get the last 25 elements. I'm a bit puzzled.

To get the first 25 I'd iterate and stop after 25 elements. But I don't know how to iterate in reverse order. Any ideas?

SortedSet<Integer> summaries = getSortedSet();
// what goes here :-(

Answer 1

You need a NavigableSet. Else you’ll have to do it inefficiently, iterating through the whole SortedSet and collecting elements into a Queue that you keep trimmed at 25 elements.

Answer 2

SortedSet<T> was designed assuming a very simple iteration model, forward only, thus finding the top n entries is easy but finding the last would require an expensive read through the iterator maintaining a window of the last n entries.

NavigableSet<T> adding in 1.6 solves this (and the only SortedSet implementation from 1.4 TreeSet implements it so it is likely to be a drop in replacement for you).

NavigableSet<T> set = new TreeSet<T>();
// add elements
set.descendingIterator() // iterate over the last n entires as needed

Answer 3

Reverse your sort and take the first 25 items. You can then reverse those which will be efficient as its only 25 items.

Bruce

Answer 4

A different data structure would be more appropriate for this operation.

This is not an elegant way or very efficient, but assuming the SortedSet is in ascending order you could get the Last() item and remove it, storing it in another list, and repeat 25 times. You would then have to put these elements back again!

Answer 5

You may want to take a look at IndexedTreeMap in indexed-tree-map

Use exact(size-25) to get to the element at index without iteration.

Answer 6

Throw the Set into a List and use subList(). I'm not sure how performant it is to create the List, so you'd have to run some tests. It'd certainly make the coding easy though.

    List f = new ArrayList( summaries);
    List lastTwentyFive = f.subList( summaries.size() - 25, summaries.size() );

Answer 7

I'm assuming that this is unlikely to be of any real-life use in your project, but it's worth noting that you might simply be able to have the list sorted in the opposite direction instead :)