14

n 要素 (最大 100,000) の大きなリストを作成する必要があります。リスト内の各要素は、リストのインデックスに相当する整数です。この後、このリストで Collections.shuffle を呼び出す必要があります。私の質問は、どのリスト実装 (Java コレクションまたは Apache コレクション) を使用する必要があるかということです。私の直感では、ここで ArrayList を十分に使用できます。すべての考えに感謝します。ありがとう！

入力していただきありがとうございます。私はArrayListに固執していると思います。現在、initialCapacity パラメータを指定して ArrayList コンストラクタを使用しており、リストのサイズを渡しています。したがって、元のリストが 100000 の場合、この新しいリストを new ArrayList(100000) で作成します。したがって、サイズ変更がないため、配列を作成してasListを実行する必要はないと思います。また、GrowthList や LazyList などのほとんどの Apache コレクション リストは、RandomAccess を実装していません。これは確かにシャッフルを遅くします（javadocsによる）。FastArrayList は RandomAccess を実装しますが、Apache にはこのクラスに関する「このクラスはクロスプラットフォームではありません。使用すると、一部のアーキテクチャで予期しないエラーが発生する可能性があります」というメモがあります。

4

10 に答える 10

12

ArrayList は、おそらくリスト要素ごとのオーバーヘッドが最も少ないため、最良の選択です。リストの途中にあるアイテムを頻繁に削除する必要がある場合は、より悪い選択になる可能性があります。

于 2009-11-18T14:25:21.640 に答える
6

Collections.shuffle javadocからの引用：

このメソッドは線形時間で実行されます。指定されたリストがRandomAccessインターフェースを実装しておらず、大きい場合、この実装は、指定されたリストをシャッフルする前に配列にダンプし、シャッフルされた配列をリストにダンプします。これにより、「シーケンシャルアクセス」リストを適切にシャッフルした結果として生じる2次動作が回避されます。

したがって、他に必要がない場合は、RandomAccessを実装するArrayListを使用します。

于 2009-11-18T14:29:32.790 に答える
5

Integer配列を作成してからラップすると、Arrays.asList通常の よりもオーバーヘッドがさらに少なくなりますArrayList。

List<Integer> makeList(int size){
    if (size < 0) throw new IllegalArgumentException();
    Integer[] arr = new Integer[size];
    for (int i = 0; i < arr.length; ++i) arr[i] = i;
    List<Integer> list = Arrays.asList(arr);
    Collection.shuffle(list);
    return list;
}

スペース全体を 1 つ節約できますint(... このコンテキストではまったく何もありません) が、「実際の」よりも少ない範囲チェックを実行するArrayListため、アクセスはわずかに高速になります。しかし、おそらく何も気付かないでしょう:)

于 2009-11-18T15:13:51.140 に答える
2

Javolutionは、Java で最速の List 実装を持っていると主張しています。しかし、このライブラリにはシャッフルの実装が見つからなかったため、手動で行う必要があります。

于 2009-11-18T23:48:46.097 に答える
2

ArrayList<T>おそらく問題ありませんが、とにかく「最高」の基準は何ですか? とにかく、それはどれだけ良いものでなければなりませんか？それらの基準が何であれ、複雑さと「良さ」の間のトレードオフは何ですか?

于 2009-11-18T14:25:36.507 に答える
1

ArrayList や LinkedList よりも非常に高速なGlueListと呼ばれる新しい List 実装があります。

免責事項：私は実装を作成しました。

于 2015-11-07T10:18:07.480 に答える
1

Google のGuavaライブラリには、シャッフル可能なリストを返すInts.asList()メソッドなど、非常に優れたプリミティブ処理があります。

コードは慎重にレビューされ、Google で頻繁に使用されていますが、Guava プロジェクトはまだ展開の準備段階にあります。SVNからコードを取得し、com.google.common.primitive クラスを構築する必要があります。

于 2009-11-19T14:18:42.240 に答える
-1

ArrayListはこれに最適なリストになります。アレイのバッキングは、シャッフルで使用される要素を交換するのに非常に効率的です。

ただし、パフォーマンスを本当に追求している場合は、int []またはint[]に基づくカスタムリストの使用を検討することをお勧めします。すべてのListおよびList標準実装と同様に、intを整数にボックス化およびボックス化解除します。

これはポインタを並べ替えるだけなので、これはスフレでは問題になりませんが、必要がない場合は100,000個のオブジェクトを作成します。作成前にリストのサイズを知っていると仮定すると、プリミティブ配列をラップする新しいListクラスを非常に簡単に作成できます。java.util.Listとして使用する場合でも、getメソッドからの戻り値をボックス化する必要があります。

于 2009-11-18T15:06:59.797 に答える
-1

また、メモリ マップ ファイル ベースのリスト実装を使用することもできます。このような実装では、リストはメモリ内に完全には存在しませんが、巨大なリストのセクションのみがメモリ内でアクティブになります。ヒープ スペースの制限に達している場合 (主に 32 ビット jvm で)、通常のファイル I/O よりも高速なメモリ マップ ファイルを使用して、リストがシームレスにデータをプッシュする必要がある場合があります。そのような実装の 1 つは、このGoogle コードで説明されており、このリンクで説明されています。

于 2013-04-28T12:15:31.247 に答える