Extract first k elements from a Set efficiently

Question

Problem

I'm writing a simple Java program in which I have a TreeSet which contains Comparable elements (it's a class that I've written myself). In a specific moment I need to take only the first k elements from it.

What I've done

Currently I've found two different solution for my problem:

Using a simple method written by me; It copies the first k elements from the initial TreeSet;
Use Google Guava greatestOf method.

For the second option you need to call the method in this way: Ordering.natural().greatestOf(mySet, 80))

But I think that it's useless to use this kind of invocation because the elements are already sorted. Am I wrong?

Question

I want to ask here which is a correct and, at the same time, efficient method to obtain a Collection derived class which contains the first k elements of a TreeSet?

Additional information

Java version: >= 7

Do you wish the new collection to change if the original `Set` changes? If so you could wrap the `Set` in another object - a very efficient mechanism. — OldCurmudgeon, Sep 02 '14 at 15:20
I don't want to close yet, but it seems like partially dupe of [this thread](http://stackoverflow.com/q/10751953/572670), at least in the algorithmic part of it. — amit, Sep 02 '14 at 15:21
"...the elements are already sorted..." The elements of a java.util.SortedSet are sorted. The elements of a java.util.Set have no defined ordering. (That is to say, an implementation of Set is allowed to iterate over its elements in any order.) — Solomon Slow, Sep 02 '14 at 15:25

Alan Stokes · Accepted Answer · 2014-09-02T15:32:19.080

2

You could use Guava's Iterables#limit:

ImmutableList.copyOf(Iterables.limit(yourSet, 7))

http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Iterables.html#limit(java.lang.Iterable, int)

edited Sep 02 '14 at 15:32

answered Sep 02 '14 at 15:25

Alan Stokes

18,815
3
45
64

I'm trying your solution, it seems the best one. – Alessandro Suglia Sep 02 '14 at 15:29

WoDoSc · Answer 2 · 2014-09-02T15:28:08.560

1

I would suggest you to use a TreeSet<YourComparableClass> collection, it seems to be the solution you are looking for.

A TreeSet can return you an iterator, and you can simply iterates K times, by storing the objects the iterator returns you: the elements will be returned you in order.

Moreover a TreeSet keep your elements always sorted: at any time, when you add or remove elements, they are inserted and removed so that the structure remains ordered.

Here a possible example:

public static ArrayList<YourComparableClass> getFirstK(TreeSet<YourComparableClass> set, int k) {
    Iterator<YourComparableClass> iterator = set.iterator();
    ArrayList<YourComparableClass> result = new ArrayList<>(k); //to store first K items
    for (int i=0;i<k;i++) result.add(iterator.next()); //iterator returns items in order
    //you should also check iterator.hasNext(); if you are not sure to have always a K<set.size()
    return result;
}

edited Sep 02 '14 at 15:28

answered Sep 02 '14 at 15:20

WoDoSc

2,598
1
13
26

This answer could be associated with my first solution. Is it right? – Alessandro Suglia Sep 02 '14 at 15:22
@AlessandroSuglia yes, now that you've edited your question is more clear that you already had in mind a solution of this kind – WoDoSc Sep 02 '14 at 15:31
Thank you for your suggestion. But I think that it's useless to write a method again if there is something really good available :) – Alessandro Suglia Sep 02 '14 at 15:32
@AlessandroSuglia actually the TreeSet is the only collections that fir your requirements, but it does not provide a method like the one you described, so if you want to use a TreeSet this is the easier way to do.. if you want to use Guava then it's another story ;) – WoDoSc Sep 02 '14 at 15:37
You can more elegantly do it in a single statement: `return (ArrayList) set.stream().limit(k).collect(Collectors.toList());` – Dheeru Mundluru Jun 02 '21 at 05:49

score 0 · Answer 3 · answered Sep 02 '14 at 15:20

The descendingIterator() method of java.util.TreeSet yields elements from greatest to least, so you can just step it however many times, inserting the elements into a collection. The running time is O(log n + k) where k is the number of elements returned, which is surely fast enough.

If you're using a HashSet, on the other hand, then the elements in fact are not sorted, so you need to use the linear-time selection method that you indicated.

Extract first k elements from a Set efficiently

3 Answers3