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

Question

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

例如我的数组是这样的。

{1, 0, 0, 1, 2, 1, 1, 1, 0, 2, 2, 0, 0, 0, 2,................................} p>

我们也可能会获取超过 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 个“真实”值放入每个数组元素。我怀疑在大多数处理器上这可能会提高内存访问效率。