存储约10000个变量的布尔类型信息的内存高效方法（动态分配）

Question

我需要存储大约10000个变量的布尔信息。一开始我想使用bool数组arr[10000]，但它占用了40000字节。但我需要以内存有效的方式存储这些信息。也许可以使用位运算？另外，我还需要全局存储并动态分配内存。你能帮我解决这个问题吗？

- Aragon

---

4000字节可以存储10000个布尔值，平均每个字节可存储2.5个布尔值。我原本期望的是1或8个布尔值。请问您使用的编译器和架构是什么？ - Coffee on Mars

@DenisErmolin 噢，抱歉，是的，bool 的大小为 1 字节。 - Jeegar Patel

为什么这会成为一个问题？在现代计算机上，40k根本不算什么。你使用的平台有特别的限制吗？ - Jens Gustedt

@DenisErmolin 在 C 语言中你不能分配/释放 1 位存储空间.. 搜索一下谷歌，你会得到更多信息。 - Jeegar Patel

@JensGustedt 是的，我正在处理内存受限平台。 - Aragon

Answer 1

您可以这样做：

vals = new char[(len+7)/8];
// To access
vals[i/8] & 1 << (i % 8)
// To set
vals[i/8] |= 1 << (i % 8);
// To clear
vals[i/8] &= ~(char)(1 << (i % 8));

为了实现最快速度，您应该使用与字大小相同的块。因此，在32位计算机上：

vals = new uint32_t[(len+31)/32];
// To access
vals[i/32] & 1 << (i % 32)
// To set
vals[i/32] |= 1 << (i % 32);
// To clear
vals[i/32] &= ~(uint32_t)(1 << (i % 32));

- CrazyCasta

---

OP 问到了 内存效率，使用64位块处理4000不会是最节省内存的方式；-) - Michael Krelin - hacker

如果我使用16位整数，那么语句应该是vals = new uint32_t[(len+15)/16]，对吗？ - Aragon

基本上，只需要使用uint16_t而不是uint32_t。 - CrazyCasta

在32位机器上，4000不会浪费空间。在64位机器上（即使用64位整数），除了需要的500字节外，还会浪费4个字节。可能不会有太大的差别，但我确实改变了我的语言:P - CrazyCasta

@CrazyCasta 你能否解释一下为什么在最后一行进行 uint32_t 类型转换（以清除）？ - Aragon

Answer 2

在C++中，您可以选择使用std::bitset<10000>来存储具有固定大小的单个位，或者使用std::vector<bool>如果需要动态更改大小。这两种方法都将每个值使用一个位。

没有必要手动进行位操作。

- Bo Persson

---

抱歉，在我写回答之前，我忽视了你也推荐使用std :: vector <bool>的部分。非常好的答案，实际上没有必要手动进行任何位操作！ - b.buchhold

Answer 3

显然，最有效的方法之一是将一个值存储为一个位，这将节省8倍的内存。

- Michael Krelin - hacker

---

我应该使用什么？我认为16位整数会很好吧？ - Aragon

随你喜欢。16位整数可以。 - Michael Krelin - hacker

8位或16位是最节省内存的方式，10000可以被8和16整除，如果使用32位，则会浪费16位。 - dev

Answer 4

10000是一个非常小的数字，当前计算机可用几GB的内存。如果您为每个布尔变量使用“int”类型，则仅占用40kB，这很小。首先将其设置为int arr[N]，然后在优化之前进行测试和测量性能。

从每个布尔变量的int转换为位压缩格式将使您使用更少的内存，但由于必须从压缩格式中打包和解包数据，因此所有操作都会变慢。您可以节省内存，但这是一种权衡，对我来说这听起来像是不必要的过早优化。

您还可以使用类似RLE压缩或BDDs的东西，它们更有效率，但实现起来更复杂，并且需要不同的运行时/内存权衡。

- Giovanni Funchal

Answer 5

我会按照下面所示的方式创建一个位域数组。正好是10000... 对于动态分配，只需将BoolBytes设置为指针，使用malloc函数即可。

typedef struct
    {
    unsigned b0     :1;
    unsigned b1     :1;
    unsigned b2     :1;
    unsigned b3     :1;
    unsigned b4     :1;
    unsigned b5     :1;
    unsigned b6     :1;
    unsigned b7     :1;
    }BitField;

BitField BoolBytes[1250]; // The number of bools is OVER NINE-THOUSAAAAAAAND!

另一个“效率”问题是询问 8 倍较低的内存是否比执行 10000 个布尔值内存地址计算所需的时间更好。这不算太大的开销，但比布尔数组稍微慢一些。

- Jeremy

Answer 6

使用std::vector<bool>应该是最简单的方法。您可以使用众所周知的向量接口（它带有动态分配，例如通过使用push_back添加项目），而我所知道的所有stl实现（我不确定是否也需要定义）都使用模板特化来实现布尔向量，并将其实现为每个值1位。

请注意，动态重新分配（您不必担心它，这全部由向量类完成）将允许插入恒定摊销时间，但可能会有一些内存开销（某些比特数的一小部分），以允许此操作。特别是，每当需要时，调整大小将通过当前长度的一小部分扩展/缩小分配的内存。

虽然这不是在每次存储信息时所需的最小内存，但我仍然认为这是一种内存高效的方式。

- b.buchhold