这是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';
}
- 不无
std::sort(data, data + arraySize);代码在11.54秒内运行
- 根据分类数据 代码在1.93秒内运行
(分类本身需要的时间比这个通过数组的时间要长, 所以如果我们需要计算未知数组, 它实际上不值得做 。)
起初,我以为这只是一种语言或编译器异常, 所以我尝试了爪哇:
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);
}
}
其结果类似,但不太极端。
我第一种想法是 分类能把数据带进缓存缓存,但那是愚蠢的 因为阵列是刚刚产生的。
- 这是怎么回事?
- 为什么处理一个分类阵列的速度要快于处理一个未排序阵列的速度?
守则正在总结一些独立的术语,因此命令不应重要。
相关/后续行动不同/以后的编译者和选项的相同效果:
巴恩·斯特鲁斯特鲁斯特鲁普的回答对此问题:
这听起来像面试问题。是真的吗?你怎么知道?回答效率问题而不首先做一些测量是不明智的,所以知道如何衡量是很重要的。
于是,我用百万整数的矢量尝试过,然后得到:
Already sorted 32995 milliseconds
Shuffled 125944 milliseconds
Already sorted 18610 milliseconds
Shuffled 133304 milliseconds
Already sorted 17942 milliseconds
Shuffled 107858 milliseconds
我跑了好几次才确定。 是的,这个现象是真实的。我的关键代码是:
void run(vector<int>& v, const string& label)
{
auto t0 = system_clock::now();
sort(v.begin(), v.end());
auto t1 = system_clock::now();
cout << label
<< duration_cast<microseconds>(t1 — t0).count()
<< " milliseconds\n";
}
void tst()
{
vector<int> v(1'000'000);
iota(v.begin(), v.end(), 0);
run(v, "already sorted ");
std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
run(v, "shuffled ");
}
至少这个编译器、 标准库和优化设置是真实存在的。 不同的执行可以而且确实提供了不同的答案。 事实上,有人做了更系统的研究( 快速的网络搜索会找到它) , 而大多数执行都显示了这种效果。
其中一个原因是分支预测: 类算法中的关键操作是“if(v[i] < pivot]) …”对于排序序列,测试总是真实的,而对于随机序列,选定的分支则随机变化。
另一个原因是,当矢量已经分类后,我们从不需要将元素移到正确位置。这些小细节的影响是我们看到的5或6个系数。
Quicksort(以及一般分类)是一项复杂的研究,吸引了计算机科学中最伟大的一些思想。 一种良好的功能是选择良好的算法和关注硬件的运行效果的结果。
如果您想要写入高效代码, 您需要了解一些关于机器结构的知识 。
除了树枝预测可能会减慢你的速度之外 分解阵列还有另一个优势
您可以有一个停止状态, 而不是仅仅检查值, 这样你只能环绕相关数据, 忽略其它数据 。
分支预测只会错失一次。
// sort backwards (higher values first), may be in some other part of the code
std::sort(data, data + arraySize, std::greater<int>());
for (unsigned c = 0; c < arraySize; ++c) {
if (data[c] < 128) {
break;
}
sum += data[c];
}
快速和简单理解的答案(阅读其他细节)
这一概念被称为子分支预测
分支预测是一种优化技术,它预言代码在被确知之前将走的道路。 这一点很重要,因为在代码执行过程中,机器预设了几条代码声明并将其储存在管道中。
问题出在有条件的分支中,有两种可能的路径或代码部分可以执行。
当预测是真实的, 优化技术 完成。
当预测是虚假的,用简单的方式解释, 管道中储存的代码声明被证明是错误的, 而实际的代码必须全部重新加载, 这需要很多时间。
正如常识所显示的,对某类物品的预测比对某类未分类物品的预测更准确。
分支预测可视化:
已分类
未排序
其他答复的假设是,一个人需要对数据进行分类是不正确的。
以下代码不排序整个阵列,但只排序其中的200个元素部分,因此运行速度最快。
只对 K 元素部分进行排序,以线性时间完成预处理,O(n),而不是O(n.log(n))排序整个阵列需要时间 。
#include <algorithm>
#include <ctime>
#include <iostream>
int main() {
int data[32768]; const int l = sizeof data / sizeof data[0];
for (unsigned c = 0; c < l; ++c)
data[c] = std::rand() % 256;
// sort 200-element segments, not the whole array
for (unsigned c = 0; c + 200 <= l; c += 200)
std::sort(&data[c], &data[c + 200]);
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i) {
for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
if (data[c] >= 128)
sum += data[c];
}
}
std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
std::cout << "sum = " << sum << std::endl;
}
这个“证明”也与任何算法问题无关, 比如排序顺序, 并且确实是分支预测。
我用MATLAB 2011b 和我的MacBook Pro(Intel i7, 64位, 2.4 GHz) 尝试了以下MATLAB 代码的相同代码 :
% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);
%Sort the data
data1= sort(data); % data1= data when no sorting done
%Start a stopwatch timer to measure the execution time
tic;
for i=1:100000
for j=1:arraySize
if data1(j)>=128
sum=sum + data1(j);
end
end
end
toc;
ExeTimeWithSorting = toc - tic;
上述MATLAB代码的结果如下:
a: Elapsed time (without sorting) = 3479.880861 seconds.
b: Elapsed time (with sorting ) = 2377.873098 seconds.
校对:Soup
a: Elapsed time (without sorting) = 19.8761 sec.
b: Elapsed time (with sorting ) = 7.37778 sec.
基于这个,看来MATLAB几乎是175乘175次低于 C 执行的慢于 C 执行,没有排序和350乘350次换句话说,其效果(分支预测)是:1.46x执行和2.7x执行《公约》的《公约》。
