Erhalten Sie eine Unterliste die letzten 5 Elemente von LinkedHashSet?

Question

Gibt es ein Motto der letzten 5 Elemente eines LinkedHashSet in einem neuen LinkedHashSet zu bekommen?

das ist, was zur Zeit ich habe, aber es ist nicht sehr effizient:

new LinkedHashSet<String>(new LinkedList<String>(set) 
.subList(Math.max(0, set.size() - 5), set.size()); 

Oder sollte ich für diesen Fall verwenden ein TreeSet, SortedSet, HashSet?

Answer 1

Ich landete diese auf mit:

com.google.common.collect.EvictingQueue<E> 

damit Sie nur die letzten x Elemente zu halten bekommen.

EvictingQueue<String> queue = EvictingQueue.create(5); 

Answer 2

Wenn Sie Java 8 und Sie sind ok ein HashSet (anstelle eines LinkedHashSet) zurück zu erhalten, können Sie den Stream-API verwenden:

Set<String> newSet = set.stream() 
         .skip(set.size() - 5) 
         .collect(Collectors.<String>toSet()); 

Answer 3

ArrayList Verwenden Sie könnten eine bessere Leistung:

long s1 = System.nanoTime(); 
LinkedHashSet<String> last5 = new LinkedHashSet<String>(new LinkedList<String>(set) 
     .subList(Math.max(0, set.size() - 5), set.size())); 
System.out.println(System.nanoTime() - s1); 

s1 = System.nanoTime(); 
LinkedHashSet<String> usingArrayList = new LinkedHashSet<String>(new ArrayList<String>(set) 
     .subList(Math.max(0, set.size() - 5), set.size())); 
System.out.println(System.nanoTime() - s1); 

Answer 4

Hier ist das Problem. Die Iteratoren für eine LinkedHashSet sind unidirektional; d.h. Sie können nicht rückwärts iterieren, obwohl die zugrunde liegende Datenstruktur eine doppelt verknüpfte Liste hat. Das heißt, um das letzte N zu erhalten, müssen Sie bis zum Ende der Liste iterieren. Das ist O(N).

In Ihrem Algorithmus kopiert der LinkedList -Konstruktor den Satz in eine neue Datenstruktur, die (wahrscheinlich) den Iterator verwendet.

Im Gegensatz dazu verfügt die API TreeSet über eine descendingIterator()-Methode, die eine Iterator zurückgibt, die rückwärts durch die Liste iteriert. Wenn Sie das richtig verwenden, können Sie die letzten 5 Elemente des Satzes in O(1) abrufen. Der Nachteil ist, dass das Hinzufügen von Elementen zu der Menge O(logN) statt O(1) für eine Hash-basierte Menge ist.