75

List と Set のパフォーマンス、メモリ割り当て、使いやすさの比較を知りたいです。

オブジェクトのリストに一意性を維持する必要がなく、挿入順序を維持する必要もない場合、ArrayList と SortedSet/HashSet を交互に使用できますか? リスト/セットの代わりに Collections クラスを直接使用するのは良いでしょうか?

PS また、Java が提供する特定の関数をリストまたは設定する必要もありません。追加のプログラミング作業なしで動的に拡張できるという理由だけで、Array の代わりに List/Set を使用しています。

4

6 に答える 6

108

HashSet同じ数の要素の場合よりも約 5.5 倍多くのメモリを消費しArrayList(どちらも線形ですが)、反復が大幅に遅くなります (同じ漸近線ではありますが)。Google で簡単に検索すると、HashSetイテレーションはArrayList.

の一意性やパフォーマンスを気にしない場合はcontains、 を使用してArrayListください。

于 2012-05-29T12:57:48.497 に答える
64

順序を気にせず、要素を削除しない場合は、このデータ構造で要素を検索する必要があるかどうか、およびそれらの検索をどれだけ高速にする必要があるかということになります。

a の値による要素の検索HashSetはO(1). では、ArrayListですO(n)。

コンテナーを使用して一連の一意のオブジェクトを格納し、最後にそれらを (任意の順序で) 反復処理する場合ArrayListは、よりシンプルで経済的であるため、間違いなくより良い選択です。

于 2012-05-29T12:47:36.497 に答える
4

ArrayList要素の追加のみを計画し、後でそれらを反復処理する場合は、置換する配列に最も近いことが最善の策です。LinkedListどの実装よりもメモリ効率が高くSet、挿入、反復、およびランダムアクセスが高速です。

于 2012-05-29T12:58:47.727 に答える
3

リストとセットを検索して比較すると、アンダーラインのハッシュアルゴリズムにより、セットの方が優れています。

リストの場合、最悪の場合、contains は最後まで検索します。Set の場合、ハッシュとバケットのため、サブセットのみを検索します。

使用例: ArrayList と HashSet に 1 ～ 100_000 の整数を追加します。ArrayList と HashSet で各整数を検索します。

Set には 9 ミリ秒かかりますが、List には 16232 秒かかります。

private static void compareSetvsList(){
    List<Integer> list = new ArrayList<>() ;
    Set<Integer> set = new HashSet<>() ;

    System.out.println("Setting values in list and set .... ");
    int counter = 100_000  ;

    for(int i =0 ; i< counter ; i++){            
        list.add(i);
        set.add(i);
    }

    System.out.println("Checking time .... ");
    long l1 = System.currentTimeMillis();
    for(int i =0 ; i< counter ; i++) list.contains(i);

    long l2 = System.currentTimeMillis();
    System.out.println(" time taken for list : "+ (l2-l1));

    for(int i =0 ; i< counter ; i++)set.contains(i);

    long l3 = System.currentTimeMillis();
    System.out.println(" time taken for set : "+ (l3-l2));

    //      for 10000   time taken for list : 123        time taken for set : 4
    //      for 100000  time taken for list : 16232          time taken for set : 9
    //      for 1000000 time taken for list : hung       time taken for set : 26

}
于 2019-01-24T19:18:23.790 に答える
1

コレクションに一意の要素を含めるArrayList必要がない場合は、非常に具体的なニーズがない限り、単純に使用してください。

コレクションに一意の要素のみを含める必要があるHashSet場合は、非常に具体的なニーズがない限り使用してください。

JavaDocによるSortedSetと、（およびそれは実装者です）に関して：TreeSet

要素の全体的な順序付けをさらに提供する Set。要素は、自然な順序付けを使用するか、通常は並べ替えセットの作成時に提供される Comparator によって順序付けられます。

つまり、要素を常に a で順序付けする必要がある、非常に特定のユースケースを対象としていますがset、これは通常は必要ありません。

于 2012-05-29T12:53:24.250 に答える