1

为了用于分析排序算法，我想要ArrayList<Integer>一百万美元的整数。整数的范围无关紧要：[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]);
        }
    }
}

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

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

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

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

于 2013-08-29T04:03:41.807 回答
3

随机生成这些数字会(list.add((int) (Math.random() * 1_000_000)))比使用 shuffle 更快吗？为什么？

生成这样的数字更快，但你会得到不同的结果！

  • 如果将数字 0 到 N-1 的列表打乱，您将得到一个没有重复的列表。

  • 如果您在 0 到 N-1 范围内生成丢失的 N 个随机数，您可能会得到一个包含重复项的列表。

如果生成 N 个随机数是可以的，那肯定会比洗牌更快。从代码中可以看出，最好的情况shuffle是生成 N 个随机数并执行 N 次交换。

执行 shuffle 调用大约需要 10 秒，而归并排序只需要 2 毫秒。

我不确定您为什么要比较 shuffle 和 mergesort（或者您正在使用什么合并排序器！），但我怀疑差异更多地与您编写基准的方式有关，而不是其他任何事情。（看起来您可能不允许 JVM 预热效果。）

于 2013-08-29T04:10:59.310 回答