c++ - 优化只有 3 个不同值的数组？如何设计？

Question

我正在尝试 C++ 中的资源不敏感功能。我正在实现一个包含 10000 条记录的数组，但任何记录都只有 3 个可能的值，即 0、1、2。所以我想知道如果我可以只保存每个实例的一个实例并进行逻辑管理，而不是为 10000 个实例存储所有 3 个实例的内存。不知道具体如何实现。

例如，我的数组将是这样的。

{1, 0, 0, 1, 2, 1, 1, 1, 0, 2, 2, 0, 0, 0, 2,......}

我们也可能会获得超过 10000 条记录

Answer 1

听起来您可以创建一个 2500 字节的数组，每个字节有 4 个值（每个值占用 2 位）。使用位移/屏蔽访问任何单个值。我怀疑这将比对值进行分组的方案更简单，并且会更加“类似数组”以进行访问。当然，很难确定，因为我们不知道您需要对这些值做什么。

您实际上可以将 5 个值放入每个字节（因为 3 ⁵是 243），因此您只需要一个大小为 2000 的字节数组......但访问代码会有些棘手。除非你真的需要它，否则我会抵制这种额外的复杂性。

此外，如果值相对稀疏——例如几乎所有内容都是 0，只有几个 1 和 2——那么您显然可以更有效地存储它。

编辑：好的，所以我很长时间没有做过任何 C++，但它会是这样的：

// Entirely untested. Please test thoroughly, and make sure you understand it
// before using it.
int get_value(unsigned index)
{
    // TODO: Argument validation
    unsigned raw_index = index / 4;
    unsigned index_within_byte = (index % 4) * 2;

    return (array[raw_index] >> index_within_byte) & 3;
}

void set_value(unsigned index, int value)
{
    // TODO: Argument validation
    unsigned raw_index = index / 4;
    unsigned index_within_byte = (index % 4) * 2;

    int mask = 0xff ^ (3 << index_within_byte);
    array[raw_index] = (array[raw_index] & mask) | (value << index_within_byte);
}

编辑：进一步考虑，您甚至可能想要创建一个由uint32_t或uint64_t代替字节的数组，并将 16 或 32 个“真实”值放入每个数组元素中。我怀疑在大多数处理器上可能会提高内存访问效率。

Answer 2

制作一个 的向量std::pair<int, int>，使得first该对中包含 0、1 或 2，并second包含该特定元素被看到的次数。

所以对于你的例子

{1, 0, 0, 1, 2, 1, 1, 1, 0, 2, 2, 0, 0, 0, 2,......}

你可以像这样存储它

{<1, 1>, <0, 2>, <1, 1>, <2, 1>, <1, 3>, <0, 1>, <2, 2>, <0, 3>, < 2，...>...}

只有当有很多连续重复并且不需要直接访问时，您才能看到它是好的。