1

並べ替えアルゴリズムのプロファイリングで使用するために、ArrayList<Integer>100 万ドルの整数が必要です。整数の境界は問題ではありません: [0, MAX_VALUE], [ MIN_VALUE, MAX_VALUE] などはすべて問題ありませんが、それらを広く配布したいと考えています。

このコードを使用すると、次のことに気付きます。

for (int i=0; i<1_000_000; i++) {
    list.add(i);
}
Collections.shuffle(list);
mergeSorter.sort(list);

呼び出しのshuffle実行には約 10 秒かかりますが、マージ ソートには 2 ミリ秒しかかかりません。

したがって、私の質問:を使用するよりも、これらの数値をランダムに生成する ( list.add((int) (Math.random() * 1_000_000)))方が高速でしょうshuffleか? また、その理由は?

(私はこれを自分でプロファイリングしますが、私のホーム ハードウェアではこれをテストするには不十分です。さらに、概念的/理論的な説明が必要です。)

4

2 に答える 2

4

Collections.shuffle()Randomフードの下で使用します。

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

よく見ると、2 つのループが実行されています。

  • 新しい配列を作成するための 1 つ
  • リストを更新するための 1 つ。

これを自分で行う場合は、2 番目のループを省略して、GCにListを収集させることができます。また、最初から配列がある場合は、新しいコピーを作成する必要さえありません。

そうです、自分でやるとパフォーマンスが向上しますが、時間の複雑さは依然としてO(n)になります

于 2013-08-29T04:03:41.807 に答える