java - SortedSetの最後の25要素を取得するには?

Question

Java では、100,000 個の要素を持つことができる SortedSet があります。最後の 25 要素を効率的かつエレガントに取得したいと考えています。私は少し困惑しています。

最初の 25 個の要素を取得するには、反復して 25 個の要素で停止します。しかし、逆の順序で反復する方法がわかりません。何か案は？

SortedSet<Integer> summaries = getSortedSet();
// what goes here :-(

score 15 · Accepted Answer

が必要ですNavigableSet。それ以外の場合は、非効率的に実行する必要があり、全体を反復して、SortedSet要素をに収集しQueue、25 要素でトリミングし続けます。

score 4 · Accepted Answer

SortedSet<T>は、前方のみの非常に単純な反復モデルを想定して設計されているため、上位 n エントリを見つけるのは簡単ですが、最後のエントリを見つけるには、最後の n エントリのウィンドウを維持する反復子を介して高価な読み取りが必要になります。

1.6 で追加されたNavigableSet<T>はこれを解決します (そして、1.4 TreeSet からの SortedSet 実装のみがそれを実装しているため、ドロップインの代わりになる可能性があります)。

NavigableSet<T> set = new TreeSet<T>();
// add elements
set.descendingIterator() // iterate over the last n entires as needed

score 3 · Accepted Answer

並べ替えを逆にして、最初の 25 項目を取ります。その後、わずか 25 アイテムとして効率的なものを逆にすることができます。

ブルース

score 1 · Accepted Answer

繰り返しなしで index の要素に到達するには、exact(size-25) を使用します。

score 1 · Accepted Answer

この操作には、別のデータ構造の方が適しています。

これは洗練された方法でも非常に効率的な方法でもありませんが、SortedSet が昇順であると仮定すると、Last() アイテムを取得して削除し、別のリストに格納して 25 回繰り返すことができます。その後、これらの要素を元に戻す必要があります。

score 1 · Accepted Answer

Set を List にスローし、subList() を使用します。リストを作成するのがどれほど効率的かはわからないので、いくつかのテストを実行する必要があります。ただし、コーディングは確かに簡単になります。

    List f = new ArrayList( summaries);
    List lastTwentyFive = f.subList( summaries.size() - 25, summaries.size() );

score 0 · Accepted Answer

これがプロジェクトで実際に使用される可能性は低いと思いますが、代わりにリストを反対方向に並べ替えることができる可能性があることに注意してください:)

7 に答える 7