使用布尔值向量是否比动态位集慢？
我刚刚听说了 boost 的动态位集，我想知道这是否值得。我可以只使用布尔值向量吗？
问问题
15676 次
4 回答
43
这里很大程度上取决于您使用的布尔值的数量。
bitset 和vector<bool>通常都使用打包表示，其中布尔值仅存储为单个位。
一方面，这会以位操作的形式施加一些开销来访问单个值。
另一方面，这也意味着您的更多布尔值将适合您的缓存。
如果您使用大量布尔值（例如，实现 Eratosthenes 的筛子），在缓存中安装更多的布尔值几乎总是会获得净收益。内存使用的减少将比位操作损失更多。
大多数反对的论点std::vector<bool>都回到了它不是标准容器的事实（即，它不符合容器的要求）。IMO，这主要是一个期望问题——因为它说，许多人期望它是一个容器（其他类型的向量是），并且他们经常对不是容器vector的事实做出负面反应。vector<bool>
如果您以确实需要将其作为容器的方式使用向量，那么您可能想要使用其他组合——deque<bool>或者vector<char>可以正常工作。不过，在你这样做之前要三思——有很多（糟糕的，IMO）建议vector<bool>通常应该避免，很少或根本没有解释为什么应该避免它，或者在什么情况下它会对你产生真正的影响.
是的，在某些情况下，其他方法会更好。如果您处于其中一种情况，使用其他东西显然是一个好主意。但是，请确保您确实首先处于其中一种情况。任何告诉你（例如）“Herb 说你应该使用vector<char>”而没有对所涉及的权衡做出大量解释的人都不应该被信任。
让我们举一个真实的例子。既然评论中提到了，让我们考虑一下埃拉托色尼筛法：
#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";
}
我们使用了一个足够大的数组，我们可以预期它的很大一部分会占用主内存。为了确保在一次调用和另一次调用之间唯一改变的是使用vector<char>vs. ，我也有点痛苦vector<bool>。以下是一些结果。首先使用 VC++ 2015：
ignore: 34568730
Time using bool: 2623
Time using char: 3108
...然后是使用 g++ 5.1 的时间：
ignore: 34568730
Time using bool: 2359
Time using char: 3116
显然，vector<bool>在这两种情况下都获胜——使用 VC++ 大约 15%，使用 gcc 超过 30%。另请注意，在这种情况下，我选择了vector<char>在非常有利的光线下显示的尺寸。例如，如果我number从减少100000000到10000000，则时间差会变得更大：
ignore: 3987474
Time using bool: 72
Time using char: 249
虽然我没有做很多工作来确认，但我猜在这种情况下，使用的版本vector<bool>节省了足够的空间，使数组完全适合缓存，而vector<char>大到足以溢出缓存，并涉及大量的主存访问。
于 2013-05-24T15:46:43.680 回答
14
您通常应该避免std::vector<bool>，因为它不是标准容器。它是一个打包版本，因此它打破了通常由vector. 一个有效的替代方法是使用std::vector<char>Herb Sutter 推荐的方法。
您可以在他的GotW 中阅读有关该主题的更多信息。
更新：
正如已经指出的那样，vector<bool>可以使用效果很好，因为打包表示可以提高大型数据集的局部性。根据情况，它很可能是最快的选择。但是，默认情况下我仍然不推荐它，因为它打破了许多承诺，std::vector并且打包是速度/内存的权衡，这可能对速度和内存都有好处。
如果您选择使用它，我会在针对vector<char>您的应用程序进行测量后这样做。即便如此，我还是建议使用 atypedef通过一个名称来引用它，该名称似乎无法做出它不具备的保证。
于 2013-05-24T15:32:33.790 回答
1
似乎动态位集的大小无法更改：“dynamic_bitset 类与 std::bitset 类几乎相同。不同之处在于 dynamic_bitset 的大小（位数）是在运行时指定的dynamic_bitset 对象的构造，而 std::bitset 的大小是在编译时通过整数模板参数指定的。” （来自http://www.boost.org/doc/libs/1_36_0/libs/dynamic_bitset/dynamic_bitset.html）因此，它应该稍微快一些，因为它的开销会比向量略少，但你失去了能力插入元素。
于 2013-05-24T15:37:11.090 回答
0
更新：我刚刚意识到 OP 是在询问vector<bool>vs bitset，而我的回答没有回答这个问题，但我认为我应该离开它，如果你搜索c++ vector bool slow，你最终会到这里。
vector<bool>非常慢。至少在我的 Arch Linux 系统上（您可能可以获得更好的实现或其他东西......但我真的很惊讶）。如果有人对为什么这么慢有任何建议，我会全力以赴！（对不起，开头很生硬，这是更专业的部分。）
我编写了 SOE 的两个实现，“接近金属”的 C 实现快了 10 倍。sievec.c是 C 实现，sievestl.cpp是 C++ 实现。我刚刚编译了make（仅隐式规则，没有 makefile）：结果是C 版本为1.4 秒， C++/STL 版本为12 秒：
sievecmp % make -B sievec && time ./sievec 27
cc sievec.c -o sievec
aa 1056282
./sievec 27 1.44s user 0.01s system 100% cpu 1.455 total
和
sievecmp % make -B sievestl && time ./sievestl 27
g++ sievestl.cpp -o sievestl
1056282./sievestl 27 12.12s user 0.01s system 100% cpu 12.114 total
sievec.c如下：
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long prime_t;
typedef unsigned long word_t;
#define LOG_WORD_SIZE 6
#define INDEX(i) ((i)>>(LOG_WORD_SIZE))
#define MASK(i) ((word_t)(1) << ((i)&(((word_t)(1)<<LOG_WORD_SIZE)-1)))
#define GET(p,i) (p[INDEX(i)]&MASK(i))
#define SET(p,i) (p[INDEX(i)]|=MASK(i))
#define RESET(p,i) (p[INDEX(i)]&=~MASK(i))
#define p2i(p) ((p)>>1) // (((p-2)>>1))
#define i2p(i) (((i)<<1)+1) // ((i)*2+3)
unsigned long find_next_zero(unsigned long from,
unsigned long *v,
size_t N){
size_t i;
for (i = from+1; i < N; i++) {
if(GET(v,i)==0) return i;
}
return -1;
}
int main(int argc, char *argv[])
{
size_t N = atoi(argv[1]);
N = 1lu<<N;
// printf("%u\n",N);
unsigned long *v = malloc(N/8);
for(size_t i = 0; i < N/64; i++) v[i]=0;
unsigned long p = 3;
unsigned long pp = p2i(p * p);
while( pp <= N){
for(unsigned long q = pp; q < N; q += p ){
SET(v,q);
}
p = p2i(p);
p = find_next_zero(p,v,N);
p = i2p(p);
pp = p2i(p * p);
}
unsigned long sum = 0;
for(unsigned long i = 0; i+2 < N; i++)
if(GET(v,i)==0 && GET(v,i+1)==0) {
unsigned long p = i2p(i);
// cout << p << ", " << p+2 << endl;
sum++;
}
printf("aa %lu\n",sum);
// free(v);
return 0;
}
sievestl.cpp如下：
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
inline unsigned long i2p(unsigned long i){return (i<<1)+1; }
inline unsigned long p2i(unsigned long p){return (p>>1); }
inline unsigned long find_next_zero(unsigned long from, vector<bool> v){
size_t N = v.size();
for (size_t i = from+1; i < N; i++) {
if(v[i]==0) return i;
}
return -1;
}
int main(int argc, char *argv[])
{
stringstream ss;
ss << argv[1];
size_t N;
ss >> N;
N = 1lu<<N;
// cout << N << endl;
vector<bool> v(N);
unsigned long p = 3;
unsigned long pp = p2i(p * p);
while( pp <= N){
for(unsigned long q = pp; q < N; q += p ){
v[q] = 1;
}
p = p2i(p);
p = find_next_zero(p,v);
p = i2p(p);
pp = p2i(p * p);
}
unsigned sum = 0;
for(unsigned long i = 0; i+2 < N; i++)
if(v[i]==0 and v[i+1]==0) {
unsigned long p = i2p(i);
// cout << p << ", " << p+2 << endl;
sum++;
}
cout << sum;
return 0;
}
于 2016-02-09T21:51:26.920 回答