非常大范围的高效随机生成器（python）
Efficient random generator for very large range (in python)
我正在尝试创建一个生成器，它 returns 给定范围内的数字通过函数 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 将传递合理数量的数字和 [=19= 的总次数] 方法将被调用将相对较小（例如，最多 200 通常要小得多）。因此，我们很可能偶然发现一个通过 foo 测试的值，并且 tried 的大小永远不会变大。 （即使它只有 10% 的时间通过，我们也不会期望 tried 大致大于 2000。）
但是当num较小时（接近__next__方法被调用的次数，或者foo大部分时间都失败了，上面的解就变得很效率低下 - 随机猜测数字，直到它猜到一个不在 tried.
中的数字
我尝试的解决方案...
我希望使用某种函数以大致随机的方式将数字 0,1,2,..., n 映射到自身。 （这没有被用于任何安全目的，所以如果它不是世界上最多 'random' 的功能也没关系）。这里的函数 (Create a random bijective function which has same domain and range) 将带符号的 32 位整数映射到自身，但我不确定如何将映射调整到更小的范围。给定 num 我什至不需要在 0,1,..num 上进行双射，只需要 n 大于 'close' 到 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 的不同值进行概括？- 解决原始问题的更好方法？
非常感谢....
在这种情况下，最佳算法 取决于 num 的值，那么为什么不使用包含在一个生成器中的 2 个可选算法呢？
您可以将 shuffle 和 set 解决方案与 num 值的阈值混合使用。这基本上是在一个生成器中组装您的 2 个第一个解决方案：
from random import shuffle,randint
def MyGenerator(foo, num):
if num < 100000 # has to be adjusted by experiments
order = list(range(num))
shuffle(order)
for i in order:
if foo(i):
yield i
else: # big values, few collisions with random generator
tried = set()
while len(tried) < num:
i = randint(0, num-1)
if i in tried:
continue
tried.add(i)
if foo(i):
yield i
randint 解决方案（对于 num 的大值）效果很好，因为随机生成器中没有那么多重复。
问题基本上是在 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
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
在 Python 中获得最佳性能比在低级语言中要困难得多。例如，在 C 语言中，您通常可以通过用移位替换乘法来节省一些热内循环。 python bytecode-orientation 的开销消除了这一点。当然，当您考虑要针对 "python" 的哪个变体（pypy？numpy？cython？）时，这会再次改变 - 您 真的 必须根据您使用的代码编写代码。
但更重要的是安排操作以避免序列化依赖，因为如今所有 CPU 都是超标量的。当然，真正的编译器知道这一点，但在选择算法时它仍然很重要。
获得一些现有答案的最简单方法之一是使用 numpy.arange() 生成块中的数字并将 ((x + c) * m) % n 直接应用于 numpy ndarray。每个可以避免的 python 级循环都有帮助。
如果该函数可以直接应用于 numpy ndarrays，那可能会更好。当然，python 中足够小的函数无论如何都会被函数调用开销所支配。
当今最好的快速随机数生成器是 PCG. I wrote a pure-python port here，但更注重灵活性和易懂性，而不是速度。
Xoroshiro128+ 质量第二好，速度更快，但学习信息量较少。
Python（以及许多其他人）默认选择的 Mersenne Twister 是最差的。
（还有一个叫做splitmix64的东西我不太了解-有人说它比xoroshiro128+好，但它有一个周期问题-当然，你可能想要 这里)
default-PCG 和 xoroshiro128+ 都使用 2N 位状态来生成 N 位数字。这通常是可取的，但意味着数字将被重复。然而，PCG 有替代模式可以避免这种情况。
当然，这在很大程度上取决于num是否（接近）2的幂。理论上，可以为任何位宽创建PCG变体，但目前仅实现了各种字长因为你需要显式屏蔽。我不确定如何为新的位大小生成参数（也许它在论文中？），但可以通过执行 period/2 跳转并验证值是否不同来简单地测试它们。
当然，如果您只对 RNG 进行 200 次调用，您实际上可能不需要在数学方面避免重复。
或者，您可以使用 LFSR， 对每个位大小都存在（但请注意，它永远不会生成全零值（或等效地，全一值））。 LFSR 是串行的并且（AFAIK）不可跳转，因此不能轻易地跨多个任务拆分。编辑：我发现这是不正确的，只需将前进步骤表示为矩阵, 并取幂使其跳跃。
请注意，LFSR do 与简单地根据随机起点按顺序生成数字具有相同的明显偏差 - 例如，如果 rng_outputs[a: b] 都使您的 foo 函数失败，那么无论起点如何，rng_outputs[b] 都更有可能作为第一个输出。 PCG 的 "stream" 参数通过不以相同顺序生成数字来避免这种情况。
Edit2：我已经完成了我认为的 "brief project" 实施 LFSRs in python，包括跳跃，完全测试。
我正在尝试创建一个生成器，它 returns 给定范围内的数字通过函数 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 将传递合理数量的数字和 [=19= 的总次数] 方法将被调用将相对较小（例如，最多 200 通常要小得多）。因此，我们很可能偶然发现一个通过 foo 测试的值，并且 tried 的大小永远不会变大。 （即使它只有 10% 的时间通过，我们也不会期望 tried 大致大于 2000。）
但是当num较小时（接近__next__方法被调用的次数，或者foo大部分时间都失败了，上面的解就变得很效率低下 - 随机猜测数字，直到它猜到一个不在 tried.
我尝试的解决方案...
我希望使用某种函数以大致随机的方式将数字 0,1,2,..., n 映射到自身。 （这没有被用于任何安全目的，所以如果它不是世界上最多 'random' 的功能也没关系）。这里的函数 (Create a random bijective function which has same domain and range) 将带符号的 32 位整数映射到自身，但我不确定如何将映射调整到更小的范围。给定 num 我什至不需要在 0,1,..num 上进行双射，只需要 n 大于 'close' 到 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的不同值进行概括？- 解决原始问题的更好方法？
非常感谢....
在这种情况下，最佳算法 取决于 num 的值，那么为什么不使用包含在一个生成器中的 2 个可选算法呢？
您可以将 shuffle 和 set 解决方案与 num 值的阈值混合使用。这基本上是在一个生成器中组装您的 2 个第一个解决方案：
from random import shuffle,randint
def MyGenerator(foo, num):
if num < 100000 # has to be adjusted by experiments
order = list(range(num))
shuffle(order)
for i in order:
if foo(i):
yield i
else: # big values, few collisions with random generator
tried = set()
while len(tried) < num:
i = randint(0, num-1)
if i in tried:
continue
tried.add(i)
if foo(i):
yield i
randint 解决方案（对于 num 的大值）效果很好，因为随机生成器中没有那么多重复。
问题基本上是在 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
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
在 Python 中获得最佳性能比在低级语言中要困难得多。例如，在 C 语言中，您通常可以通过用移位替换乘法来节省一些热内循环。 python bytecode-orientation 的开销消除了这一点。当然，当您考虑要针对 "python" 的哪个变体（pypy？numpy？cython？）时，这会再次改变 - 您 真的 必须根据您使用的代码编写代码。
但更重要的是安排操作以避免序列化依赖，因为如今所有 CPU 都是超标量的。当然，真正的编译器知道这一点，但在选择算法时它仍然很重要。
获得一些现有答案的最简单方法之一是使用 numpy.arange() 生成块中的数字并将 ((x + c) * m) % n 直接应用于 numpy ndarray。每个可以避免的 python 级循环都有帮助。
如果该函数可以直接应用于 numpy ndarrays，那可能会更好。当然，python 中足够小的函数无论如何都会被函数调用开销所支配。
当今最好的快速随机数生成器是 PCG. I wrote a pure-python port here，但更注重灵活性和易懂性，而不是速度。
Xoroshiro128+ 质量第二好，速度更快，但学习信息量较少。
Python（以及许多其他人）默认选择的 Mersenne Twister 是最差的。
（还有一个叫做splitmix64的东西我不太了解-有人说它比xoroshiro128+好，但它有一个周期问题-当然，你可能想要 这里)
default-PCG 和 xoroshiro128+ 都使用 2N 位状态来生成 N 位数字。这通常是可取的，但意味着数字将被重复。然而，PCG 有替代模式可以避免这种情况。
当然，这在很大程度上取决于num是否（接近）2的幂。理论上，可以为任何位宽创建PCG变体，但目前仅实现了各种字长因为你需要显式屏蔽。我不确定如何为新的位大小生成参数（也许它在论文中？），但可以通过执行 period/2 跳转并验证值是否不同来简单地测试它们。
当然，如果您只对 RNG 进行 200 次调用，您实际上可能不需要在数学方面避免重复。
或者，您可以使用 LFSR， 对每个位大小都存在（但请注意，它永远不会生成全零值（或等效地，全一值））。 LFSR 是串行的并且（AFAIK）不可跳转，因此不能轻易地跨多个任务拆分。编辑：我发现这是不正确的，只需将前进步骤表示为矩阵, 并取幂使其跳跃。
请注意，LFSR do 与简单地根据随机起点按顺序生成数字具有相同的明显偏差 - 例如，如果 rng_outputs[a: b] 都使您的 foo 函数失败，那么无论起点如何，rng_outputs[b] 都更有可能作为第一个输出。 PCG 的 "stream" 参数通过不以相同顺序生成数字来避免这种情况。
Edit2：我已经完成了我认为的 "brief project" 实施 LFSRs in python，包括跳跃，完全测试。