我是一个有用的助手，可以为您进行翻译。
我有一个大型数组（>百万）的Item，每个Item的形式如下：
struct Item { void *a; size_t b; };
a字段——也就是说，有许多具有相同a字段的项。Item具有重要的排序，并且这可能会随时间改变。因此，我不能只是为每个不同的a创建一个单独的Item[]，因为这将失去相对于彼此的项目的顺序。size_t index;字段中存储所有项目的排序，则会失去从删除void *a;字段中获得的任何内存节省。unsigned char来索引到一个小数组中的a，但我想知道是否有更好的方法。那样需要我使用未对齐的内存或将每个Item[]拆分成两个，这对于内存局部性来说并不理想，因此我希望有其他更好的选择。）#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个位很少会成为问题。a*值。例如，@Frank的答案采用了DICT后跟NS。如果您有长时间运行相同的指针，可以在其上考虑使用RLE（Run-Length编码）。void* 的一半，因为 32 位的本质，你可以说已经是某种东西了。） - user541686// Assume that Payload has already been typedef'd. In my application,
// it would be a union of, eg., uint64_t, int64_t, double, pointer, etc.
// In your application, it would be b.
// Eight-byte payload version:
typedef struct Chunk8 { uint8_t kind[8]; Payload value[8]; }
// Four-byte payload version:
typedef struct Chunk4 { uint8_t kind[4]; Payload value[4]; }
向量是块的向量。为了使hack起作用，它们必须在8字节（或4字节）对齐的内存地址上分配，但我们已经假定对于Payload类型需要对齐。
这个hack的关键是如何表示指向单个值的指针，因为该值在内存中不是连续的。我们使用指向其“kind”成员的指针作为代理：
typedef uint8_t ValuePointer;
然后使用以下低开销但不是零开销的函数：
#define P_SIZE 8U
#define P_MASK P_SIZE - 1U
// Internal function used to get the low-order bits of a ValuePointer.
static inline size_t vpMask(ValuePointer vp) {
return (uintptr_t)vp & P_MASK;
}
// Getters / setters. This version returns the address so it can be
// used both as a getter and a setter
static inline uint8_t* kindOf(ValuePointer vp) { return vp; }
static inline Payload* valueOf(ValuePointer vp) {
return (Payload*)(vp + 1 + (vpMask(vp) + 1) * (P_SIZE - 1));
}
// Increment / Decrement
static inline ValuePointer inc(ValuePointer vp) {
return vpMask(++vp) ? vp : vp + P_SIZE * P_SIZE;
}
static inline ValuePointer dec(ValuePointer vp) {
return vpMask(vp--) ? vp - P_SIZE * P_SIZE : vp;
}
// Simple indexed access from a Chunk pointer
static inline ValuePointer eltk(Chunk* ch, size_t k) {
return &ch[k / P_SIZE].kind[k % P_SIZE];
}
// Increment a value pointer by an arbitrary (non-negative) amount
static inline ValuePointer inck(ValuePointer vp, size_t k) {
size_t off = vpMask(vp);
return eltk((Chunk*)(vp - off), k + off);
}
我省略了很多其他的技巧，但我相信你可以自行理解。
通过交错存储值的各个部分，一个很酷的事情是它具有中等良好的局部性。对于8字节版本，几乎一半的时间，对某种类型和值的随机访问仅会命中一个64字节缓存线；其余时间会命中两个连续的缓存线，结果是向前（或向后）遍历向量与遍历普通向量一样友好，只不过因为对象大小减半所以使用的缓存线更少。4字节版本甚至更加缓存友好。
a和b的位编码为一个整数（以使其更接近信息理论最优），但在你的情况下，你将它们分开以获得更快的性能。看起来我们在所有答案中涵盖了整个光谱。 :-) - user541686vector<A> vec_a;
vector<B> vec_b;
SomeType b_to_a_map;
Item Get(int index)
{
Item retval;
retval.a = vec_a[b_to_a_map[index]];
retval.b = vec_b[index];
return retval;
}
int a_index = b_to_a_map[index*2]*2 + b_to_a_map[index*2+1];
retval.a = vec_a[a_index];
a 的能力。Item，即有多少个不同的 (a,b) 对。毕竟，可能对于一个 a 有十亿个不同的 b，但对于其他的 a，只有一小撮，因此你想利用这一点。N 个不同的项目可供选择，则我们需要 n = ceil(log2(N)) 位来表示每个 Item。所以，我们真正想要的是一个包含 n 位整数数组，其中 n 在运行时计算出来。然后，一旦你获取了 n 位整数，你就可以在基于你所知道的每个 a 的 b 的数量的二分搜索中花费 log(n) 时间来确定它对应哪个 a。（这可能会影响一下性能，但取决于不同的 a 数量。）uint_vector 数据结构，其中每个元素的位数是可以动态指定的数量。然后，在随机访问时，你需要进行一些除法或模运算，并进行位移以提取所需整数。n 值的过程（C++ 模板在这里很有帮助！），然后使用各种 if (n == 33) { handle_case<33>(i); } 或 switch (n) { case 33: handle_case<33>(i); } 等分支进入它们，以便编译器将除数视为常量，并根据需要生成移位/加法/乘法，而不是除法。k * n 位中，然后使用更多的数学提取它们。这也可能会降低性能。
（或者，长话短说：C 和 C++ 真正需要一个高性能的 uint_vector 数据结构……）
CHAR_BIT取代 8。 - Angew is no longer proud of SOCHAR_BIT是指char变量的位数，因此它取决于平台。是的，在大多数现代硬件上，它几乎可以保证是8，但这并不是一般情况下都成立的。而且，CHAR_BIT比8更具有自我描述性。 - Angew is no longer proud of SO