使用布尔值的向量比动态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 
使用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 says vector, many people expect it to be a container (other types of vectors are), and they often react negatively to the fact that vector<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> or vector<char> can work fine. Think before you do that though -- there's a lot of (lousy, IMO) advice that vector<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 show vector<char> in quite favorable light. If, for example, I reduce number from 100000000 to 10000000, 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 the vector<char> is large enough to overflow the cache, and involve a great deal of main memory access.

                        
这篇关于使用布尔值的向量比动态bitset慢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！