我在 Java 中实现桶排序，我发现当输入数组被排序（升序或降序）而不是随机时，它的排序（升序）更快。为什么是这样？据我了解，它只是遍历数组并在每个元素的索引处递增“计数”数组。我不明白为什么使用排序输入它会运行得更快，但它似乎快了两倍。
谢谢
问问题
336 次
1 回答
3
原因很可能是由于空间局部性和排序输入集的更高缓存命中率。
如果您对输入进行了排序，则同一邻域中的桶相对会获得一堆命中，并且随着您的排序输入移动到更高的范围，下一个桶的邻域将开始获得命中。
考虑一个简化的例子来说明这一点：
假设您有 10 个范围大小为 1,000 的桶：
[0-999], [1000-1999], ..., [9000-9999]
并假设您一次只能缓存对一个存储桶的引用（这是人为的部分，但实践中的想法是相同的：
现在假设您的输入集是之间的随机数[0 - 9999]
- 如果输入被排序，每个桶将恰好得到一个初始缓存未命中，然后是多次缓存命中，直到输入中的序列移动到下一个桶的范围内。
- 如果您有未排序的输入，并且在最坏的情况下，缓存将始终丢失，并将另一个存储桶加载到缓存中，并且只会再次丢失，因为未排序序列中的下一个数字将寻找另一个存储桶。
于 2013-03-07T04:59:07.850 回答