2

我有一组连续整数值和相应的一组非连续值，例如：

0 -> 22
1 -> 712
2 -> 53
3 -> 12323
...

等等。

项目的数量非常大（大约 10^9...10^10），因此不能只使用普通数组。

是否存在能够从第一个值快速映射到另一个具有中等内存需求的数据结构？例如：

ret = map(0); // returns 22
ret = map(3); // returns 12323

编辑：这个集合中的值实际上是使用伪随机数生成器生成的，所以不可能建议一些特定的分布。问题是 - 是否可以降低内存要求（可能是以查找速度为代价）？我的意思是使用“完美哈希”之类的东西——生成这种“完美哈希”所需的时间并不重要。

4

4 回答 4

2

由于您的范围是连续的，因此显而易见的解决方案是将您的值存储在连续的 int[] 中。那么值 i 是arr[i]。作为 PRNG 生成的值，将很难应用进一步的压缩。

另一种以时间换空间的解决方案是存储 RNG 的种子并即时重新计算。通过存储中间种子，这种方法可以及时改进，并在空间上恶化。即密钥 1000、2000 等的种子。

于 2012-08-17T12:52:55.603 回答
0

如果您的函数范围是由伪随机数生成器按顺序生成的一组数字，那么您可以将序列压缩到生成序列的代码以及开始前 PRNG 的状态。例如，包含 pi 的十进制扩展的（无限）数字系列很容易（并且在技术上是无限地）压缩为代码以生成该系列；您的系列可以被视为几乎相同的一个例子。

因此，如果您愿意等待很长时间以获取系列中的最后一个元素，则可以通过将系列不写入数据结构而是写入函数来获得非常好的压缩。那是您的时间/空间权衡范围的一端。

在频谱的另一端是所有数字的数组。这会占用大量空间，但可以非常快速地 ( O(1)) 访问集合中的任何所需元素。出于各种原因，这似乎对您没有吸引力，但我不确定比数组更聪明的数据结构是否会节省大量空间，或者就此而言是否节省时间。

我看到的一个明显的解决方案是每隔一段时间保存一组 PRNG 的中间状态，因此您的“数据”结构将变为：

ret(0) = prng(seed, other_parameters, ...)
ret(10^5-1)  = prng(seed', other_parameters, ...)
ret(2*(10^5)-1) = prng(seed'', other_parameters, ...)

等等，然后，要获取元素 9765，例如，您读取（PRNG 的状态）ret(0)并在其后生成第 9765 个伪随机数。

于 2012-08-17T12:52:40.770 回答
0

好的，所以目的是用速度换取更少的内存使用。

想象一下，您有某种填充数组的循环。

int array[intendedArraySize];

seed = 3;
for (size_t z = 0; z < intendedArraySize; z++)
{
     array[z] = some_int_psn_generator(seed);
}

之后您可以显示这些值。

for (size_t z = 0; z < intendedArraySize; z++)
{
    std::cout << z << " " << array[z] << std::endl;
}

如果确实如此，请考虑完全丢弃数组，只需每次重新计算值即可。

for (size_t z = 0; z < intendedArraySize; z++)
{
    std::cout << z << " " << some_int_psn_generator(z) << std::endl;
}
于 2012-08-17T15:35:23.270 回答
0

您可以通过准确使用每个值所需的位数来节省一些空间。例如，如果您的值只有 24 位，您可以在 32 位整数上保存一个字节。也就是说，您可以节省的内存只有这么多。

在 64 位机器上，将mmap()文件存储到内存地址是可行的，因此可以通过使用磁盘存储来克服物理内存限制，但要以性能为代价。

但是，既然您提到使用伪随机生成器来生成值，那么仅存储特定索引的 RNG 种子并根据需要计算其余值怎么样？例如，您可以存储索引 0、100、200...的种子，并通过将 RNG 重新播种为 100 并调用生成器函数 3 次来计算例如 102。

这种方法会大大减少所需的内存（在本例中为 100），并且您可以通过捆绑或缓存查询来降低性能成本。

于 2012-08-17T12:52:06.850 回答