arrays - 空间优化具有许多重复项的大型数组

Question

我有一个数组，其中索引兼作“项目集合的标识符”，并且数组的内容是组号。组数落入从 0..N 的有限范围内，其中 N << length_of_the_array。因此，每一个条目都会被重复很多次。目前我必须使用 2 个字节来表示组号（可以是 > 1000 但 < 6500 ），由于重复的性质最终会消耗大量内存。

有没有办法对这个数组进行空间优化，因为整个数组的大小可以达到多个 MB。感谢任何指向相关优化算法/技术的指针。仅供参考：我使用的编程语言是 cpp。

Answer 1

您还想要对任意元素进行有效的随机访问吗？或者您是否正在考虑索引-> 组映射的空间高效序列化？

如果您仍然想要有效的随机访问，那么单个数组查找也不错。最坏的情况是单个缓存未命中。真的，最坏的情况是页面错误，或者更可能是 TLB 未命中，但如果它只有几 MB，则不太可能）。

可以对已排序和运行长度编码的列表进行二进制搜索（通过搜索重复计数的前缀和数组），但这仅在您偶尔可以对列表进行排序以将重复项保持在一起时才有效。

如果重复项至少不能在某种程度上组合在一起，那么您可以做的就是允许随机访问。

打包的 12 位条目可能不值得麻烦，除非这足以显着减少缓存未命中。一对生成正确地址的乘法指令，以及包含所需值的 16b 加载的移位和屏蔽指令，与高速缓存未命中相比，开销并不大。对压缩位域的写访问速度较慢，而且不是原子的，所以这是一个严重的缺点。让编译器使用结构来打包位域可能是特定于编译器的。也许只使用 char 数组会是最好的。