python - 非常大范围的高效随机生成器(在 python 中)

Question

我正在尝试创建一个生成器，该生成器返回给定范围内的数字，这些数字通过函数给出的特定测试 foo .但是我希望以随机顺序测试这些数字。以下代码将实现这一点:

from random import shuffle

def MyGenerator(foo, num):
    order = list(range(num))
    shuffle(order)
    for i in order:
        if foo(i):
            yield i

问题

此解决方案的问题在于，有时范围会非常大(num 的顺序可能是 10**8 或更高)。这个函数可能会变慢，因为内存中有这么大的列表。我已尝试使用以下代码避免此问题:

from random import randint    

def MyGenerator(foo, num):
    tried = set()
    while len(tried) <= num - 1:
        i = randint(0, num-1)
        if i in tried:
            continue
        tried.add(i)
        if foo(i):
            yield i

这在大多数情况下都很有效，因为在大多数情况下 num会很大，foo将传递合理数量的数字和总次数 __next__将被调用的方法将相对较小(例如，最多 200 个通常要小得多)。因此，我们很可能偶然发现一个通过 foo 的值。测试和大小 tried永远不会变大。 (即使它只有 10% 的时间通过，我们也不会期望 tried 大致大于 2000。)

然而，当num很小(接近 __next__ 方法被调用的次数，或者 foo 大部分时间失败，上述解决方案变得非常低效 - 随机猜测数字，直到它猜到一个不在 tried 中的数字。 .

我尝试的解决方案...

我希望使用某种映射数字 0,1,2,..., n 的函数以一种大致随机的方式在自己身上。 (这不用于任何安全目的，因此如果它不是世界上最“随机”的功能也没关系)。这里的函数 ( Create a random bijective function which has same domain and range ) 将带符号的 32 位整数映射到自身，但我不确定如何将映射调整到更小的范围。鉴于 num我什至不需要 0,1,..num 上的双射只是一个值 n大于并“接近”num (使用您认为合适的任何关闭定义)。然后我可以执行以下操作:

def mix_function_factory(num):
    # something here???
    def foo(index):
        # something else here??
    return foo

def MyGenerator(foo, num):
    mix_function = mix_function_factory(num):
    for i in range(num):
        index = mix_function(i)
        if index <= num:
            if foo(index):
                yield index

(只要双射不是在一组大大大于 num 的数字上，index <= num 不为真的次数就会很小)。

我的问题

你能想到以下其中一项吗:

• mix_function_factory 的潜在解决方案甚至是 mix_function 的一些其他潜在功能我可以尝试概括 num 的不同值？
• 解决原始问题的更好方法？

提前致谢....

Answer 1

问题基本上是生成 0..n-1 范围内整数的随机排列。

对我们来说幸运的是，这些数字有一个非常有用的属性:它们都有一个不同的值模 n。如果我们可以对这些数字应用一些数学运算，同时注意保持每个数字不同模 n，就很容易生成一个看起来随机的排列。最好的部分是我们不需要任何内存来跟踪我们已经生成的数字，因为每个数字都是用一个简单的公式计算的。

---

我们可以对范围内的每个数字 x 执行的操作示例包括:

• 加法:我们可以将任何整数c加到x上。
• 乘法:我们可以将 x 与任何与 n 没有质因数的数 m 相乘。

仅在 0..n-1 范围内应用这两个操作已经给出了非常令人满意的结果:

>>> n = 7
>>> c = 1
>>> m = 3
>>> [((x+c) * m) % n for x in range(n)]
[3, 6, 2, 5, 1, 4, 0]

看起来很随意，不是吗？

如果我们从随机数生成 c 和 m，它实际上也是 随机的。但请记住，不能保证此算法会生成所有可能的排列，或者每个排列都有相同的生成概率。

---

实现

实现的困难部分实际上只是生成一个合适的随机 m。我使用了 this answer 中的质因数分解代码这样做。

import random

# credit for prime factorization code goes
# to https://stackoverflow.com/a/17000452/1222951
def prime_factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, next_ = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[next_]
        next_ += 1
        if next_ == length:
            next_ = cycle
    if n > 1: fs.append(n)
    return fs

def generate_c_and_m(n, seed=None):
    # we need to know n's prime factors to find a suitable multiplier m
    p_factors = set(prime_factors(n))

    def is_valid_multiplier(m):
        # m must not share any prime factors with n
        factors = prime_factors(m)
        return not p_factors.intersection(factors)

    # if no seed was given, generate random values for c and m
    if seed is None:
        c = random.randint(n)
        m = random.randint(1, 2*n)
    else:
        c = seed
        m = seed

    # make sure m is valid
    while not is_valid_multiplier(m):
        m += 1

    return c, m

现在我们可以为 c 和 m 生成合适的值，创建排列很简单:

def random_range(n, seed=None):
    c, m = generate_c_and_m(n, seed)

    for x in range(n):
        yield ((x + c) * m) % n

你的生成器函数可以实现为

def MyGenerator(foo, num):
    for x in random_range(num):
        if foo(x):
            yield x