为了分析排序算法,我想要一个 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
更快吗? ,为什么?
(我会自己对此进行分析,但我的家用硬件不足以对此进行测试。此外,我想要一个概念/理论解释。)
最佳答案
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)
关于java - 随机生成列表还是随机生成列表更快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18501998/