为什么处理排序数组比处理未排序数组更快？
这是一段C++代码，显示了一些非常奇怪的行为。
出于某种原因，对数据进行排序（之前定时区域）奇迹般地使主循环快了近六倍：
#include
#include
#include
int main(){// Generate data
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
// !!! With this, the next loop runs faster.std::sort(data, data + arraySize);
// Testclock_t start = clock();long long sum = 0;for (unsigned i = 0; i < 100000; ++i){for (unsigned c = 0; c < arraySize; ++c){ // Primary loop.if (data[c] >= 128)sum += data[c];}}
double elapsedTime = static_cast(clock()-start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << '\n';std::cout << "sum = " << sum << '\n';} - 如果没有
std::sort(data, data + arraySize);，代码将在11.54秒内运行。 - 使用排序的数据，代码在1.93秒内运行。
（排序本身比遍历数组需要更多的时间，所以如果我们需要为未知数组计算它，实际上不值得这样做。
最初，我认为这可能只是一种语言或编译器异常，所以我尝试Java：
import java.util.Arrays;import java.util.Random;
public class Main{public static void main(String[] args){// Generate dataint arraySize = 32768;int data[] = new int[arraySize];
Random rnd = new Random(0);for (int c = 0; c < arraySize; ++c)data[c] = rnd.nextInt() % 256;
// !!! With this, the next loop runs fasterArrays.sort(data);
// Testlong start = System.nanoTime();long sum = 0;for (int i = 0; i < 100000; ++i){for (int c = 0; c < arraySize; ++c){ // Primary loop.if (data[c] >= 128)sum += data[c];}}
System.out.println((System.nanoTime() - start) / 1000000000.0);System.out.println("sum = " + sum);}}类似但不那么极端的结果。
我的第一个想法是排序将数据带入缓存，但这很愚蠢，因为数组刚刚生成。
- 这是怎么回事？
- 为什么处理排序数组比处理未排序数组更快？
代码总结了一些独立的术语，所以顺序应该无关紧要。
相关/后续问答关于不同/更高版本编译器和选项的相同效果：
最佳答案