我很好奇是否对 vector <vector<int>>
进行排序会比排序 vector <array <int, 3>>
慢. vector
的尺寸是 1000000 乘 3,下面是我的驱动程序代码:
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector <vector<int>> v(1000000, vector <int> (3));
srand(time(nullptr));
for(int i = 0; i < 1000000; ++i){
for(int j = 0; j < 3; ++j){
v[i][j] = rand();
}
}
double start = clock();
sort(v.begin(), v.end());
cout << (clock()-start)/(CLOCKS_PER_SEC/1000) << endl;
return 0;
}
编译 g++ -O3 sorting_test.cxx
使用 gcc 7.5.0,我得到大约 300 毫秒的运行时间。申报v
作为 vector <array <int, 3>>
将运行时间减半至 149 毫秒左右。但是,声明
v
作为 vector <tuple<int, int, int>>
击败上述两个选项,平均运行时间约为 100 ms
.我有点理解为什么
array
选项比 vector
更快选项( array
大小是一个常量表达式,与 vector
不同),但我不知道为什么 tuple
会打败他们两个。有人可以向我解释一下吗?填写
tuple <int, int, int>
的代码是srand(time(nullptr));
for(int i = 0; i < 1000000; ++i){
get <0> (v[i]) = rand();
get <1> (v[i]) = rand();
get <2> (v[i]) = rand();
}
最佳答案
虽然整个程序的反汇编过大,但这说明了operator<
之间的核心区别。为 array
和 tuple
:https://godbolt.org/z/h1Y33e
本质上,在元组版本中,您有 3 个元素的固定比较,而在数组版本中,您有一个循环。
虽然我很惊讶编译器没有展开循环。
编辑:看起来像 clang 确实优化了它们,非循环代码:https://godbolt.org/z/cMExTb (我没有完全阅读它,但我只看到向前跳跃)
关于c++ - 为什么对 std::tuple 的 std::vector 进行排序比对 std::arrays 的 vector 排序更快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64232212/