比較可能なVs TreeSetのリスト

Question

オプション1：値を追加するたびにComparableを実装し、collections.sort（List l）を使用してソートするリストを作成します。 オプション2：TreeSetを作成します（それ自体が常にソートされます）。

どちらが高速になりますか？私はこれを頼んでいるのは、Listが私に必要なListIteratorのオプションを与えるからです。なぜなら、反復中に要素を追加できるからです。

Answer 1

最も重要な違い：

Criterion  | List with Collections.sort | TreeSet 
----------------+----------------------------+--------- 
cost of adding | O(n log n)     | O(log n) 
equal sort keys | permitted     | eliminated as duplicates 
iteration  | bidirectional, can insert | unidirectional, can not insert 

ConcurrentModificationExceptionを得ることなく繰り返し処理を行う場合、要素を挿入するには、あなたが行うことができます：

for (E e : new ArrayList<E>(collection)) { 
    // some other code 

    collection.add(anotherE); 
} 

Answer 2

ここでツリーセットを使用してください。

TreeSetに追加する操作はlog(n)です。リストに追加するのはconst timeですが、ソートするのはn log(n)です。

Answer 3

Collections.sortがnlogで修正マージソートを使用しています（n）ソート時間。追加するたびにメソッドを呼び出すと、n^2log（n）の時間になる可能性があります。 TreeSetの挿入はlog（n）を保証します。したがって、追加するたびに呼び出すと、n.log（n）になります。ですから、代わりにTreeSetを使うことをお勧めします。しかし、TreeSetは重複を許さないので、あなたの決定に影響するかもしれません。

Listを使用している場合、Collections.sortを使用する代わりに、最適化することが1つあります。リストに要素を挿入するたびにリストがソートされるので、ここでの挿入並べ替えを使用すると、そのような場合に挿入の並べ替えが優れているため、パフォーマンスが向上します。