java - 按排序顺序返回唯一条目的随机数生成器

Question

我需要一个生成器来生成许多(最多一万亿，10^12)个唯一的随机 64 位数字。 生成器需要按排序顺序(Long.MIN_VALUE 到 Long.MAX_VALUE)返回数字。问题是对 $10^{12}$ 数字进行排序很慢。用例正在复制为 BBHash 运行的测试(在 paper 中，4.5 索引万亿键)。

直接的解决方案是在内存中创建一个集合，使用一个巨大的位集合左右 以确保不返回重复项。 但这会使用太多内存或 I/O。 我最多想使用几 MB 的内部状态。

生成器应该在内部使用 java.util.Random。 它应该尽可能“公平”(具有与以其他方式生成的统计分布相同的统计分布)。我还想要一个适用于 128 位数字(2 个长整数)的版本。

到目前为止，我所拥有的是在内存中创建集合的代码(Java 代码):

public static void main(String... args) {
    for(long x : randomSet(10, 0)) {
        System.out.println(x);
    }
}

static Iterable<Long> randomSet(int size, int seed) {
    Random r = new Random(seed);
    TreeSet<Long> set = new TreeSet<Long>();
    while (set.size() < size) {
        set.add(r.nextLong());
    }
    return set;
}

-8292973307042192125
-7423979211207825555
-6688467811848818630
-4962768465676381896
-2228689144322150137
-1083761183081836303
-279624296851435688
4437113781045784766
6146794652083548235
7105486291024734541

最简单(错误)的解决方案不是随机的，而是平均分配结果。 我认为“添加随机间隙”的解决方案不会奏效， 因为它很慢，而且这些差距的总和在 10^12 之后，不会落在它应该的地方(好吧，也许:记住剩下多少数字，然后重新计算分布......)。我认为以下应该可行，但是很复杂，并且不确定要使用什么公式:对于每个位级别， 递归地计算可能会出现多少个 0/1 (以某种方式使用二项式分布或近似值，正态/高斯分布)。 在某个点停止(比如，100 万个条目或更少的 block )， 使用上面的代码，速度。 但也许有一个优雅的解决方案。 也许这与 Metropolis–Hastings 算法有关，不确定。 我读了“顺序随机抽样的有效算法”， 但我认为它只适用于小 n，我发现很难从中得到一个简单的算法。

Java 代码最好，但 C 也不错(无论如何，在某些时候我可能不得不将其转换为 C/C++)。我不想使用太多库，以简化移植。

Answer 1

对于要求

1. generate a sequence of random numbers r_i from a whole number interval I = [-(R+1), R], R > 0 with a statistical distribution like java.util.Random
2. the sequence r_i must be strictly increasing (r_i > r_j for i > j)

我们可以想出一个简单的算法

A1:
 - draw a random number r_i from I via a library call
 - discard it, if it is less or equal the last draw, try another pick

可能的提示是这个算法可能不会给出正确数量的生成的 r_i，有一个模糊的要求大约 N=10^12 个预期的总数

3. "need a generator for many (up to one trillion, 10^12) unique random 64-bit numbers"

解决方案是

A2:
 - to generate N numbers and then 
 - sort them

但是还有一个要求，就是没有足够的可用内存。

4. "I'd like to use at most a few MB of internal state."

我的推测是不可能一次满足所有这些要求。

作为妥协我建议

A3:
 R=2^63 = 9 10^18  
 N=1 Trillion = 10^12
 - divide the range I=[-R,R-1] into N intervals of length (2R+1)/N each 
 - visit each of those intervals (visiting one interval after another)
 - draw a random number from that interval

这将按递增顺序给出 N 个随机数。

更新:

浏览 BBHash paper 后和 sources几次这是我的理解:

给定一些整数集 I 和一个 N=|S| 的子集 S元素，BBHash 过程将计算一个函数 f，它将 S 映射到 {1,..,N} 的某个排列(什么排列似乎由 BBHash 过程隐式决定)并将所有其他元素从 I 映射到一个特殊值 Imax来 self 。

可能的测试:

给定 S 和 f，人们可能会检查是否正确计算了 I 中某个任意元素在 S 中的成员资格。

也可以检查 f(S) = {1,..,N}。

我的猜测是所请求的算法旨在在内存预算紧张的情况下动态计算 N=10^12 的样本集 S，需要随机数序列的唯一性而不是单调。

引用https://stackoverflow.com/a/35050835/2579220

Probabilistic data structures can't give you a definite answer, instead they provide you with a reasonable approximation of the answer and a way to approximate this estimation. They are extremely useful for big data and streaming application because they allow to dramatically decrease the amount of memory needed (in comparison to data structures that give you exact answers).

In majority of the cases these data structures use hash functions to randomize the items. Because they ignore collisions they keep the size constant, but this is also a reason why they can't give you exact values.

在 BBHash 的情况下，使用了一系列不同的哈希函数 h_i。应用不同的 h_i 直到没有碰撞发生。这仅在输入是唯一的情况下才有效。仅当实现为特定 S 存储了足够多的不同 h_i 时，它才会起作用。