我有一个数组，其中索引兼作'项集合的标识符'，数组的内容是组号。群号在0..N，其中N <<length_of_the_array。因此，每个条目都将被复制大量次。目前，我必须使用2字节来表示组号(可以> 1000，但<6500)，由于重复的性质，最终会消耗大量内存。
是否有方法来空间优化这个数组，因为完整的数组可以进入多个mb的大小。感谢任何有关优化算法/技术的指导。仅供参考:我使用的编程语言是cpp。
您还希望对任意元素进行有效的随机访问吗?或者您正在考虑对index->group映射进行空间高效的序列化吗?
如果你仍然想要有效的随机访问，单个数组查找是不错的。最坏的情况是一个缓存丢失(实际上，最坏的情况是一个页面错误，或者更可能是TLB丢失，但如果只有几个MB，这是不太可能的)。
一个经过排序和运行长度编码的列表可以进行二进制搜索(通过搜索重复计数的前缀和数组)，但这只有在您可以偶尔对列表进行排序以保持重复项在一起时才有效。
如果副本不能至少在某种程度上分组在一起，那么你就不能做很多事情来允许随机访问。
打包的12位条目可能不值得麻烦，除非这足以显著减少缓存丢失。一对乘法指令来生成正确的地址，在16b负载上执行一个包含所需值的移位和掩码指令，与缓存丢失相比，开销并不大。对封装位域的写访问速度较慢，并且不是原子性的，因此这是一个严重的缺点。让编译器使用结构体打包位域可能是特定于编译器的。