代码之家 › 专栏 › 技术社区 › Martin Ba

选择set<int>vs.vector<bool>vs.vector<boolean>to use as a bitmap(bitset/bit array)

performance c++

Martin Ba · 技术社区 · 15 年前

给定一系列索引(标识符),我希望将每个索引映射到一个布尔值,即:

// interface pseudocode
interface bitmap {
  bool identifier_is_set(unsigned int id_idx) const;
  void set_identifier(unsigned int id_idx, bool val) const;
};

因此,我可以为每个ID(索引)进行设置和查询(如果设置了或没有设置),您希望使用什么来实现这一点?

我认为这被称为位数组、位图或位集,如果我错了,请纠正我。

假设最大标识符是预先确定的,并且不大于1e6(1米),可能要小得多(10公里-100公里)。 (这意味着sizeof(int)*maximum_id_idx使用的大小很容易装入内存。)

目前为止我看到的可能的解决方案:

std::set<size_t> -必要时添加或删除此集合中的标识符。这将允许任意大的标识符,只要我们有一个稀疏的位图。
std::vector<bool> -大小调整到适当的最大值,为每个ID_IDX存储“真”或“假”。
std::vector<char> -同样的事情,但不受奇怪的折磨 STD::矢量& BoOL & GT; 问题。使用的内存比 vector<int> .
std::vector<int> -使用 int 作为布尔标志有一个使用机器自然字大小的容器。(不知道这会不会有什么不同。)

请回答您喜欢哪种类型的容器以及为什么,考虑到上面提到的最大ID限制,尤其是考虑到性能的方面查询位图(插入性能无关紧要)。

注:接口使用 vector VS set 没关系,因为无论如何它都会隐藏在包装类的后面。

编辑:STD:STD::BITSET将整个数组大小并入对象,即SsieOf(STD::BITSET & lt;1M>)将是大约1/8兆字节的大小,这使得一个巨大的单个对象,并使你不能再放入栈中的东西(WHIC)h可能相关也可能不相关)。

6 回复 | 直到 15 年前

MSN 15 年前

在不知道运行此代码的平台和访问模式的情况下,很难说 vector<bool> 会比 vector<char> (或 vector<int> )甚至 set<int> 或 unordered_set<int> .

例如,如果您有一个非常稀疏的数组,则对 矢量<int> 只包含索引集的方法可能是最好的答案。( See Mike Abrash's article on optimizing Pixomatic for x86. )

另一方面,您可能有一些稀疏的数组。有点稀疏,我的意思是集合元素的数量远远大于l1或l2。在这种情况下,更多的低级细节开始发挥作用,以及您的实际访问模式。

例如,在某些平台上,可变比特移位的成本非常昂贵。因此,如果您查询的是一组随机的标识符,那么执行此操作的频率越高,则 矢量<char> 或 矢量<int> 成为一个比 bitset<...> 或 矢量<bool> . (后两个使用位移到查找位。)另一方面,如果您要按顺序迭代稀疏位向量,只需要设置位,则可以优化该迭代,以消除可变移位的开销。

此时,您可能还想知道稀疏标识符实际上是如何分布的。如果它们是成堆的,您需要知道最佳内存读取大小和每次读取一个字符之间的权衡。这将决定更频繁地访问缓存是否会抵消非本机大小数据中的读取。

如果标识符是分散的,则可以通过使用哈希集获得显著的胜利。( 无序\设置<int> )而不是位向量。不过,这取决于负载。

Moo-Juice 15 年前

您签出了boost::dynamic\u位集了吗?

http://www.boost.org/doc/libs/1_36_0/libs/dynamic_bitset/dynamic_bitset.html

Steve M 15 年前

假设最大标识符是预先确定的,且不大于1e6(1m)

使用A std::bitset 如果有硬限制:

std::bitset<1000000> bits;
bits.set(1000);

CashCow 15 年前

如果按性能来说,你是指最快查找的那个STD::BITSET可能是足够快的,因为它的查找是固定时间的。将所有位设置为零有一个初始开销。矢量<int>的速度可能会非常快,并且设置比特的开销会更大,因为在32位系统中,比特的数量是32倍。

vector<bool>在其实现中与bitset类似,并且具有在需要时可调整大小的优势,尽管通常我会避免vector,如果需要调整大小,请使用boost的动态位集。

STD:SET将是O(log n)在查找和插入/删除中,尽管它是最可扩展的内存使用,如果集合不是特别满,则占用更少。STD::设置在范围内不受限制。

如果数据比较稀疏,有些形式的哈希也是一个选项,通常是O(1)设置和查找,尽管冲突处理可能会有一些开销。

valdo 15 年前

最快的似乎是使用位掩码。你应该构建一个 std::vector<int> ,并使其大小足够(n除以sizeof(int)*8,向上取整)。

这似乎比 std::vector<bool> (或类似)对于大型数据集。因为实际使用的内存要少得多,所以缓存利用率更好

Nim 15 年前

你可以一直拥有 std::vector<std::bitset<sizeof(size_t)> > ,那么您的查找是简单的计算(虽然模运算相对较慢),但您有这样的优势,即能够增长…我敢说,从空间上看,上述可能也是最理想的…