C ++矢量VS阵列（时间） [英] C++ Vector vs Array (Time)

问题描述

我这里有两个节目我，无论正在做同样的任务。他们只是在设置布尔数组/矢量值true。采用矢量程序
需要27秒，而运行涉及阵列5倍的容量，程序只需要不到1秒。我想知道确切的原因，为什么会有这样的主要区别？是矢量
真的那么低效率？

I have got here two programs with me, both are doing exactly the same task. They are just setting an boolean array / vector to the value true. The program using vector takes 27 seconds to run whereas the program involving array with 5 times greater size takes less than 1 s. I would like to know the exact reason as to why there is such a major difference ? Are vectors really that inefficient ?

使用矢量程序

#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;
}

运行 - 26秒。

Runtime - 27 seconds

使用数组程序

#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;
}

运行 - ＆LT; 1秒

Runtime - < 1 seconds

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

Platform - Visual Studio 2008 OS - Windows Vista 32 bit SP 1 Processor Intel(R) Pentium(R) Dual CPU T2370 @ 1.73GHz Memory (RAM) 1.00 GB

感谢

阿玛雷

推荐答案

您正在使用的std ::布尔的载体，这不是你认为它是！

布尔的载体是应该就不存在了，并在每个位实际存储1布尔一个私生子模板特殊化。访问到它更加复杂，由于掩蔽和不断变化的逻辑，所以肯定会有些慢。

vector of bool is a bastard child template specialization that should never have existed and actually stores 1 bool in each bit. Accesses into it are more complicated due to masking and shifting logic, so will definitely be somewhat slower.

单击此处查找有关布尔矢量一些信息。

此外，您可能正在运行一个未优化的版本（几乎可以肯定给你列出的时间27秒离谱的400万次迭代）。标准模板库非常依赖优化做的事情像内联函数调用的Elid和临时。缺乏这种优化将导致特别严重的性能下降为布尔的载体，因为它返回一个代理对象，当你索引到，因为你不能把一个位的地址，这样的运算符[] 不能返回引用。

Also, you may be running an unoptimized build (almost certainly given the times you listed, 27 seconds is outrageous for 4 million iterations). The Standard Template Library relies very heavily on the optimizer to do things like inline function calls and elide temporaries. Lack of this optimization causes an especially heavy performance degradation for vector of bool because it has to return a proxy object when you index into it, because you can't take the address of a bit, so operator [] can't return a reference.

单击此处查找有关代理的集装箱更多信息（后半段是关于布尔向量）

Click here for more info on proxied containers (The last half is about vector of bool)

此外，许多STL实现了有用的调试位不在这帮助您捕捉虫子标准的一部分，但真正拖累业绩下降。你要确保那些在你构建优化禁用。

In addition many STL implementations have helpful debugging bits that are not part of the standard which help you catch bugs, but really drag performance down. You'll want to make sure those are disabled in your optimized build.

一旦你打开优化，设置是否正确（即，没有STL调试开启），并在这两个回路实际测试同样的事情，你会看到几乎没有区别。

Once you turn on the optimizer, have the right settings (i.e. no STL debugging turned on), and are actually testing the same thing in both loops, you will see almost no difference.

我必须让你的循环大得多来测试我的机器上，但这里有两个版本你在我的机器上的布尔环的载体，呈现出优化的标志对STL code的影响

I had to make your loop much larger to test on my machine, but here's two builds of your vector of bool loop on my machine, showing the impact of optimizer flags on STL code

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

这篇关于C ++矢量VS阵列（时间）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！