3

我需要存储大约 10000 个变量的布尔信息。首先我想使用一个布尔数组 arr[10000] 但它需要 40000 个字节。但我需要以一种内存有效的方式存储这些信息。也许使用位操作？还有一件事我需要全局存储它并动态分配它。你能帮我解决这个问题吗？

4

6 回答 6

6

你可以这样做：

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));
于 2012-09-27T08:44:21.800 回答
3

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

没有太多需要手动进行位摆弄。

于 2012-09-27T09:49:01.973 回答
1

显然，最有效的方法是稍微存储一个值。Wich 将减少 8 倍的内存。

于 2012-09-27T08:42:04.970 回答
1

10000 是一个非常小的数字，目前的计算机有几 Gb 的可用内存。如果您对每个布尔变量使用“int”类型，则仅占 40kB，这是很小的。先做一个int arr[N]，然后在进一步优化之前测试和测量性能。

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

您还可以使用RLE 压缩或BDD 之类的东西，它们更高效，但实现起来更复杂，并且再次实现了不同的运行时/内存权衡。

于 2012-09-27T09:04:51.627 回答
0

我会制作一个位字段数组，如下所示。正好是 10000... 对于动态分配，只需将 BoolBytes 设为指针，使用 malloc 和 bob 即可。

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 个布尔的地址计算所增加的时间更好。开销不大，但这会比布尔数组稍慢。

于 2012-09-27T11:29:34.200 回答
0

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

请注意，动态重新分配（您不必关心它，这一切都由向量类完成）将允许插入的恒定摊销时间，但可能会有内存开销（实际位数的一小部分）到允许这个。特别是，在需要时，调整大小会将分配的内存扩展/缩小当前长度的一小部分。

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

于 2012-09-27T12:10:13.293 回答