有什么方法可以"分解"常用字段以节省空间？

Question

我有一个大型数组(>数百万)的Items,其中每个Item都有以下形式:

struct Item { void *a; size_t b; };

有一些不同的a字段 - 意味着有许多项具有相同的a字段.

我想"计算"这些信息以节省大约50%的内存使用量.

然而,麻烦的是这些Item具有重要的排序,并且可能随着时间而改变.因此,我不能只Item[]为每个不同的东西单独分开a,因为这将失去彼此相对于物品的相对排序.

另一方面,如果我将所有项目的订单存储在一个size_t index;字段中,那么我将因删除void *a;字段而减少任何内存节省.

那么有没有办法让我在这里实际节省内存,或者没有？

(注意:我已经可以想到例如使用unsigned charfor a来索引到一个小数组,但我想知道是否有更好的方法.那将要求我使用未对齐的内存或将每个Item[]分成两个,这不是'非常适合记忆位置,所以我更喜欢别的东西.)

Answer 1

(注意:我已经可以想到例如使用unsigned char来索引一个小数组,但我想知道是否有更好的方法.)

这种想法是正确的,但并不是那么简单,因为你会遇到一些令人讨厌的对齐/填充问题,这会使你的记忆收益减少.

此时,当您开始尝试划分像这样的结构的最后几个字节时,您可能希望使用位字段.

#define A_INDEX_BITS 3
struct Item { 
  size_t a_index : A_INDEX_BITS; 
  size_t b       : (sizeof(size_t) * CHAR_BIT) - A_INDEX_BITS; 
};

请注意,这将限制可用的位数b,但在现代平台上,其中sizeof(size_t)8位,从中剥离3-4位很少是个问题.

Answer 2

使用轻量级压缩方案的组合(请参阅此示例和一些引用)来表示a*值.例如,@ Frank的回答雇用了DICT,然后是NS.如果你有相同指针的长时间运行,你可以考虑RLE(运行长度编码).