为什么处理已排序的数组比处理未排序的数组更快？
2022-08-31 01:21:34
下面是一段C++代码，显示了一些非常奇特的行为。出于某种奇怪的原因，对数据进行排序（在定时区域之前）奇迹般地使循环速度提高了近六倍。
#include <algorithm>
#include <ctime>
#include <iostream>
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);
// Test
clock_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<double>(clock()-start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << '\n';
std::cout << "sum = " << sum << '\n';
}
- 如果没有，代码将在 11.54 秒内运行。
std::sort(data, data + arraySize); - 使用排序后的数据，代码将在 1.93 秒内运行。
（排序本身需要比这个数组更多的时间，所以如果我们需要为一个未知数组计算这个，它实际上不值得这样做。
最初，我认为这可能只是一种语言或编译器异常，所以我尝试了Java：
import java.util.Arrays;
import java.util.Random;
public class Main
{
public static void main(String[] args)
{
// Generate data
int 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 faster
Arrays.sort(data);
// Test
long 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);
}
}
具有类似但不那么极端的结果。
我的第一个想法是排序将数据带入缓存，但后来我认为这是多么愚蠢，因为数组刚刚生成。
- 这是怎么回事？
- 为什么处理已排序的数组比处理未排序的数组更快？
代码总结了一些独立的术语，因此顺序无关紧要。
相关/后续问答，关于不同/更高版本的编译器和选项的相同效果：
