我注意到,在运行以下代码时,向量比布尔数组慢得多。
int main()
{
int count = 0;
int n = 1500000;
// slower with c++ vector<bool>
/*vector<bool> isPrime;
isPrime.reserve(n);
isPrime.assign(n, true);
*/
// faster with bool array
bool* isPrime = new bool[n];
for (int i = 0; i < n; ++i)
isPrime[i] = true;
for (int i = 2; i< n; ++i) {
if (isPrime[i])
count++;
for (int j =2; i*j < n; ++j )
isPrime[i*j] = false;
}
cout << count << endl;
return 0;
}
有什么方法可以让vector<bool>
变得更快吗?顺便说一句,std::vector::push_back
和std::vector::emplace_back
都比std::vector::assign
慢。
发布于 2016-04-29 15:54:06
vector<bool>
可以具有模板专门化,并且可以使用位数组来实现以节省空间。提取并保存位并将其从bool
转换为bool
可能会导致您观察到的性能下降。如果你使用std::vector::push_back
,你正在调整向量的大小,这将导致更差的性能。下一个性能杀手可能是assign
(最糟糕的复杂性:第一个参数的线性),而不是使用operator []
(复杂性:常量)。
另一方面,保证bool []
是bool
的数组。
你应该调整到n
而不是n-1
,以避免未定义的行为。
https://stackoverflow.com/questions/36932684
复制相似问题