algorithm - 存储一长串随机数的最佳方法是什么？

Question

我正在寻找一种算法，它可以存储一长串（可能是数千个）随机数并有效地检索它们。通常，该解决方案不需要对数据进行任何排序，即数字在生成时存储，并且所需的存储空间应小于此类数字的数组/散列所需的存储空间。可以将新号码添加到列表中。

Answer 1

尝试实现任何伪随机生成器。您所需要的一切 - 只需存储初始种子（必须是随机的）。但是，当然 - 访问伪随机序列的任何元素都将具有 O(N) 复杂度。这只是时空权衡。

Answer 2

@Stemm 有一个很好的想法，就是将种子存储到伪随机数生成器 (prng) 中。还需要对数字进行计数，以便您知道调用 prng 多少次来检索它们。

如果您无权访问种子或数字是随机的，那么您可能有另一种选择。如果你的数字是整数，不是很大，并且你知道没有重复，那么考虑将它们存储为位。因此，例如，如果您的最长值适合 2 字节 int，则可以使用 1 位存储该值。一些例子：

0 = 1。

4 = 10000 二进制或 10 十六进制。

10 = 10000000000 二进制。

如果最大值是 65535，这是可以容纳在 16 位无符号整数内的最大值，那么保存所有值的内存量可以计算为 65536 / 8 = 8192 字节。如果您使用的是 Java，请查看java.util.BitSet或java.math.BigInteger类以帮助执行此操作。

Answer 3

如果这些数字是真正随机的，或者即使它们来自您不知道种子的足够好的 RNG，则无法压缩它们。对于特定的压缩方案，您可能会很幸运并得出一组可压缩的数字，但此类事件的概率总是很小。

这来自于 count 参数（又名 pigeonhole 参数），没有足够的长度小于的位串n来编码每个长度的字符串n。流行的压缩方案通过利用只有一小部分输入字符串是可能的这一事实来解决这个问题。然后这个小集合（例如英文文本、可执行二进制文件等）可以在较短的字符串上完全编码。

对于完全随机的字符串，没有这样的后门，因此不可能进行有意义的压缩。