java - 比較可能な対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

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

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

Answer 3

ここでTreeSetを使用します。

TreeSetへの追加はlog(n)操作です。リストへの追加は一定時間ですが、並べ替えはですn log(n)。