使用布尔值的向量比动态bitset慢? [英] Is using a vector of boolean values slower than a dynamic bitset?
问题描述
使用的布尔值向量比动态位集慢?
我刚刚听说过boost的动态bitset,我想知道是值
麻烦。我可以只使用布尔值的向量吗?
这里的很大一部分取决于你使用的布尔值。
bitset和向量< bool>
通常使用压缩表示,其中布尔值只存储为一个
一方面,以位操作的形式施加一些开销来访问单个值。
另一方面,这也意味着更多的布尔值将适合你的缓存。
如果你使用了很多布尔值(例如,实现适合更多的它们在缓存中的几乎总是结束净增益。
std :: vector< bool>的大多数参数。
回到它不是一个标准容器(即,它不满足容器的要求)的事实。 IMO,这主要是一个期望的问题 - 因为它说矢量
,许多人期望它是一个容器(其他类型的矢量),他们经常反应向量< bool>
不是容器的事实。
如果你使用向量一种真正需要它作为容器的方法,那么你可能想使用一些其他组合 - deque< bool>
或 vector< char> ;
可以正常工作。 之前,你应该尽量避免 - 有很多(糟糕的,IMO)建议,矢量< bool>
很少或没有解释为什么它应该被避免,或在什么情况下,它使你真正的区别。
是的,有些情况下,其他的东西会更好。如果你在这些情况之一,使用别的东西显然是一个好主意。但是,确保你真的在这些情况之一。任何人告诉你(例如)Herb说你应该使用向量< char>
,而不需要关于所涉及的权衡的很多解释。
让我们举一个真实的例子。因为在评论中提到,让我们考虑筛选Eratosthenes:
#include< vector>
#include< iostream>
#include< iterator>
#include< chrono>
unsigned long primes = 0;
template< class bool_t>
unsigned long sieve(unsigned max){
std :: vector< bool_t>筛(max,false);
sieve [0] = sieve [1] = true;
for(int i = 2; i if(!sieve [i]){
++ primes;
for(int temp = 2 * i; temp sieve [temp] = true;
}
}
return primes;
}
//警告:自动返回类型将失败,旧的编译器
//很好用g ++ 5.1和VC ++ 2015。
//
template< class F>
auto timer(F f,int max){
auto start = std :: chrono :: high_resolution_clock :: now();
primes + = f(max);
auto stop = std :: chrono :: high_resolution_clock :: now();
return stop - start;
}
int main(){
using namespace std :: chrono;
无符号数= 100000000;
auto using_bool = timer(sieve< bool>,number);
auto using_char = timer(sieve< char>,number);
std :: cout<< ignore:< primes<< \\\
;
std :: cout<< Time using bool:<< duration_cast< milliseconds>(using_bool).count()< \\\
;
std :: cout<< Time using char:<< duration_cast< milliseconds>(using_char).count()< \\\
;
}
我们使用了足够大的数组,它占用主内存。我也有点痛苦,以确保在一个调用与另一个调用之间改变的只是向量< char>
与向量< bool>
。这里有一些结果。首先使用VC ++ 2015:
忽略:34568730
使用bool的时间:2623
使用char:3108的时间
...时间使用g ++ 5.1:
忽略:34568730
$ p $显然,在这两种情况下,
使用bool的时间:2359
使用char的时间:3116
向量< bool>
胜过 - 与VC ++约15%,超过30%用gcc。还要注意,在这种情况下,我选择的大小显示向量< char>
在相当有利的光。例如,如果我将数字
从100000000
减少到10000000
,时间差异变得更大:忽略:3987474
:72
使用char的时间:249
虽然我没有做很多工作确认,我猜想在这种情况下,使用
向量< bool>
的版本节省了足够的空间,数组适合完全在缓存中,而vector< char>
足够大以溢出缓存,并涉及大量的主内存访问。Is using a vector of boolean values slower than a dynamic bitset?
I just heard about boost's dynamic bitset, and I was wondering is it worth the trouble. Can I just use vector of boolean values instead?
解决方案A great deal here depends on how many Boolean values you're working with.
Both bitset and
vector<bool>
normally use a packed representation where a Boolean is stored as only a single bit.On one hand, that imposes some overhead in the form of bit manipulation to access a single value.
On the other hand, that also means many more of your Booleans will fit in your cache.
If you're using a lot of Booleans (e.g., implementing a sieve of Eratosthenes) fitting more of them in the cache will almost always end up a net gain. The reduction in memory use will gain you a lot more than the bit manipulation loses.
Most of the arguments against
std::vector<bool>
come back to the fact that it is not a standard container (i.e., it does not meet the requirements for a container). IMO, this is mostly a question of expectations -- since it saysvector
, many people expect it to be a container (other types of vectors are), and they often react negatively to the fact thatvector<bool>
isn't a container.If you're using the vector in a way that really requires it to be a container, then you probably want to use some other combination -- either
deque<bool>
orvector<char>
can work fine. Think before you do that though -- there's a lot of (lousy, IMO) advice thatvector<bool>
should be avoided in general, with little or no explanation of why it should be avoided at all, or under what circumstances it makes a real difference to you.Yes, there are situations where something else will work better. If you're in one of those situations, using something else is clearly a good idea. But, be sure you're really in one of those situations first. Anybody who tells you (for example) that "Herb says you should use
vector<char>
" without a lot of explanation about the tradeoffs involved should not be trusted.Let's give a real example. Since it was mentioned in the comments, let's consider the Sieve of Eratosthenes:
#include <vector> #include <iostream> #include <iterator> #include <chrono> unsigned long primes = 0; template <class bool_t> unsigned long sieve(unsigned max) { std::vector<bool_t> sieve(max, false); sieve[0] = sieve[1] = true; for (int i = 2; i < max; i++) { if (!sieve[i]) { ++primes; for (int temp = 2 * i; temp < max; temp += i) sieve[temp] = true; } } return primes; } // Warning: auto return type will fail with older compilers // Fine with g++ 5.1 and VC++ 2015 though. // template <class F> auto timer(F f, int max) { auto start = std::chrono::high_resolution_clock::now(); primes += f(max); auto stop = std::chrono::high_resolution_clock::now(); return stop - start; } int main() { using namespace std::chrono; unsigned number = 100000000; auto using_bool = timer(sieve<bool>, number); auto using_char = timer(sieve<char>, number); std::cout << "ignore: " << primes << "\n"; std::cout << "Time using bool: " << duration_cast<milliseconds>(using_bool).count() << "\n"; std::cout << "Time using char: " << duration_cast<milliseconds>(using_char).count() << "\n"; }
We've used a large enough array that we can expect a large portion of it to occupy main memory. I've also gone to a little pain to ensure that the only thing that changes between one invocation and the other is the use of a
vector<char>
vs.vector<bool>
. Here are some results. First with VC++ 2015:ignore: 34568730 Time using bool: 2623 Time using char: 3108
...then the time using g++ 5.1:
ignore: 34568730 Time using bool: 2359 Time using char: 3116
Obviously, the
vector<bool>
wins in both cases--by around 15% with VC++, and over 30% with gcc. Also note that in this case, I've chosen the size to showvector<char>
in quite favorable light. If, for example, I reducenumber
from100000000
to10000000
, the time differential becomes much larger:ignore: 3987474 Time using bool: 72 Time using char: 249
Although I haven't done a lot of work to confirm, I'd guess that in this case, the version using
vector<bool>
is saving enough space that the array fits entirely in the cache, while thevector<char>
is large enough to overflow the cache, and involve a great deal of main memory access.这篇关于使用布尔值的向量比动态bitset慢?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!