我正在尝试创建一个发电机，该发电机返回给定范围内的数字，该数字传递了函数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上进行两次试验，仅比num大的n值(使用您认为合适的关闭定义(。然后我可以做以下操作：
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的不同值？
？
- 解决原始问题的更好方法？
非常感谢....
问题基本上是在0..n-1范围内生成整数的随机置换。
对我们来说幸运的是，这些数字具有非常有用的属性：它们都具有独特的值模型n。如果我们可以将一些数学操作应用于这些数字，同时小心地保持每个数字不同的模型n，则很容易生成出现随机的排列。最好的部分是，我们不需要任何内存来跟踪我们已经生成的数字，因为每个数字都是用简单的公式计算的。
操作示例我们可以在该范围内的每个数字上执行x包括：
-
加法：我们可以将任何整数
c添加到x。 -
乘法：我们可以使用任何数字
m乘以CC_31，该数字与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，则它实际上也将 be 随机。但是请记住，不能保证该算法会产生所有可能的排列，或者每个排列的可能性相同。
实施
有关实现的困难部分实际上只是生成合适的随机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
可能是最好的算法取决于 num的值，那么为什么不使用2个包裹在一个生成器中的2个可选算法？
您可以将shuffle和set解决方案与num的阈值混合。这基本上是在一个发电机中组装您的两个第一个解决方案：
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的较大值(效果很好，因为随机发电机中的重复次数不多。
在Python中获得最佳性能要比低级语言要棘手。例如，在C中，您通常可以通过换档替换乘法来节省热内循环。python字节码方向的开销消除了这一点。当然，这再次更改当您考虑" python"的哪个变体(pypy？numpy？cython？(？您正在使用哪一个。
，但更重要的是安排操作以避免串行依赖性，因为如今所有CPU都是超级标准。当然，真正的编译器知道这一点，但是当选择算法时，仍然很重要。
通过使用numpy.arange((在块中生成数字并将((x + c) * m) % n直接应用于numpy ndarray，这是通过在块中生成数字的最简单方法之一。每个可以避免的python级循环有帮助。
如果该函数可以直接应用于numpy ndarrays，则可能会更好。当然，无论如何，Python中的足够小的功能将由函数通话开销主导。
今天最好的快速随机数发电机是PCG。我在这里写了一个纯净的python港口，但专注于灵活性和易于理解而不是速度。
xoroshiro128 是第二高的质量，更快，但学习信息较少。
python's(以及许多其他'(默认选择Mersenne Twister是最糟糕的。
(还有一些叫做SplitMix64的东西，我不知道要放置的东西 - 有人说它比Xoroshiro128 更好，但是它有一个时期问题 - 当然，您可能想要想要(
default-pcg和xoroshiro128 使用2n位状态生成n位数字。这通常是可取的，但意味着数字将被重复。PCG具有避免这种情况的替代模式。
当然，这大部分取决于num是否是(接近(2的功率。从理论上讲，可以为任何位宽度创建PCG变体，但是目前仅实现各种单词大小，因为您需要显式掩蔽。我不确定如何确切地生成新的位尺寸的参数(也许是在纸上？(，但是只需进行段/2的跳转即可通过验证该值不同。
当然，如果您只对RNG拨打200个电话，则实际上您可能不需要避免在数学方面进行重复。
另外，您可以使用一个LFSR，该LFSR在每个位大小都存在 dim (尽管请注意，它永远不会生成全Zeros值(或等效地，All-Eons值((。 lfsr是串行的，(afaik(不可跳，因此不能轻易在多个任务上分开。 edit：我发现这是不真实的，只需将前进步骤表示为矩阵，然后指出它跳。
请注意，LFSRS do 具有与简单基于随机起始点以顺序生成数字相同的明显偏差 - 例如，如果RNG_OUTPUTS [a：b]都失败了，则您的foo函数失败，然后无论起点如何，rng_outputs[b]都会更有可能是第一个输出。PCG的"流"参数可以通过不以相同顺序生成数字来避免这种情况。
edit2：我已经完成了我认为在Python中实现LFSR的"简短项目"，包括跳跃，经过全面测试。