java - 随机生成列表还是随机生成列表更快？

Question

为了分析排序算法，我想要一个 ArrayList<Integer>一百万 dollars 整数。整数的范围无关紧要:[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 更快吗？ ，为什么？

(我会自己对此进行分析，但我的家用硬件不足以对此进行测试。此外，我想要一个概念/理论解释。)

Answer 1

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]);
        }
    }
}

如果仔细观察，会执行两个 循环。

• 一个用于创建新数组
• 一个用于更新列表。

如果您自己执行此操作，则可以取消第二个 循环并让GC 收集List。如果您有一个数组开始，您甚至不需要创建一个新副本。

所以是的，自己做会提高性能，但时间复杂度仍然是O(n)