适用于很大范围的高效随机生成器（在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以一种大致随机的方式将数字映射到自己。（这并不是用于任何安全目的，因此，如果它不是世界上最“随机”的功能，也没关系）。这里的函数（创建一个具有相同域和范围的随机双射函数）将带符号的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与m不共享素数的任何数字相乘n。

仅将这两个操作应用于范围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从一个随机数，它会实际上 是
随机的，太。但是请记住，不能保证此算法将生成所有可能的排列，也不保证每个排列具有相同的生成概率。

关于实现的困难部分实际上只是生成合适的random
m。我使用了这个答案中的素数分解代码。

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