C++向量与数组(时间)

Question

我和我在这里有两个程序,两个程序完成相同的任务.它们只是将布尔数组/向量设置为值true.使用向量的程序需要27秒才能运行,而涉及大小为5倍的数组的程序则需要不到1秒.我想知道为什么会有这么大的差异的确切原因？载体真的效率低吗？

程序使用向量

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int main(){
 const int size = 2000;
 time_t start, end;
 time(&start);
 vector<bool> v(size);
 for(int i = 0; i < size; i++){
  for(int j = 0; j < size; j++){
   v[i] = true;
  }
 }
 time(&end);
 cout<<difftime(end, start)<<" seconds."<<endl;
}

运行时 - 27秒

使用Array编程

#include <iostream>
#include <ctime>

using namespace std;

int main(){
 const int size = 10000; // 5 times more size
 time_t start, end;
 time(&start);
 bool v[size];
 for(int i = 0; i < size; i++){
  for(int j = 0; j < size; j++){
   v[i] = true;
  }
 }
 time(&end);
 cout<<difftime(end, start)<<" seconds."<<endl;
}

运行时间 - <1秒

平台 - Visual Studio 2008操作系统 - Windows Vista 32位SP 1处理器英特尔(R)奔腾(R)双CPU T2370 @ 1.73GHz内存(RAM)1.00 GB

谢谢

阿玛雷

Answer 1

你正在使用bool的std :: vector,这不是你想象的那样!

bool的矢量是一个不应该存在的混蛋子模板专业化,实际上每个位存储1个bool.由于屏蔽和移位逻辑,访问它会更复杂,因此肯定会慢一些.

点击这里查看关于bool矢量的一些信息.

此外,您可能正在运行未经优化的构建(几乎可以肯定的是,在您列出的时间内,对于400万次迭代,27秒是令人发指的).标准模板库非常依赖于优化器来执行内联函数调用和elide temporaries等操作.缺少这种优化会导致bool向量性能特别严重,因为它在索引时必须返回一个代理对象,因为你不能取一点地址,所以operator []不能返回一个引用.

点击这里获取有关代理容器的更多信息(后半部分是关于bool的矢量)

此外,许多STL实现都有有用的调试位,这些位不是标准的一部分,可以帮助您捕获错误,但实际上会降低性能.您需要确保在优化的构建中禁用了这些功能.

一旦你打开优化器,有正确的设置(即没有打开STL调试),并且实际上在两个循环中测试相同的东西,你将看到几乎没有差异.

我必须让你的循环更大才能在我的机器上进行测试,但是这里有两个我的机器上的bool循环向量构建,显示了优化器标志对STL代码的影响

$ g++ main.cpp 
$ ./a.out 
17 seconds.
$ g++ -O2 main.cpp 
$ ./a.out 
1 seconds.