Obtenez une sous-liste des 5 derniers éléments de LinkedHashSet?

Question

Y a-t-il un seul revêtement pour obtenir les 5 derniers éléments d'un LinkedHashSet dans un nouveau LinkedHashSet?

C'est ce que j'ai actuellement, mais ce n'est pas très efficace:

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

Ou devrais-je utiliser pour ce cas un TreeSet, SortedSet, HashSet?

Answer 1

Je fini par utiliser ceci:

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

avec cela, vous pouvez garder seulement les derniers éléments de x.

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

Answer 2

Si vous utilisez Java 8 et vous êtes ok pour retourner un HashSet (au lieu d'un LinkedHashSet), vous pouvez utiliser l'API Stream:

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

Answer 3

En utilisant ArrayList vous pourriez obtenir une meilleure performance:

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

Voici le problème. Les itérateurs d'un LinkedHashSet sont unidirectionnels; c'est-à-dire que vous ne pouvez pas parcourir en arrière, même si la structure de données sous-jacente comporte une liste à double liaison. Cela signifie que vous devez obtenir le dernier N dont vous avez besoin pour parcourir jusqu'à la fin de la liste. C'est O(N).

Dans votre algorithme, le constructeur LinkedList copie l'ensemble dans une nouvelle structure de données en utilisant (probablement) l'itérateur.

Par contre, l'API TreeSet a une méthode descendingIterator() qui renvoie un Iterator qui itère en arrière dans la liste. Si vous l'utilisez correctement, vous pouvez obtenir les 5 derniers éléments de l'ensemble en O(1). L'inconvénient est que l'ajout d'éléments à l'ensemble sera O(logN) au lieu de O(1) pour un ensemble basé sur le hachage.