当95% 的情况下值为0或1时，对于非常大的数组上的随机访问有什么优化吗？

对于非常大的数组上的随机访问是否有任何可能的优化(我目前使用的是 uint8_t，我正在询问哪种方法更好)

uint8_t MyArray[10000000];

当数组中任何位置的值为

  • 所有病例 95% 均为0 或 1,
  • 2 4% ,
  • 在 3和 255之间 其他 1% 的案件？

那么，还有什么比使用 uint8_t数组更好的方法吗？它应该尽可能快地以随机顺序遍历整个数组，这对 RAM 带宽是非常沉重的，所以当有多个线程同时为不同的数组做这件事时，目前整个 RAM 带宽很快就饱和了。

我这么问是因为使用这么大的数组(10MB)感觉效率很低，而实际上我们知道除了5% 之外，几乎所有的值都是0或1。因此，当数组中95% 的值实际上只需要1位而不是8位时，这将减少几乎一个数量级的内存使用。 感觉好像必须有一个更有效的内存解决方案，这将大大减少内存带宽的需要，因此也是显着更快的随机访问。

15624 次浏览
小开
最佳答案

我想到的一个简单的可能性是，对于普通情况，保留每个值2位的压缩数组，对于其他值，保留每个值4字节的分隔数组(原始元素索引为24位，实际值为8位，因此 (idx << 8) | value))。

当你查找一个值时，你首先在2bpp 数组(O (1))中查找; 如果你找到0,1或2，它就是你想要的值; 如果你找到3，它意味着你必须在次要数组中查找它。在这里，您将执行一个二进制搜索，以左移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位地址，你将不得不调整“二级存储”; 一个简单的方法来扩展它是有一个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;
}

(代码和数据总是在我的 Bitbucket 中更新)

上面的代码填充了一个10M 的元素数组，随机数据分布在 OP 指定的文章中，初始化我的数据结构，然后:

  • 使用我的数据结构执行10M 个元素的随机查找
  • 通过原始数组执行相同操作。

(请注意，在顺序查找的情况下，数组总是在很大程度上获胜，因为它是您可以执行的最友好的缓存查找)

最后两个块重复50次并计时，最后计算并打印每种查找类型的均值和标准差，以及加速比(lookup _ mean/array _ mean)。

我在 Ubuntu 16.04上用 g + + 5.4.0(-O3 -static，加上一些警告)编译了上面的代码，并在一些机器上运行它; 大多数机器都在运行 Ubuntu 16.04，一些旧的 Linux，一些新的 Linux。我不认为操作系统应该在这种情况下相关。

            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

结果是... 喜忧参半！

  1. 一般来说，这些机器中的大多数都有某种加速，或者至少它们是平行的。
  2. 数组真正胜过“智能结构”查找的两种情况是在一台缓存很多而且不是特别忙的机器上: 上面的至强 E5-1650(15MB 缓存)是一台夜间构建机器，目前相当空闲; 至强 E5-2697(35MB 缓存)是一台高性能计算机，在空闲时也是如此。这是有意义的，原始数组完全适合它们的巨大缓存，因此紧凑的数据结构只会增加复杂性。
  3. 在“性能光谱”的另一端——但是在数组稍微快一点的地方，有一个不起眼的赛扬(Celeron)驱动我的 NAS; 它的缓存非常少，以至于数组和“智能结构”都不适合它。其他缓存足够小的机器执行类似的操作。
  4. 至强 X5650必须谨慎对待——它们是一个非常繁忙的双套接字虚拟机服务器上的虚拟机; 很可能是这样的，虽然名义上它有相当数量的缓存，但在测试期间，它被完全不相关的虚拟机抢占了好几次。
小开

这更像是一个“冗长的评论”，而不是一个具体的答案

除非你的数据是一些众所周知的东西，否则我怀疑没有人能够直接回答你的问题(我不知道有什么东西符合你的描述，但是我不知道所有关于各种用例的各种数据模式的一切)。稀疏数据是高性能计算中的一个常见问题，但它通常是“我们有一个甚大天线阵，但只有一些值是非零的”。

因为没有人知道像我认为你的是什么样的模式，没有人会直接知道哪个更好，这取决于细节: 随机访问是如何随机的-是系统访问数据项的集群，还是它完全随机像从一个统一的随机数生成器。表格数据是完全随机的，还是先有0的序列，然后有1的序列，再有其他值的散射？运行长度编码将工作良好，如果您有合理的长序列0和1，但不会工作，如果您有“棋盘0/1”。此外，你必须保持一个“起点”表，这样你就可以合理快速地工作到相关的地方。

很久以前我就知道，一些大型数据库只是 RAM 中的一个大型表(本例中是电话交换机用户数据) ，其中一个问题是处理器中的缓存和页表优化非常无用。调用者很少与最近调用某人的人相同，因此没有任何预加载的数据，它只是纯粹的随机。对于这种类型的访问，大页表是最好的优化。

在很多情况下，在“速度和小尺寸”之间做出妥协是软件工程中必须选择的事情之一(在其他工程中，这不一定是一种妥协)。因此，“为更简单的代码浪费内存”通常是首选。从这个意义上说，“简单”的解决方案很可能在速度方面更好，但是如果您对 RAM 有“更好”的使用，那么优化表的大小将给您带来足够的性能和大小方面的良好改进。有很多不同的方法可以实现这一点——就像注释中建议的那样，一个2位字段存储两个或三个最常见的值，然后为其他值提供一些替代数据格式——哈希表将是我的第一种方法，但列表或二进制树也可以工作——同样，它取决于“不是0,1或2”的模式。同样，它取决于值在表中是如何“分散”的——它们是在集群中，还是更像是均匀分布的模式？

但问题是您仍然在从 RAM 读取数据。然后，您将花费更多的代码来处理数据，包括一些代码来处理“这不是一个公共值”。

最常见的压缩算法存在的问题是，它们基于解压序列，因此无法随机访问它们。将大数据分割成256个条目，将256个条目解压缩成 uint8 _ t 数组，获取所需数据，然后丢弃未压缩的数据，这些开销不太可能给您带来良好的性能——当然，前提是这具有一定的重要性。

最后，你可能不得不在评论/回答中实现一个或几个想法来测试，看看它是否有助于解决你的问题，或者内存总线是否仍然是主要的限制因素。

小开

看看这个，你可以分割你的数据，例如:

  • 索引并表示值0的位集(std: : Vector 在这里会很有用)
  • 被索引并表示值1的位集
  • 值为2的 std: : Vector，包含引用此值的索引
  • 其他值(或 std: : Vector >)的映射

在这种情况下，所有的值都出现在给定的索引之前，因此您甚至可以删除其中一个位集，并将该值表示为其他位集中缺失的值。

这会为这个案子节省一些记忆，尽管会让最糟糕的情况变得更糟。 您还需要更多的 CPU 能量来执行查找。

一定要量好！

小开

我过去所做的是在位集的 前面中使用散列表。

与 Matteo 的回答相比，这样做减少了一半的空间，但是如果“异常”查找速度很慢(例如，有许多异常) ，那么这样做可能会慢一些。

然而，通常“缓存为王”。

小开

另一个选择可能是

  • 检查结果是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表示“其他”。

这个结构对于更新来说很简单，多占用了25% 的内存，但是只有5% 的情况下会查找大部分内存。当然，像往常一样，如果它是一个好主意或不取决于很多其他条件，所以唯一的答案是实验与真正的使用。

小开

除非你的数据有模式，否则不太可能有任何合理的速度或大小优化，并且——假设你的目标是一台普通的计算机——10MB 不是什么大问题。

你的问题有两个假设:

  1. 由于没有使用所有的位，数据存储得很差
  2. 更好地储存会让事情变得更快。

我认为这两个假设都是错误的。在大多数情况下，存储数据的适当方法是存储最自然的表示。在您的示例中，这就是您所选择的字节: 0到255之间的数字的一个字节。任何其他表示都将更加复杂，因此——所有其他条件相同——速度更慢，更容易出错。为了偏离这个一般原则，你需要一个比95% 的数据上潜在的6个“浪费”位更强有力的理由。

对于您的第二个假设，如果且仅当更改数组的大小会导致大幅度减少缓存丢失时，才会为真。这种情况是否会发生，只能通过分析工作代码来确定，但我认为这不太可能产生实质性的影响。因为在这两种情况下都是随机访问数组，所以处理器将很难知道在这两种情况下要缓存和保存哪些数据位。

小开

您已经简要地描述了数组的所有分布特征; 扔掉数组。

您可以轻松地用随机方法替换数组，该方法产生与数组相同的概率输出。

如果一致性很重要(为相同的随机索引产生相同的值) ，可以考虑使用 开花过滤器开花过滤器和/或 散列表来跟踪重复命中。但是，如果您的数组访问真的是随机的，那么这是完全没有必要的。

小开

如果只执行读操作，最好不要将值赋给单个索引，而是赋给索引的间隔。

例如:

[0, 15000] = 0
[15001, 15002] = 153
[15003, 26876] = 2
[25677, 31578] = 0
...

这可以通过一个结构来完成。如果您喜欢 OO 方法，您可能还需要定义一个类似于此的类。

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运行，等等) ，以及你的访问模式是什么样的(“随机”是指“到处都是”还是仅仅是“不严格地以完全线性的方式”或者“每个值只有一次，只是随机”还是...) ，就很难说什么是真正的最佳解决方案。

尽管如此，我还是想到了两种机制:

  • 比特数组; 也就是说，如果你只有两个值，你可以轻松地压缩你的数组8倍; 如果你有4个值(或“3个值 + 其他所有值”) ，你可以压缩2倍。这可能只是不值得的麻烦，将需要基准，特别是如果您有 真的随机访问模式逃脱您的缓存，因此不改变访问时间在所有。
  • (index,value)或 (value,index)表。例如，对于1% 的情况有一个非常小的表，对于5% 的情况可能有一个表(它只需要存储索引，因为所有索引都具有相同的值) ，对于最后两种情况有一个大的压缩位数组。对于“表”，我的意思是允许相对快速的查找; 例如，可能是一个散列，一个二叉树，等等，这取决于您有什么可用的和您的实际需要。如果这些子表适合您的第一/第二级缓存，那么您可能会比较幸运。
小开

我将补充 @ o11c的回答，因为他的措辞可能有点混乱。 如果我需要压缩最后一位和 CPU 周期，我会做以下操作。

我们将从构建一个包含5% “其他东西”案例的 平衡二叉查找树开始。对于每次查找，都要快速遍历树: 您有10000000个元素: 其中5% 在树中: 因此树数据结构包含500000个元素。在 O (log (n))时间内遍历这个过程，会得到19次迭代。我不是这方面的专家，但是我猜测有一些内存高效的实现。让我们猜猜看:

  • 平衡树，因此子树位置可以计算(索引不需要存储在树的节点中)。与堆(数据结构)存储在线性内存中的方式相同。
  • 1字节值(2到255)
  • 索引为3字节(10000000需要23位，大小为3字节)

总共4字节: 500000 * 4 = 1953kB。适合缓存！

对于所有其他情况(0或1) ，您可以使用位向量。请注意，不能忽略随机访问的5% 其他情况: 1.19 MB。

这两者的组合使用大约3.099 MB。使用这种技术，您将节省3.08倍的内存。

然而，遗憾的是，这并没有超过 @ Matteo Italia的答案(它使用2.76 MB)。还有什么我们能做的吗？内存消耗最大的部分是树中的3字节索引。如果我们能把这个数字减少到2，我们将节省488kB，总内存使用量将是: 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位向量策略稍微占用了一点内存，但实现起来却很困难。但是如果它可以决定是否适合缓存，那么尝试一下也许是值得的。

小开

如果数据和访问是均匀随机分布的，那么性能可能取决于访问的哪一部分可以避免外层缓存丢失。优化，将需要知道什么大小的数组可以可靠地容纳在缓存中。如果您的缓存足够大，可以容纳每5个单元格一个字节，最简单的方法可能是让一个字节保存0-2范围内的5个以3为基数的编码值(5个值有243个组合，所以将适合于一个字节) ，以及一个10,000,000字节的数组，每当以3为基数的值表示“2”时，将查询这个数组。

如果缓存不是那么大，但是可以容纳每8个单元一个字节，那么就不可能使用一个字节值从所有6,561个可能的8个基数 -3的组合中进行选择，但是因为将0或1改为2的唯一效果将导致一个不必要的查找，正确性将不需要支持所有6,561个。相反，我们可以关注256个最“有用”的值。

特别是如果0比1更常见，或者反之亦然，一个好的方法可能是使用217个值来编码包含5个或更少1的0和1的组合，使用16个值来编码 xxxx0000到 xxx1111，使用16来编码0000xxxx 到111xxxxx，使用一个值来编码 xxxxxxxxx。对于可能发现的其他用途，将保留四个值。如果数据像上面描述的那样是随机分布的，那么所有查询中的大部分都会碰到只包含0和1的字节(在所有8组中的2/3中，所有比特都是0和1，其中大约7/8会有6个或更少的1比特) ; 绝大多数没有碰到这种情况的查询都会碰到包含4个 x 的字节，并且有50% 的机会碰到0或1。因此，只有大约四分之一的查询需要大数组查找。

如果数据是随机分布的，但是缓存不够大，不足以处理每8个元素一个字节，可以尝试使用这种方法，每个字节处理8个以上的项目，但是除非有一个强烈的偏向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个字节的倍数，也可能从正确的开始位置读取，所以读取一个小集群，其中包含搜索索引，然后从 CPU 中的这个小集群中读取搜索索引。(在您的情况下，您不需要插入填充字段，但是概念应该很清楚)

也许其他倍数也可能是新系统的关键。

我不知道这是否适用于你的情况，所以如果它不工作: 对不起。如果它工作，我会很高兴听到一些测试结果。

PS: 哦，如果有任何访问模式或附近的访问索引，您可以重用缓存的集群。

附言: 可能是，多因素更像是16字节或类似的东西，太久以前，我可以记得很清楚。

小开

我对 C 不是很熟悉，但是在 C + + 中，你可以使用 无符号字符来表示0-255范围内的整数。

与需要 4字节(32位)的正常 Int(同样，我来自 爪哇咖啡和 C + + 世界)相比，无符号字符需要 1字节(8位)。 所以它可以将数组的总大小减少75% 。


提交答案