对于一个非常大的数组的随机访问是否有任何可能的优化(我目前使用uint8_t，我问什么更好)
uint8_t MyArray[10000000];
当数组中任何位置的值为
- 0或1表示95%的所有情况，
- 4%的病例中有2例，
- 介于 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，这意味着你必须在辅助数组中查找它。在这里，您将执行二叉搜索以查找您感兴趣的索引左移 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 µsn", 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 µsn", dur);
arr_t(dur);
}
}
fprintf(stderr, " lookup | ± | array | ± | speedupn");
printf("%7.0f | %4.0f | %7.0f | %4.0f | %0.2fn",
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
结果是...混合！
- 一般来说，在大多数这些机器上都有某种加速，或者至少它们是相当的。
- 阵列真正胜过"智能结构"查找的两种情况是在具有大量缓存且不是特别繁忙的机器上：上面的至强E5-1650(15 MB缓存)是一台夜间构建机器，目前相当空闲;至强E5-2697(35 MB缓存)是一台用于高性能计算的机器，在空闲时刻也是如此。这确实是有道理的，原始数组完全适合其巨大的缓存，因此紧凑的数据结构只会增加复杂性。
- 在"性能范围"的另一边 - 但阵列再次稍微快一点的地方，有一个不起眼的赛扬，它为我的 NAS 供电;它的缓存太少了，阵列和"智能结构"都不适合它。缓存足够小的其他计算机执行类似。
- Xeon X5650必须谨慎行事 - 它们是相当繁忙的双插槽虚拟机服务器上的虚拟机;很可能，虽然名义上它有相当数量的缓存，但在测试期间它会被完全不相关的虚拟机抢占几次。
另一种选择可能是
- 检查结果是 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% 的情况下被查找。当然，像往常一样，它是否是一个好主意取决于许多其他条件，所以唯一的答案是尝试实际使用。
这更像是一个"长评论"，而不是一个具体的答案
除非你的数据是众所周知的，否则我怀疑任何人都能直接回答你的问题(我不知道任何符合你描述的东西，但我不知道关于各种用例的各种数据模式的一切)。稀疏数据是高性能计算中的常见问题，但它通常是"我们有一个非常大的数组，但只有一些值不为零"。
对于像我认为的那样不知名的模式，没有人会直接知道哪个更好，这取决于细节：随机访问的随机性 - 系统是访问数据项的集群，还是像来自统一随机数生成器一样完全随机。表数据是完全随机的，还是先有 0 的序列然后是 1 的序列，并且其他值分散？如果你有相当长的 0 和 1 序列，运行长度编码会很好地工作，但如果你有"0/1 的棋盘格"，则运行长度编码将不起作用。此外，您必须保留一个"起点"表，以便您可以合理快速地到达相关地点。
我很久以前就知道，一些大型数据库只是RAM中的一个大表(在本例中为电话交换用户数据)，其中一个问题是处理器中的缓存和页表优化毫无用处。呼叫者很少与最近呼叫某人的人相同，因此没有任何类型的预加载数据，它只是纯粹随机的。大页面表是针对此类访问的最佳优化。
在很多情况下，在"速度和小尺寸"之间做出妥协是软件工程中你必须选择的事情之一[在其他工程中，这不一定是那么多的妥协]。因此，"为更简单的代码浪费内存"通常是首选。从这个意义上说，"简单"解决方案很可能对速度更好，但是如果您对RAM有"更好"的使用，那么优化表的大小将为您提供足够的性能和大小的良好改进。有很多不同的方法可以实现这一点 - 正如评论中所建议的那样，存储两个或三个最常见值的 2 位字段，然后是其他值的一些替代数据格式 - 哈希表将是我的第一个方法，但列表或二叉树也可能有效 - 再次， 这取决于你的"不是0,1或2"的模式。同样，这取决于值在表中的"分散"方式 - 它们是在集群中还是更均匀分布的模式？
但问题是您仍在从RAM读取数据。然后，您将花费更多的代码来处理数据，包括一些代码来处理"这不是一个公共值"。
大多数常见压缩算法的问题在于它们基于解包序列，因此您无法随机访问它们。将大数据拆分为一次 256 个条目的块，并将 256 个解压缩为uint8_t数组，获取所需的数据，然后丢弃未压缩的数据，这种开销极不可能为您提供良好的性能 - 当然，假设这很重要。
最后，您可能必须实现评论/答案中的一个或几个想法来进行测试，看看它是否有助于解决您的问题，或者内存总线是否仍然是主要的限制因素。
我过去所做的是在位集前面使用哈希图。
与 Matteo 的答案相比，这减少了一半的空间，但如果"异常"查找很慢(即有很多例外)，则可能会更慢。
然而，通常"缓存为王"。
除非你的数据有模式，否则不太可能有任何合理的速度或大小优化，而且 - 假设你的目标是一台普通的计算机 - 10 MB无论如何都没什么大不了的。
您的问题中有两个假设：
- 数据存储不佳，因为您没有使用所有位
- 更好地存储它会让事情变得更快。
我认为这两种假设都是错误的。在大多数情况下，存储数据的适当方法是存储最自然的表示形式。在您的情况下，这就是您所追求的：0 到 255 之间的数字的字节。任何其他表示将更加复杂，因此 - 在所有其他条件相同的情况下 - 更慢且更容易出错。要偏离这一一般原则，你需要一个更有力的理由，而不是在95%的数据上可能浪费六个位。
对于第二个假设，当且仅当更改数组大小导致缓存未命中次数大幅减少时，它将是正确的。这是否会发生只能通过分析工作代码来确定，但我认为这不太可能产生实质性的影响。因为无论哪种情况，您都将随机访问阵列，因此处理器将很难知道在任何一种情况下都要缓存和保留哪些数据位。
如果数据和访问是均匀随机分布的，则性能可能取决于哪一部分访问避免了外部缓存未命中。 优化这一点需要知道缓存中可以可靠地容纳多大的数组。 如果您的缓存足够大，可以容纳每五个单元格一个字节，最简单的方法可能是让一个字节保存 0-2 范围内的五个进制三编码值(有 5 个值的 243 个组合，因此可以放入一个字节)，以及一个 10,000,000 字节的数组，只要 base-3 值指示"2"，就会查询该数组。
如果缓存不是那么大，但每 8 个单元格可以容纳一个字节，那么就不可能使用一个字节值从八个 base-3 值的所有 6,561 种可能组合中进行选择，但由于将 0 或 1 更改为 2 的唯一影响是导致不必要的查找， 正确性不需要支持所有 6,561。 相反，人们可以专注于256个最"有用"的值。
特别是如果 0 比 1 更常见，反之亦然，一个好的方法可能是使用 217 个值对包含 5 个或更少 1 的 0 和 1 的组合进行编码，使用 16 个值对 xxxx0000 到 xxxx1111 进行编码，使用 16 个值对 0000x 到 1111xxxx 进行编码，1 个值对 xxx 进行编码。 四个值将保留用于可能发现的任何其他用途。 如果数据按描述随机分布，则所有查询中的大多数将命中仅包含零和一的字节(在所有八组中的大约 2/3 中，所有位都是零和一，其中大约 7/8 将有六个或更少的 1 位);绝大多数没有降落在包含四个X的字节中，并且有50%的机会落在零或一上。 因此，只有大约四分之一的查询需要大数组查找。
如果数据是随机分布的，但缓存不够大，无法处理每八个元素一个字节，则可以尝试使用此方法，每个字节处理八个以上的项目，但除非对 0 或 1 有很强的偏差，否则无需在大数组中查找即可处理的值的比例将随着每个字节处理的数量增加而缩小。
我会补充@o11c的答案，因为他的措辞可能有点混乱。 如果我需要挤压最后一个位和 CPU 周期，我会执行以下操作。
我们将首先构建一个平衡的二叉搜索树，其中包含 5% 的"其他"情况。对于每次查找，您都可以快速浏览树：您有 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, 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 的所有间隔。将相应的值放入地图中，并仅在间隔内未找到您要查找的项目时才对其进行检查。这也应该会稍微提高平均性能。
很久以前，我只记得...
在大学里，我们接到了一项任务，即加速光线追踪程序，该程序必须通过算法一遍又一遍地从缓冲数组中读取。一位朋友告诉我，要始终使用 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：哦，如果有任何访问模式或附近访问的索引，您可以重用缓存的集群。
PPS：可能是，多重因素更像是16Bytes或类似的东西，这是很久以前的事了，我记得很清楚。
查看此内容，您可以拆分数据，例如：
- 一个被索引并表示值 0 的位集(std：：vector 在这里很有用)
- 一个位集，它被索引并表示值 1
- 一个 std：：vector，表示值为 2，包含引用此值的索引
- 其他值的映射(或 std：：vector>)
在这种情况下，所有值都会显示到给定的索引，因此您甚至可以删除其中一个位集，并将该值表示为在其他位集中缺失的值。
这将为您节省一些内存，尽管会使最坏的情况变得更糟。 您还需要更多 CPU 能力来进行查找。
一定要测量！
就像 Mats 在他的评论答案中提到的那样，很难说出什么是真正的最佳解决方案，不知道你拥有什么样的数据(例如，是否有长时间的 0，等等)，以及你的访问模式是什么样子的("随机"是指"无处不在"还是只是"不严格以完全线性的方式"或"每个值恰好一次， 只是随机的"或...
也就是说，有两种机制浮现在脑海中：
位数组;- 即，如果你只有两个值，你可以简单地将数组压缩8倍;如果你有4个值(或"3个值+其他所有值")，你可以压缩两倍。这可能不值得麻烦，需要基准测试，特别是如果您有真正的随机访问模式，这些模式会逃脱缓存，因此根本不会更改访问时间。
(index,value)或(value,index)表。 即，对于 1% 的情况，有一个非常小的表，对于 5% 的情况可能有一个表(只需要存储索引，因为所有索引都具有相同的值)，以及一个用于最后两种情况的大压缩位数组。对于"表"，我的意思是允许相对快速查找的东西;即，可能是哈希，二叉树等，具体取决于您可用的内容和实际需求。如果这些子表适合您的 1st/2nd 级缓存，您可能会很幸运。
我对 C 不是很熟悉，但在C++中您可以使用无符号字符来表示 0 - 255 范围内的整数。
与需要4 字节(32 位)的普通int(再次，我来自Java和C++世界)相比，无符号字符需要1 个字节(8 位)。 因此，它可能会将数组的总大小减少 75%。
您已经简洁地描述了数组的所有分布特征;扔掉数组。
您可以轻松地将数组替换为随机方法，该方法生成与数组相同的概率输出。
如果一致性很重要(为同一随机索引生成相同的值)，请考虑使用布隆过滤器和/或哈希图来跟踪重复命中。但是，如果您的数组访问确实是随机的，则完全没有必要。