适用于非常大范围的高效随机发生器(在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从一个随机数,它会实际上是随机的,太.但请记住,无法保证此算法将生成所有可能的排列,或者每个排列具有相同的生成概率.

履行

关于实现的困难部分实际上只是生成一个合适的随机数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