当 95% 的情况下的值是 0 或 1 时，对一个非常大的数组的随机访问有什么优化吗？
Any optimization for random access on a very big array when the value in 95% of cases is either 0 or 1?
在一个非常大的数组上是否有任何可能的随机访问优化（我目前使用 uint8_t，我在问什么更好）
uint8_t MyArray[10000000];
当数组中任意位置的值为
- 0 或 1 所有情况的 95%，
- 2 在 4% 的案例中，
- 介于 3 和 255 之间
其他 1% 个案例？
那么，有什么比 uint8_t 数组更好的方法可以用于此吗？应该尽可能快地以随机顺序遍历整个数组，这对 RAM 带宽来说非常沉重，所以当有多个线程同时对不同的数组执行此操作时，目前整个 RAM 带宽很快就饱和了。
我问是因为拥有如此大的数组 (10 MB) 感觉非常低效，而实际上知道几乎所有值，除了 5%，都将是 0 或 1。所以当 95% 的数组中的所有值实际上只需要 1 位而不是 8 位，这将减少内存使用量几乎一个数量级。
感觉必须有一个内存效率更高的解决方案，可以大大减少为此所需的 RAM 带宽，因此随机访问也明显更快。
想到的一个简单的可能性是为常见情况保留每个值 2 位的压缩数组，并为每个值保留 4 个字节（原始元素索引为 24 位，实际值为 8 位，因此(idx << 8) | value)) 其他数组的排序数组。
当你查找一个值时，你首先在2bpp数组中查找（O（1））；如果你找到 0、1 或 2，它就是你想要的值；如果找到 3，则意味着您必须在辅助数组中查找它。在这里，您将执行二进制搜索以查找您感兴趣的 index 左移 8（O（log（n），n 较小，因为这应该是 1% ), 并从 4 字节的东西中提取值。
std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;
uint8_t lookup(unsigned idx) {
// extract the 2 bits of our interest from the main array
uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
// usual (likely) case: value between 0 and 2
if(v != 3) return v;
// bad case: lookup the index<<8 in the secondary array
// lower_bound finds the first >=, so we don't need to mask out the value
auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
// some coherency checks
if(ptr == sec_arr.end()) std::abort();
if((*ptr >> 8) != idx) std::abort();
#endif
// extract our 8-bit value from the 32 bit (index, value) thingie
return (*ptr) & 0xff;
}
void populate(uint8_t *source, size_t size) {
main_arr.clear(); sec_arr.clear();
// size the main storage (round up)
main_arr.resize((size+3)/4);
for(size_t idx = 0; idx < size; ++idx) {
uint8_t in = source[idx];
uint8_t &target = main_arr[idx>>2];
// if the input doesn't fit, cap to 3 and put in secondary storage
if(in >= 3) {
// top 24 bits: index; low 8 bit: value
sec_arr.push_back((idx << 8) | in);
in = 3;
}
// store in the target according to the position
target |= in << ((idx & 3)*2);
}
}
对于您提出的数组，第一个数组应占用 10000000 / 4 = 2500000 字节，第二个数组应占用 10000000 * 1% * 4 B = 400000 字节；因此 2900000 字节，即不到原始数组的三分之一，最常用的部分都放在内存中，这应该有利于缓存（甚至可以容纳 L3）。
如果您需要超过 24 位的寻址，则必须调整 "secondary storage"；扩展它的一种简单方法是使用一个 256 元素指针数组来切换索引的前 8 位并转发到如上所述的 24 位索引排序数组。
快速基准测试
#include <algorithm>
#include <vector>
#include <stdint.h>
#include <chrono>
#include <stdio.h>
#include <math.h>
using namespace std::chrono;
/// XorShift32 generator; extremely fast, 2^32-1 period, way better quality
/// than LCG but fail some test suites
struct XorShift32 {
/// This stuff allows to use this class wherever a library function
/// requires a UniformRandomBitGenerator (e.g. std::shuffle)
typedef uint32_t result_type;
static uint32_t min() { return 1; }
static uint32_t max() { return uint32_t(-1); }
/// PRNG state
uint32_t y;
/// Initializes with seed
XorShift32(uint32_t seed = 0) : y(seed) {
if(y == 0) y = 2463534242UL;
}
/// Returns a value in the range [1, 1<<32)
uint32_t operator()() {
y ^= (y<<13);
y ^= (y>>17);
y ^= (y<<15);
return y;
}
/// Returns a value in the range [0, limit); this conforms to the RandomFunc
/// requirements for std::random_shuffle
uint32_t operator()(uint32_t limit) {
return (*this)()%limit;
}
};
struct mean_variance {
double rmean = 0.;
double rvariance = 0.;
int count = 0;
void operator()(double x) {
++count;
double ormean = rmean;
rmean += (x-rmean)/count;
rvariance += (x-ormean)*(x-rmean);
}
double mean() const { return rmean; }
double variance() const { return rvariance/(count-1); }
double stddev() const { return std::sqrt(variance()); }
};
std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;
uint8_t lookup(unsigned idx) {
// extract the 2 bits of our interest from the main array
uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
// usual (likely) case: value between 0 and 2
if(v != 3) return v;
// bad case: lookup the index<<8 in the secondary array
// lower_bound finds the first >=, so we don't need to mask out the value
auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
// some coherency checks
if(ptr == sec_arr.end()) std::abort();
if((*ptr >> 8) != idx) std::abort();
#endif
// extract our 8-bit value from the 32 bit (index, value) thingie
return (*ptr) & 0xff;
}
void populate(uint8_t *source, size_t size) {
main_arr.clear(); sec_arr.clear();
// size the main storage (round up)
main_arr.resize((size+3)/4);
for(size_t idx = 0; idx < size; ++idx) {
uint8_t in = source[idx];
uint8_t &target = main_arr[idx>>2];
// if the input doesn't fit, cap to 3 and put in secondary storage
if(in >= 3) {
// top 24 bits: index; low 8 bit: value
sec_arr.push_back((idx << 8) | in);
in = 3;
}
// store in the target according to the position
target |= in << ((idx & 3)*2);
}
}
volatile unsigned out;
int main() {
XorShift32 xs;
std::vector<uint8_t> vec;
int size = 10000000;
for(int i = 0; i<size; ++i) {
uint32_t v = xs();
if(v < 1825361101) v = 0; // 42.5%
else if(v < 4080218931) v = 1; // 95.0%
else if(v < 4252017623) v = 2; // 99.0%
else {
while((v & 0xff) < 3) v = xs();
}
vec.push_back(v);
}
populate(vec.data(), vec.size());
mean_variance lk_t, arr_t;
for(int i = 0; i<50; ++i) {
{
unsigned o = 0;
auto beg = high_resolution_clock::now();
for(int i = 0; i < size; ++i) {
o += lookup(xs() % size);
}
out += o;
int dur = (high_resolution_clock::now()-beg)/microseconds(1);
fprintf(stderr, "lookup: %10d µs\n", dur);
lk_t(dur);
}
{
unsigned o = 0;
auto beg = high_resolution_clock::now();
for(int i = 0; i < size; ++i) {
o += vec[xs() % size];
}
out += o;
int dur = (high_resolution_clock::now()-beg)/microseconds(1);
fprintf(stderr, "array: %10d µs\n", dur);
arr_t(dur);
}
}
fprintf(stderr, " lookup | ± | array | ± | speedup\n");
printf("%7.0f | %4.0f | %7.0f | %4.0f | %0.2f\n",
lk_t.mean(), lk_t.stddev(),
arr_t.mean(), arr_t.stddev(),
arr_t.mean()/lk_t.mean());
return 0;
}
(code and data always updated in my Bitbucket)
上面的代码使用 运行dom 数据填充了一个 10M 元素数组，这些数据作为在其 post 中指定的 OP 分发，初始化我的数据结构，然后：
- 使用我的数据结构对 1000 万个元素执行 运行dom 查找
- 通过原始数组做同样的事情。
（请注意，在顺序查找的情况下，数组总是胜出很多，因为它是您可以执行的对缓存最友好的查找）
最后两个块重复50次并计时；最后，计算并打印每种查找类型的平均值和标准偏差，以及加速比 (lookup_mean/array_mean)。
我在 Ubuntu 16.04 上用 g++ 5.4.0（-O3 -static，加上一些警告）编译了上面的代码，在某些机器上 运行 它；其中大部分是 运行 Ubuntu 16.04，一些较旧的 Linux，一些较新的 Linux。我认为 OS 在这种情况下根本不相关。
CPU | cache | lookup (µs) | array (µs) | speedup (x)
Xeon E5-1650 v3 @ 3.50GHz | 15360 KB | 60011 ± 3667 | 29313 ± 2137 | 0.49
Xeon E5-2697 v3 @ 2.60GHz | 35840 KB | 66571 ± 7477 | 33197 ± 3619 | 0.50
Celeron G1610T @ 2.30GHz | 2048 KB | 172090 ± 629 | 162328 ± 326 | 0.94
Core i3-3220T @ 2.80GHz | 3072 KB | 111025 ± 5507 | 114415 ± 2528 | 1.03
Core i5-7200U @ 2.50GHz | 3072 KB | 92447 ± 1494 | 95249 ± 1134 | 1.03
Xeon X3430 @ 2.40GHz | 8192 KB | 111303 ± 936 | 127647 ± 1503 | 1.15
Core i7 920 @ 2.67GHz | 8192 KB | 123161 ± 35113 | 156068 ± 45355 | 1.27
Xeon X5650 @ 2.67GHz | 12288 KB | 106015 ± 5364 | 140335 ± 6739 | 1.32
Core i7 870 @ 2.93GHz | 8192 KB | 77986 ± 429 | 106040 ± 1043 | 1.36
Core i7-6700 @ 3.40GHz | 8192 KB | 47854 ± 573 | 66893 ± 1367 | 1.40
Core i3-4150 @ 3.50GHz | 3072 KB | 76162 ± 983 | 113265 ± 239 | 1.49
Xeon X5650 @ 2.67GHz | 12288 KB | 101384 ± 796 | 152720 ± 2440 | 1.51
Core i7-3770T @ 2.50GHz | 8192 KB | 69551 ± 1961 | 128929 ± 2631 | 1.85
结果...喜忧参半！
- 一般来说，这些机器中的大多数都有某种加速，或者至少它们是相提并论的。
- 数组真正胜过 "smart structure" 查找的两种情况是在具有大量缓存且不是特别繁忙的机器上：上面的 Xeon E5-1650（15 MB 缓存）是夜间构建机器，此刻很闲； Xeon E5-2697（35 MB 高速缓存）是一台用于高性能计算的机器，在闲置时也是如此。确实有道理，原始数组完全适合他们巨大的缓存，所以紧凑的数据结构只会增加复杂性。
- 在 "performance spectrum" 的对面 - 但是阵列速度稍快的地方是为我的 NAS 提供动力的不起眼的 Celeron；它的缓存太少了，数组和 "smart structure" 都放不下。缓存足够小的其他机器执行类似。
- Xeon X5650 必须谨慎使用 - 它们是非常繁忙的双路虚拟机服务器上的虚拟机；很可能是，虽然名义上它有相当数量的缓存，但在测试期间它被完全不相关的虚拟机抢占了好几次。
这更像是一个 "long comment" 而不是具体的答案
除非你的数据是众所周知的，否则我怀疑任何人都可以直接回答你的问题（而且我不知道有什么符合你的描述，但我不知道所有类型的一切各种用例的数据模式）。稀疏数据是高性能计算中的常见问题，但通常是 "we have a very large array, but only some values are non-zero".
对于像我认为你的模式这样不为人知的模式，没有人会直接知道哪个更好，这取决于细节：随机访问的随机性如何——系统是访问数据项的集群，还是它完全随机，就像来自统一的随机数生成器一样。 table 数据是完全随机的，还是先是 0 的序列，然后是 1 的序列，并散布着其他值？如果你有相当长的 0 和 1 序列，运行 长度编码会工作得很好，但如果你有 "checkerboard of 0/1" 就不会工作。此外，您必须保持 "starting points" 的 table，这样您就可以相当快地到达相关地点。
我很久以前就知道一些大数据库只是 RAM 中的一个大 table（在这个例子中是电话交换用户数据），其中一个问题是缓存和页面-table 处理器中的优化毫无用处。呼叫者与最近呼叫某人的呼叫者很少相同，因此没有任何类型的预加载数据，它只是纯粹的随机数据。 Big page-tables 是该类型访问的最佳优化。
在很多情况下，"speed and small size" 之间的妥协是您在软件工程中必须选择的事情之一 [在其他工程中，它不一定是那么多的妥协]。因此，"wasting memory for simpler code" 通常是首选。从这个意义上说，"simple" 解决方案很可能在速度方面更好，但是如果您将 "better" 用于 RAM，那么针对 table 的大小进行优化将为您提供足够的性能和尺寸有很好的改进。有很多不同的方法可以实现这一点——正如评论中所建议的，一个 2 位字段，其中存储了两个或三个最常见的值，然后是其他值的一些替代数据格式——一个 hash-table 将是我的第一种方法，但列表或二叉树也可能有效 - 同样，这取决于 "not 0, 1 or 2" 所在的模式。同样，这取决于 "scattered" 在 table 中的值如何 - 它们是成簇的还是更均匀分布的模式？
但问题是您仍在从 RAM 中读取数据。然后您将花费更多的代码来处理数据，包括一些代码来处理 "this is not a common value".
最常见的压缩算法的问题是它们基于解包序列，因此您不能随机访问它们。将您的大数据拆分成块，例如，一次 256 个条目，并将 256 个解压缩到 uint8_t 数组，获取您想要的数据，然后丢弃未压缩的数据的开销是极不可能的为您提供良好的性能 - 当然假设这很重要。
最后，您可能需要实施 comments/answers 中的一个或几个想法来进行测试，看看它是否有助于解决您的问题，或者内存总线是否仍然是主要限制因素.
看这个，你可以拆分你的数据，例如：
- 一个被索引并表示值 0 的位集（std::vector 在这里很有用）
- 一个被索引并表示值 1 的位集
- a std::vector 用于值 2，包含引用此值的索引
- 其他值的映射（或 std::vector>）
在这种情况下，所有值都出现在给定索引之前，因此您甚至可以删除其中一个位集并表示该值在其他位集中缺失。
这会为您节省一些内存，但会使最坏的情况变得更糟。
您还需要更多 CPU 功能来进行查找。
一定要测量！
我过去所做的是在位集的前面中使用哈希图。
与 Matteo 的答案相比，space 减半，但如果 "exception" 查找速度较慢（即有很多例外），则可能会更慢。
然而，通常 "cache is king"。
另一种选择是
- 检查结果是 0、1 还是 2
- 如果不进行定期查找
换句话说：
unsigned char lookup(int index) {
int code = (bmap[index>>2]>>(2*(index&3)))&3;
if (code != 3) return code;
return full_array[index];
}
其中 bmap 每个元素使用 2 位，值 3 表示 "other"。
这个结构更新起来很简单，多使用了 25% 的内存，但大部分只在 5% 的情况下被查找。当然，和往常一样，这是否是一个好主意取决于很多其他条件，所以唯一的答案是尝试实际使用。
除非您的数据存在模式，否则不太可能有任何合理的速度或大小优化，并且 - 假设您的目标是普通计算机 - 10 MB 无论如何都不是什么大问题。
你的问题有两个假设：
- 数据存储不当，因为您没有使用所有位
- 更好地存储它会使事情变得更快。
我认为这两个假设都是错误的。在大多数情况下，存储数据的适当方式是存储最自然的表示。在您的情况下，这就是您想要的：一个字节表示 0 到 255 之间的数字。任何其他表示形式都会更复杂，因此 - 所有其他条件相同 - 更慢且更容易出错。要偏离这个一般原则，你需要一个比 95% 的数据可能有六个 "wasted" 位更强大的理由。
对于你的第二个假设，当且仅当改变数组的大小导致缓存未命中率大大降低时，它才会成立。这是否会发生只能通过分析工作代码来明确确定，但我认为这不太可能产生实质性的差异。因为在任何一种情况下您都将随机访问数组，所以处理器将很难知道在任何一种情况下要缓存和保留哪些数据位。
您已经简洁地描述了您阵列的所有分布特征； 抛数组.
您可以使用产生与数组相同概率输出的随机方法轻松替换数组。
如果一致性很重要（为相同的随机索引生成相同的值），请考虑使用 bloom filter and/or hash map 来跟踪重复命中。但是，如果您的数组访问确实是随机的，则完全没有必要。
如果只执行读取操作，最好不要将值分配给单个索引，而是分配给索引区间。
例如：
[0, 15000] = 0
[15001, 15002] = 153
[15003, 26876] = 2
[25677, 31578] = 0
...
这可以用一个结构来完成。如果您喜欢 OO 方法，您可能还想定义一个与此类似的 class。
class Interval{
private:
uint32_t start; // First element of interval
uint32_t end; // Last element of interval
uint8_t value; // Assigned value
public:
Interval(uint32_t start, uint32_t end, uint8_t value);
bool isInInterval(uint32_t item); // Checks if item lies within interval
uint8_t getValue(); // Returns the assigned value
}
现在您只需要遍历一系列间隔并检查您的索引是否位于其中一个间隔内，这平均占用的内存要少得多，但会消耗更多 CPU 资源。
Interval intervals[INTERVAL_COUNT];
intervals[0] = Interval(0, 15000, 0);
intervals[1] = Interval(15001, 15002, 153);
intervals[2] = Interval(15003, 26876, 2);
intervals[3] = Interval(25677, 31578, 0);
...
uint8_t checkIntervals(uint32_t item)
for(int i=0; i<INTERVAL_COUNT-1; i++)
{
if(intervals[i].isInInterval(item) == true)
{
return intervals[i].getValue();
}
}
return DEFAULT_VALUE;
}
如果按大小降序对间隔进行排序，则会增加较早找到您要查找的项目的可能性，从而进一步减少平均内存和 CPU 资源使用。
您也可以删除所有大小为 1 的区间。将相应的值放入地图中，只有在区间中找不到您要查找的项目时才检查它们。这也应该会稍微提高平均性能。
就像 Mats 在他的评论回答中提到的那样，如果不知道具体你有什么样的数据（例如，有长0 的运行，依此类推），以及您的访问模式是什么样的（"random" 是指 "all over the place" 还是只是 "not strictly in completely linear fashion" 或 "every value exactly once, just randomized" 或...）。
也就是说，我想到了两种机制：
- 位数组；也就是说，如果你只有两个值，你可以简单地将你的数组压缩 8 倍；如果您有 4 个值（或“3 个值 + 其他所有值”），则可以压缩两倍。这可能不值得麻烦并且需要基准测试，特别是如果您有 真正 随机访问模式，它会逃避您的缓存，因此根本不会改变访问时间。
(index,value) 或 (value,index) tables。即，对于 1% 的情况有一个非常小的 table，对于 5% 的情况可能有一个 table（它只需要存储索引，因为所有索引都具有相同的值），以及一个大的压缩位最后两种情况的数组。 "table" 我的意思是允许相对快速查找的东西；即，可能是散列、二叉树等，具体取决于您可用的内容和您的实际需求。如果这些子table适合你的一级/二级缓存，你可能会走运。
我将添加到 @o11c 的回答中，因为他的措辞可能有点令人困惑。
如果我需要挤压最后一点和 CPU 循环，我会执行以下操作。
我们将从构建一个 平衡 二叉搜索树开始，它包含 5% "something else" 个案例。对于每次查找，您快速遍历树：您有 10000000 个元素：其中 5% 在树中：因此树数据结构包含 500000 个元素。在 O(log(n)) 时间内走这个，给你 19 次迭代。我不是这方面的专家，但我想那里有一些内存高效的实现。让我们猜猜：
- 平衡树，因此可以计算子树位置（索引不需要存储在树的节点中）。与堆（数据结构）存储在线性内存中的方式相同。
- 1 字节值（2 到 255）
- 索引3个字节（10000000占用23位，适合3个字节）
总计，4 个字节：500000*4 = 1953 kB。适合缓存！
对于所有其他情况（0 或 1），您可以使用位向量。请注意，您不能遗漏 5% 的其他随机访问情况：1.19 MB。
这两个的组合使用大约 3,099 MB。使用此技术，您将节省 3.08 倍的内存。
然而，这并没有击败 @Matteo Italia 的答案（使用 2.76 MB），很遗憾。有什么我们可以额外做的吗？最消耗内存的部分是树中索引的 3 个字节。如果我们可以将其降低到 2，我们将节省 488 kB，总内存使用量将是：2.622 MB，这会更小！
我们如何做到这一点？我们必须将索引减少到 2 个字节。同样，10000000 占用 23 位。我们需要能够丢弃 7 位。我们可以通过将 10000000 个元素的范围划分为 78125 个元素的 2^7（=128）个区域来简单地做到这一点。现在我们可以为每个区域构建一个平衡树，平均有 3906 个元素。选择正确的树是通过将目标索引除以 2^7（或移位 >> 7）来完成的。现在需要存储的索引可以由剩余的 16 位表示。请注意，需要存储的树的长度有一些开销，但这可以忽略不计。另请注意，这种拆分机制减少了遍历树所需的迭代次数，现在减少到 7 次迭代，因为我们丢弃了 7 位：只剩下 12 次迭代。
请注意，理论上您可以重复该过程以切断接下来的 8 位，但这需要您创建 2^15 棵平衡树，平均约有 305 个元素。这将产生 2.143 MB，只有 4 次迭代遍历树，与我们开始时的 19 次迭代相比，这是一个相当大的加速。
最后的结论是：这比 2 位向量策略稍微占用一点内存，但实现起来却很费劲。但是，如果它可以决定是否适合缓存，那么它可能值得一试。
如果数据和访问是均匀随机分布的，性能可能取决于有多少访问避免外层缓存未命中。优化它需要知道什么大小的数组可以可靠地容纳在缓存中。如果您的缓存足够大以容纳每五个单元一个字节，最简单的方法可能是让一个字节保存 0-2 范围内的五个以三为底的编码值（有 5 个值的 243 种组合，因此将适合一个字节），以及一个 10,000,000 字节的数组，只要 base-3 值表示“2”，就会查询该数组。
如果缓存不是那么大，但可以每 8 个单元格容纳一个字节，那么就不可能将一个字节值用于 select 来自八个基数的所有 6,561 种可能组合中的一个字节值- 3 个值，但由于将 0 或 1 更改为 2 的唯一影响是导致不必要的查找，因此正确性不需要支持所有 6,561 个。相反，可以关注 256 个最 "useful" 值。
特别是如果 0 比 1 更常见，反之亦然，一个好的方法可能是使用 217 个值来编码包含 5 个或更少 1 的 0 和 1 的组合，16 个值来编码 xxxx0000 到 xxxx1111， 16 编码 0000xxxx 到 1111xxxx，一个用于 xxxxxxxx。四个值将保留用于人们可能发现的任何其他用途。如果数据按照描述的那样随机分布，那么所有查询中的一小部分将命中仅包含零和一的字节（在所有八组中的大约 2/3 中，所有位都是零和一，大约 7/8那些将有六个或更少的 1 位）；那些没有的绝大多数将落在一个包含四个 x 的字节中，并且有 50% 的机会落在零或一上。因此，只有大约四分之一的查询需要大型数组查找。
如果数据是随机分布的，但缓存不够大，无法处理每八个元素一个字节，可以尝试使用这种方法，每个字节处理超过八个项目，但除非有强烈的偏见趋向于 0 或趋向于 1，随着每个字节处理的数字的增加，无需在大数组中进行查找即可处理的值的比例将缩小。
很久很久以前，我只记得...
在大学里，我们接到了一个加速光线追踪程序的任务，该程序必须通过算法从缓冲区数组中一遍又一遍地读取。一位朋友告诉我始终使用 4 字节的倍数的 RAM 读取。所以我将数组从 [x1,y1,z1,x2,y2,z2,...,xn,yn,zn] 的模式更改为 [x1,y1,z1,0,x2,y2,z2] 的模式,0,...,xn,yn,zn,0]。意味着我在每个 3D 坐标后添加一个空字段。经过一些性能测试：速度更快。
长话短说：从 RAM 的数组中读取 4 个字节的倍数，也可能从正确的起始位置读取，因此您读取了一个小簇，其中包含搜索索引，并从 [= 中的这个小簇读取搜索索引23=]。 （在你的情况下你不需要插入填充字段，但概念应该很清楚）
也许其他倍数也可能是较新系统的关键。
我不知道这是否适用于您的情况，所以如果它不起作用：抱歉。如果它有效，我会很高兴听到一些测试结果。
PS: 哦，如果有任何访问模式或附近的访问索引，您可以重用缓存的集群。
PPS: 应该是，倍数大概是16Bytes之类的吧，时间太久了，记不太清了。
我对C不是很熟悉，但是在C++中可以使用unsigned char来表示0-范围内的整数255.
与正常 int 相比（同样，我来自 Java 和 C++ world) 其中需要 4 byte（32 位），unsigned char 需要 1 byte（8 位）。
所以它可能会将数组的总大小减少 75%。
在一个非常大的数组上是否有任何可能的随机访问优化（我目前使用 uint8_t，我在问什么更好）
uint8_t MyArray[10000000];
当数组中任意位置的值为
- 0 或 1 所有情况的 95%，
- 2 在 4% 的案例中，
- 介于 3 和 255 之间 其他 1% 个案例？
那么，有什么比 uint8_t 数组更好的方法可以用于此吗？应该尽可能快地以随机顺序遍历整个数组，这对 RAM 带宽来说非常沉重，所以当有多个线程同时对不同的数组执行此操作时，目前整个 RAM 带宽很快就饱和了。
我问是因为拥有如此大的数组 (10 MB) 感觉非常低效，而实际上知道几乎所有值，除了 5%，都将是 0 或 1。所以当 95% 的数组中的所有值实际上只需要 1 位而不是 8 位，这将减少内存使用量几乎一个数量级。 感觉必须有一个内存效率更高的解决方案，可以大大减少为此所需的 RAM 带宽，因此随机访问也明显更快。
想到的一个简单的可能性是为常见情况保留每个值 2 位的压缩数组，并为每个值保留 4 个字节（原始元素索引为 24 位，实际值为 8 位，因此(idx << 8) | value)) 其他数组的排序数组。
当你查找一个值时，你首先在2bpp数组中查找（O（1））；如果你找到 0、1 或 2，它就是你想要的值；如果找到 3，则意味着您必须在辅助数组中查找它。在这里，您将执行二进制搜索以查找您感兴趣的 index 左移 8（O（log（n），n 较小，因为这应该是 1% ), 并从 4 字节的东西中提取值。
std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;
uint8_t lookup(unsigned idx) {
// extract the 2 bits of our interest from the main array
uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
// usual (likely) case: value between 0 and 2
if(v != 3) return v;
// bad case: lookup the index<<8 in the secondary array
// lower_bound finds the first >=, so we don't need to mask out the value
auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
// some coherency checks
if(ptr == sec_arr.end()) std::abort();
if((*ptr >> 8) != idx) std::abort();
#endif
// extract our 8-bit value from the 32 bit (index, value) thingie
return (*ptr) & 0xff;
}
void populate(uint8_t *source, size_t size) {
main_arr.clear(); sec_arr.clear();
// size the main storage (round up)
main_arr.resize((size+3)/4);
for(size_t idx = 0; idx < size; ++idx) {
uint8_t in = source[idx];
uint8_t &target = main_arr[idx>>2];
// if the input doesn't fit, cap to 3 and put in secondary storage
if(in >= 3) {
// top 24 bits: index; low 8 bit: value
sec_arr.push_back((idx << 8) | in);
in = 3;
}
// store in the target according to the position
target |= in << ((idx & 3)*2);
}
}
对于您提出的数组，第一个数组应占用 10000000 / 4 = 2500000 字节，第二个数组应占用 10000000 * 1% * 4 B = 400000 字节；因此 2900000 字节，即不到原始数组的三分之一，最常用的部分都放在内存中，这应该有利于缓存（甚至可以容纳 L3）。
如果您需要超过 24 位的寻址，则必须调整 "secondary storage"；扩展它的一种简单方法是使用一个 256 元素指针数组来切换索引的前 8 位并转发到如上所述的 24 位索引排序数组。
快速基准测试
#include <algorithm>
#include <vector>
#include <stdint.h>
#include <chrono>
#include <stdio.h>
#include <math.h>
using namespace std::chrono;
/// XorShift32 generator; extremely fast, 2^32-1 period, way better quality
/// than LCG but fail some test suites
struct XorShift32 {
/// This stuff allows to use this class wherever a library function
/// requires a UniformRandomBitGenerator (e.g. std::shuffle)
typedef uint32_t result_type;
static uint32_t min() { return 1; }
static uint32_t max() { return uint32_t(-1); }
/// PRNG state
uint32_t y;
/// Initializes with seed
XorShift32(uint32_t seed = 0) : y(seed) {
if(y == 0) y = 2463534242UL;
}
/// Returns a value in the range [1, 1<<32)
uint32_t operator()() {
y ^= (y<<13);
y ^= (y>>17);
y ^= (y<<15);
return y;
}
/// Returns a value in the range [0, limit); this conforms to the RandomFunc
/// requirements for std::random_shuffle
uint32_t operator()(uint32_t limit) {
return (*this)()%limit;
}
};
struct mean_variance {
double rmean = 0.;
double rvariance = 0.;
int count = 0;
void operator()(double x) {
++count;
double ormean = rmean;
rmean += (x-rmean)/count;
rvariance += (x-ormean)*(x-rmean);
}
double mean() const { return rmean; }
double variance() const { return rvariance/(count-1); }
double stddev() const { return std::sqrt(variance()); }
};
std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;
uint8_t lookup(unsigned idx) {
// extract the 2 bits of our interest from the main array
uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
// usual (likely) case: value between 0 and 2
if(v != 3) return v;
// bad case: lookup the index<<8 in the secondary array
// lower_bound finds the first >=, so we don't need to mask out the value
auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
// some coherency checks
if(ptr == sec_arr.end()) std::abort();
if((*ptr >> 8) != idx) std::abort();
#endif
// extract our 8-bit value from the 32 bit (index, value) thingie
return (*ptr) & 0xff;
}
void populate(uint8_t *source, size_t size) {
main_arr.clear(); sec_arr.clear();
// size the main storage (round up)
main_arr.resize((size+3)/4);
for(size_t idx = 0; idx < size; ++idx) {
uint8_t in = source[idx];
uint8_t &target = main_arr[idx>>2];
// if the input doesn't fit, cap to 3 and put in secondary storage
if(in >= 3) {
// top 24 bits: index; low 8 bit: value
sec_arr.push_back((idx << 8) | in);
in = 3;
}
// store in the target according to the position
target |= in << ((idx & 3)*2);
}
}
volatile unsigned out;
int main() {
XorShift32 xs;
std::vector<uint8_t> vec;
int size = 10000000;
for(int i = 0; i<size; ++i) {
uint32_t v = xs();
if(v < 1825361101) v = 0; // 42.5%
else if(v < 4080218931) v = 1; // 95.0%
else if(v < 4252017623) v = 2; // 99.0%
else {
while((v & 0xff) < 3) v = xs();
}
vec.push_back(v);
}
populate(vec.data(), vec.size());
mean_variance lk_t, arr_t;
for(int i = 0; i<50; ++i) {
{
unsigned o = 0;
auto beg = high_resolution_clock::now();
for(int i = 0; i < size; ++i) {
o += lookup(xs() % size);
}
out += o;
int dur = (high_resolution_clock::now()-beg)/microseconds(1);
fprintf(stderr, "lookup: %10d µs\n", dur);
lk_t(dur);
}
{
unsigned o = 0;
auto beg = high_resolution_clock::now();
for(int i = 0; i < size; ++i) {
o += vec[xs() % size];
}
out += o;
int dur = (high_resolution_clock::now()-beg)/microseconds(1);
fprintf(stderr, "array: %10d µs\n", dur);
arr_t(dur);
}
}
fprintf(stderr, " lookup | ± | array | ± | speedup\n");
printf("%7.0f | %4.0f | %7.0f | %4.0f | %0.2f\n",
lk_t.mean(), lk_t.stddev(),
arr_t.mean(), arr_t.stddev(),
arr_t.mean()/lk_t.mean());
return 0;
}
(code and data always updated in my Bitbucket)
上面的代码使用 运行dom 数据填充了一个 10M 元素数组，这些数据作为在其 post 中指定的 OP 分发，初始化我的数据结构，然后：
- 使用我的数据结构对 1000 万个元素执行 运行dom 查找
- 通过原始数组做同样的事情。
（请注意，在顺序查找的情况下，数组总是胜出很多，因为它是您可以执行的对缓存最友好的查找）
最后两个块重复50次并计时；最后，计算并打印每种查找类型的平均值和标准偏差，以及加速比 (lookup_mean/array_mean)。
我在 Ubuntu 16.04 上用 g++ 5.4.0（-O3 -static，加上一些警告）编译了上面的代码，在某些机器上 运行 它；其中大部分是 运行 Ubuntu 16.04，一些较旧的 Linux，一些较新的 Linux。我认为 OS 在这种情况下根本不相关。
CPU | cache | lookup (µs) | array (µs) | speedup (x)
Xeon E5-1650 v3 @ 3.50GHz | 15360 KB | 60011 ± 3667 | 29313 ± 2137 | 0.49
Xeon E5-2697 v3 @ 2.60GHz | 35840 KB | 66571 ± 7477 | 33197 ± 3619 | 0.50
Celeron G1610T @ 2.30GHz | 2048 KB | 172090 ± 629 | 162328 ± 326 | 0.94
Core i3-3220T @ 2.80GHz | 3072 KB | 111025 ± 5507 | 114415 ± 2528 | 1.03
Core i5-7200U @ 2.50GHz | 3072 KB | 92447 ± 1494 | 95249 ± 1134 | 1.03
Xeon X3430 @ 2.40GHz | 8192 KB | 111303 ± 936 | 127647 ± 1503 | 1.15
Core i7 920 @ 2.67GHz | 8192 KB | 123161 ± 35113 | 156068 ± 45355 | 1.27
Xeon X5650 @ 2.67GHz | 12288 KB | 106015 ± 5364 | 140335 ± 6739 | 1.32
Core i7 870 @ 2.93GHz | 8192 KB | 77986 ± 429 | 106040 ± 1043 | 1.36
Core i7-6700 @ 3.40GHz | 8192 KB | 47854 ± 573 | 66893 ± 1367 | 1.40
Core i3-4150 @ 3.50GHz | 3072 KB | 76162 ± 983 | 113265 ± 239 | 1.49
Xeon X5650 @ 2.67GHz | 12288 KB | 101384 ± 796 | 152720 ± 2440 | 1.51
Core i7-3770T @ 2.50GHz | 8192 KB | 69551 ± 1961 | 128929 ± 2631 | 1.85
结果...喜忧参半！
- 一般来说，这些机器中的大多数都有某种加速，或者至少它们是相提并论的。
- 数组真正胜过 "smart structure" 查找的两种情况是在具有大量缓存且不是特别繁忙的机器上：上面的 Xeon E5-1650（15 MB 缓存）是夜间构建机器，此刻很闲； Xeon E5-2697（35 MB 高速缓存）是一台用于高性能计算的机器，在闲置时也是如此。确实有道理，原始数组完全适合他们巨大的缓存，所以紧凑的数据结构只会增加复杂性。
- 在 "performance spectrum" 的对面 - 但是阵列速度稍快的地方是为我的 NAS 提供动力的不起眼的 Celeron；它的缓存太少了，数组和 "smart structure" 都放不下。缓存足够小的其他机器执行类似。
- Xeon X5650 必须谨慎使用 - 它们是非常繁忙的双路虚拟机服务器上的虚拟机；很可能是，虽然名义上它有相当数量的缓存，但在测试期间它被完全不相关的虚拟机抢占了好几次。
这更像是一个 "long comment" 而不是具体的答案
除非你的数据是众所周知的，否则我怀疑任何人都可以直接回答你的问题（而且我不知道有什么符合你的描述，但我不知道所有类型的一切各种用例的数据模式）。稀疏数据是高性能计算中的常见问题，但通常是 "we have a very large array, but only some values are non-zero".
对于像我认为你的模式这样不为人知的模式，没有人会直接知道哪个更好，这取决于细节：随机访问的随机性如何——系统是访问数据项的集群，还是它完全随机，就像来自统一的随机数生成器一样。 table 数据是完全随机的，还是先是 0 的序列，然后是 1 的序列，并散布着其他值？如果你有相当长的 0 和 1 序列，运行 长度编码会工作得很好，但如果你有 "checkerboard of 0/1" 就不会工作。此外，您必须保持 "starting points" 的 table，这样您就可以相当快地到达相关地点。
我很久以前就知道一些大数据库只是 RAM 中的一个大 table（在这个例子中是电话交换用户数据），其中一个问题是缓存和页面-table 处理器中的优化毫无用处。呼叫者与最近呼叫某人的呼叫者很少相同，因此没有任何类型的预加载数据，它只是纯粹的随机数据。 Big page-tables 是该类型访问的最佳优化。
在很多情况下，"speed and small size" 之间的妥协是您在软件工程中必须选择的事情之一 [在其他工程中，它不一定是那么多的妥协]。因此，"wasting memory for simpler code" 通常是首选。从这个意义上说，"simple" 解决方案很可能在速度方面更好，但是如果您将 "better" 用于 RAM，那么针对 table 的大小进行优化将为您提供足够的性能和尺寸有很好的改进。有很多不同的方法可以实现这一点——正如评论中所建议的，一个 2 位字段，其中存储了两个或三个最常见的值，然后是其他值的一些替代数据格式——一个 hash-table 将是我的第一种方法，但列表或二叉树也可能有效 - 同样，这取决于 "not 0, 1 or 2" 所在的模式。同样，这取决于 "scattered" 在 table 中的值如何 - 它们是成簇的还是更均匀分布的模式？
但问题是您仍在从 RAM 中读取数据。然后您将花费更多的代码来处理数据，包括一些代码来处理 "this is not a common value".
最常见的压缩算法的问题是它们基于解包序列，因此您不能随机访问它们。将您的大数据拆分成块，例如，一次 256 个条目，并将 256 个解压缩到 uint8_t 数组，获取您想要的数据，然后丢弃未压缩的数据的开销是极不可能的为您提供良好的性能 - 当然假设这很重要。
最后，您可能需要实施 comments/answers 中的一个或几个想法来进行测试，看看它是否有助于解决您的问题，或者内存总线是否仍然是主要限制因素.
看这个，你可以拆分你的数据，例如：
- 一个被索引并表示值 0 的位集（std::vector 在这里很有用）
- 一个被索引并表示值 1 的位集
- a std::vector 用于值 2，包含引用此值的索引
- 其他值的映射（或 std::vector>）
在这种情况下，所有值都出现在给定索引之前，因此您甚至可以删除其中一个位集并表示该值在其他位集中缺失。
这会为您节省一些内存，但会使最坏的情况变得更糟。 您还需要更多 CPU 功能来进行查找。
一定要测量！
我过去所做的是在位集的前面中使用哈希图。
与 Matteo 的答案相比，space 减半，但如果 "exception" 查找速度较慢（即有很多例外），则可能会更慢。
然而，通常 "cache is king"。
另一种选择是
- 检查结果是 0、1 还是 2
- 如果不进行定期查找
换句话说：
unsigned char lookup(int index) {
int code = (bmap[index>>2]>>(2*(index&3)))&3;
if (code != 3) return code;
return full_array[index];
}
其中 bmap 每个元素使用 2 位，值 3 表示 "other"。
这个结构更新起来很简单，多使用了 25% 的内存，但大部分只在 5% 的情况下被查找。当然，和往常一样，这是否是一个好主意取决于很多其他条件，所以唯一的答案是尝试实际使用。
除非您的数据存在模式，否则不太可能有任何合理的速度或大小优化，并且 - 假设您的目标是普通计算机 - 10 MB 无论如何都不是什么大问题。
你的问题有两个假设：
- 数据存储不当，因为您没有使用所有位
- 更好地存储它会使事情变得更快。
我认为这两个假设都是错误的。在大多数情况下，存储数据的适当方式是存储最自然的表示。在您的情况下，这就是您想要的：一个字节表示 0 到 255 之间的数字。任何其他表示形式都会更复杂，因此 - 所有其他条件相同 - 更慢且更容易出错。要偏离这个一般原则，你需要一个比 95% 的数据可能有六个 "wasted" 位更强大的理由。
对于你的第二个假设，当且仅当改变数组的大小导致缓存未命中率大大降低时，它才会成立。这是否会发生只能通过分析工作代码来明确确定，但我认为这不太可能产生实质性的差异。因为在任何一种情况下您都将随机访问数组，所以处理器将很难知道在任何一种情况下要缓存和保留哪些数据位。
您已经简洁地描述了您阵列的所有分布特征； 抛数组.
您可以使用产生与数组相同概率输出的随机方法轻松替换数组。
如果一致性很重要（为相同的随机索引生成相同的值），请考虑使用 bloom filter and/or hash map 来跟踪重复命中。但是，如果您的数组访问确实是随机的，则完全没有必要。
如果只执行读取操作，最好不要将值分配给单个索引，而是分配给索引区间。
例如：
[0, 15000] = 0
[15001, 15002] = 153
[15003, 26876] = 2
[25677, 31578] = 0
...
这可以用一个结构来完成。如果您喜欢 OO 方法，您可能还想定义一个与此类似的 class。
class Interval{
private:
uint32_t start; // First element of interval
uint32_t end; // Last element of interval
uint8_t value; // Assigned value
public:
Interval(uint32_t start, uint32_t end, uint8_t value);
bool isInInterval(uint32_t item); // Checks if item lies within interval
uint8_t getValue(); // Returns the assigned value
}
现在您只需要遍历一系列间隔并检查您的索引是否位于其中一个间隔内，这平均占用的内存要少得多，但会消耗更多 CPU 资源。
Interval intervals[INTERVAL_COUNT];
intervals[0] = Interval(0, 15000, 0);
intervals[1] = Interval(15001, 15002, 153);
intervals[2] = Interval(15003, 26876, 2);
intervals[3] = Interval(25677, 31578, 0);
...
uint8_t checkIntervals(uint32_t item)
for(int i=0; i<INTERVAL_COUNT-1; i++)
{
if(intervals[i].isInInterval(item) == true)
{
return intervals[i].getValue();
}
}
return DEFAULT_VALUE;
}
如果按大小降序对间隔进行排序，则会增加较早找到您要查找的项目的可能性，从而进一步减少平均内存和 CPU 资源使用。
您也可以删除所有大小为 1 的区间。将相应的值放入地图中，只有在区间中找不到您要查找的项目时才检查它们。这也应该会稍微提高平均性能。
就像 Mats 在他的评论回答中提到的那样，如果不知道具体你有什么样的数据（例如，有长0 的运行，依此类推），以及您的访问模式是什么样的（"random" 是指 "all over the place" 还是只是 "not strictly in completely linear fashion" 或 "every value exactly once, just randomized" 或...）。
也就是说，我想到了两种机制：
- 位数组；也就是说，如果你只有两个值，你可以简单地将你的数组压缩 8 倍；如果您有 4 个值（或“3 个值 + 其他所有值”），则可以压缩两倍。这可能不值得麻烦并且需要基准测试，特别是如果您有 真正 随机访问模式，它会逃避您的缓存，因此根本不会改变访问时间。
(index,value)或(value,index)tables。即，对于 1% 的情况有一个非常小的 table，对于 5% 的情况可能有一个 table（它只需要存储索引，因为所有索引都具有相同的值），以及一个大的压缩位最后两种情况的数组。 "table" 我的意思是允许相对快速查找的东西；即，可能是散列、二叉树等，具体取决于您可用的内容和您的实际需求。如果这些子table适合你的一级/二级缓存，你可能会走运。
我将添加到 @o11c 的回答中，因为他的措辞可能有点令人困惑。 如果我需要挤压最后一点和 CPU 循环，我会执行以下操作。
我们将从构建一个 平衡 二叉搜索树开始，它包含 5% "something else" 个案例。对于每次查找，您快速遍历树：您有 10000000 个元素：其中 5% 在树中：因此树数据结构包含 500000 个元素。在 O(log(n)) 时间内走这个，给你 19 次迭代。我不是这方面的专家，但我想那里有一些内存高效的实现。让我们猜猜：
- 平衡树，因此可以计算子树位置（索引不需要存储在树的节点中）。与堆（数据结构）存储在线性内存中的方式相同。
- 1 字节值（2 到 255）
- 索引3个字节（10000000占用23位，适合3个字节）
总计，4 个字节：500000*4 = 1953 kB。适合缓存！
对于所有其他情况（0 或 1），您可以使用位向量。请注意，您不能遗漏 5% 的其他随机访问情况：1.19 MB。
这两个的组合使用大约 3,099 MB。使用此技术，您将节省 3.08 倍的内存。
然而，这并没有击败 @Matteo Italia 的答案（使用 2.76 MB），很遗憾。有什么我们可以额外做的吗？最消耗内存的部分是树中索引的 3 个字节。如果我们可以将其降低到 2，我们将节省 488 kB，总内存使用量将是：2.622 MB，这会更小！
我们如何做到这一点？我们必须将索引减少到 2 个字节。同样，10000000 占用 23 位。我们需要能够丢弃 7 位。我们可以通过将 10000000 个元素的范围划分为 78125 个元素的 2^7（=128）个区域来简单地做到这一点。现在我们可以为每个区域构建一个平衡树，平均有 3906 个元素。选择正确的树是通过将目标索引除以 2^7（或移位 >> 7）来完成的。现在需要存储的索引可以由剩余的 16 位表示。请注意，需要存储的树的长度有一些开销，但这可以忽略不计。另请注意，这种拆分机制减少了遍历树所需的迭代次数，现在减少到 7 次迭代，因为我们丢弃了 7 位：只剩下 12 次迭代。
请注意，理论上您可以重复该过程以切断接下来的 8 位，但这需要您创建 2^15 棵平衡树，平均约有 305 个元素。这将产生 2.143 MB，只有 4 次迭代遍历树，与我们开始时的 19 次迭代相比，这是一个相当大的加速。
最后的结论是：这比 2 位向量策略稍微占用一点内存，但实现起来却很费劲。但是，如果它可以决定是否适合缓存，那么它可能值得一试。
如果数据和访问是均匀随机分布的，性能可能取决于有多少访问避免外层缓存未命中。优化它需要知道什么大小的数组可以可靠地容纳在缓存中。如果您的缓存足够大以容纳每五个单元一个字节，最简单的方法可能是让一个字节保存 0-2 范围内的五个以三为底的编码值（有 5 个值的 243 种组合，因此将适合一个字节），以及一个 10,000,000 字节的数组，只要 base-3 值表示“2”，就会查询该数组。
如果缓存不是那么大，但可以每 8 个单元格容纳一个字节，那么就不可能将一个字节值用于 select 来自八个基数的所有 6,561 种可能组合中的一个字节值- 3 个值，但由于将 0 或 1 更改为 2 的唯一影响是导致不必要的查找，因此正确性不需要支持所有 6,561 个。相反，可以关注 256 个最 "useful" 值。
特别是如果 0 比 1 更常见，反之亦然，一个好的方法可能是使用 217 个值来编码包含 5 个或更少 1 的 0 和 1 的组合，16 个值来编码 xxxx0000 到 xxxx1111， 16 编码 0000xxxx 到 1111xxxx，一个用于 xxxxxxxx。四个值将保留用于人们可能发现的任何其他用途。如果数据按照描述的那样随机分布，那么所有查询中的一小部分将命中仅包含零和一的字节（在所有八组中的大约 2/3 中，所有位都是零和一，大约 7/8那些将有六个或更少的 1 位）；那些没有的绝大多数将落在一个包含四个 x 的字节中，并且有 50% 的机会落在零或一上。因此，只有大约四分之一的查询需要大型数组查找。
如果数据是随机分布的，但缓存不够大，无法处理每八个元素一个字节，可以尝试使用这种方法，每个字节处理超过八个项目，但除非有强烈的偏见趋向于 0 或趋向于 1，随着每个字节处理的数字的增加，无需在大数组中进行查找即可处理的值的比例将缩小。
很久很久以前，我只记得...
在大学里，我们接到了一个加速光线追踪程序的任务，该程序必须通过算法从缓冲区数组中一遍又一遍地读取。一位朋友告诉我始终使用 4 字节的倍数的 RAM 读取。所以我将数组从 [x1,y1,z1,x2,y2,z2,...,xn,yn,zn] 的模式更改为 [x1,y1,z1,0,x2,y2,z2] 的模式,0,...,xn,yn,zn,0]。意味着我在每个 3D 坐标后添加一个空字段。经过一些性能测试：速度更快。 长话短说：从 RAM 的数组中读取 4 个字节的倍数，也可能从正确的起始位置读取，因此您读取了一个小簇，其中包含搜索索引，并从 [= 中的这个小簇读取搜索索引23=]。 （在你的情况下你不需要插入填充字段，但概念应该很清楚）
也许其他倍数也可能是较新系统的关键。
我不知道这是否适用于您的情况，所以如果它不起作用：抱歉。如果它有效，我会很高兴听到一些测试结果。
PS: 哦，如果有任何访问模式或附近的访问索引，您可以重用缓存的集群。
PPS: 应该是，倍数大概是16Bytes之类的吧，时间太久了，记不太清了。
我对C不是很熟悉，但是在C++中可以使用unsigned char来表示0-范围内的整数255.
与正常 int 相比（同样，我来自 Java 和 C++ world) 其中需要 4 byte（32 位），unsigned char 需要 1 byte（8 位）。 所以它可能会将数组的总大小减少 75%。