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

Question

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

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

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

または、この場合、 TreeSet 、 SortedSet 、 HashSet を使用する必要がありますか?

score 0 · Accepted Answer

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

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

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

score 0 · Accepted Answer

Java 8 を使用していて、HashSet( の代わりにLinkedHashSet) を取得しても問題ない場合は、Stream API を使用できます。

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

score 0 · Accepted Answer

を使用ArrayListすると、パフォーマンスが向上します。

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);

score 0 · Accepted Answer

私はこれを使用することになりました：

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

これにより、最後の x 要素のみを保持できます。

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

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

4 に答える 4

Related

Reference