LinkedHashSetの最後の5つの要素のサブリストを取得しますか？

Question

新しいLinkedHashSetでLinkedHashSetの最後の5要素を取得するライナーは1つありますか？

これは私が現在持っているものですが、それは非常に効率的ではありません。

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

または私はこの場合TreeSetの、にSortedSet、HashSetのために使うべきでしょうか？

Answer 1

私はこれを使用して終了：これで

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

をあなただけ最後のx個の要素を手にします。

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

Answer 2

は、Java 8を使用して、（代わりにLinkedHashSetの）HashSetを取り戻すしても大丈夫な場合は、ストリームAPIを使用することができます。

ArrayListを使用して

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

Answer 3

あなたはより良いパフォーマンスを得ることができます：

を

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

ここに問題があります。 LinkedHashSetのイテレータは単方向です。基礎となるデータ構造に二重リンクリストがある場合でも、逆方向に反復することはできません。これは、リストの最後まで繰り返す必要がある最後のN個を取得することを意味します。つまり、O(N)です。

アルゴリズムでは、LinkedListコンストラクタは、（おそらく）イテレータを使用して新しいデータ構造にセットをコピーしています。

対照的に、TreeSet APIにはdescendingIterator()メソッドがあり、これはリストを逆方向に反復するIteratorを返します。これを正しく使用すると、セットの最後の5つの要素をO(1)に取得できます。欠点は、要素をセットに追加することは、ハッシュベースのセットに対してO(1)の代わりにO(logN)になることです。