随机数生成器，每次只返回一个数字

Question

Python是否有一个随机数生成器，每次调用next()函数时只返回一个随机整数值？编号不应该重复并且生成器应返回唯一的间隔[1, 1 000 000]中的随机整数。

我需要生成超过百万个不同的数字，这听起来好像它非常消耗内存，以防万一所有数字都在同一时间生成并存储在列表中。

Answer 1

您正在寻找一段完整的linear congruential generator。这将允许您在目标号码范围内获得非重复数字的伪随机序列。

实现一个LCG其实很简单，看起来像这样：

def lcg(a, c, m, seed = None): 
    num = seed or 0 
    while True: 
     num = (a * num + c) % m 
     yield num 

然后，它只是归结为选择正确的值a，c，并m以保证LCG将产生整个期间（这是唯一保证你得到非重复数字）。由于维基百科的文章介绍，以下三个条件必须是真实的：

1. m和c需要相对素数。
2. a - 1是的m
3. a - 1所有的质因数整除是被4整除，如果m也整除4.

第一个是很容易保证通过简单的选择一个主要的c。而且，这是最后可以选择的值，这最终可以让我们将序列混合一点。

虽然a - 1和m之间的关系更复杂。在整个LCG期间，m是期间的长度。换句话说，这是你的号码来自的数字范围。所以这就是你通常首先选择的东西。在你的情况下，你想m约1000000。选择准确的最大数字可能会很困难，因为这限制了你很多（在你选择的a和c），所以你也可以选择大于这个数字的数字，然后简单地跳过你范围之外的所有数字。

尽管现在我们选择m = 1000000。 m的主要因素是2和5。而且它也明显可以被4整除。因此，对于a - 1，我们需要一个数字为2 * 2 * 5的倍数以满足条件2和3.我们选择a - 1 = 160，所以a = 161。

对于c，我们使用的是随机引那是在我们的范围介于两者之间：c = 506903

把那到我们的LCG为我们提供了我们所期望的序列。我们可以选择范围内的任何种子值（0 <= seed <= m）作为我们序列的起点。

所以让我们试试看，并验证我们认为的实际工作。为了这个目的，我们只是收集来自发生器的所有数字，直到我们碰到一个副本。在这一点上，我们应该有m = 1000000号码设定：

>>> g = lcg(161, 506903, 1000000) 
>>> numbers = set() 
>>> for n in g: 
     if n in numbers: 
      raise Exception('Number {} already encountered before!'.format(n)) 
     numbers.add(n) 

Traceback (most recent call last): 
    File "<pyshell#5>", line 3, in <module> 
    raise Exception('Number {} already encountered before!'.format(n)) 
Exception: Number 506903 already encountered before! 
>>> len(numbers) 
1000000 

而且它是正确的！所以我们创建了一个伪随机数字序列，允许我们从我们的范围m获得非重复数字。当然，按照设计，这个序列总是相同的，所以当你选择这些数字时，它只是随机的。只要你保持上面提到的属性，你可以切换a和c的值来获得不同的序列。

---

这种方法的好处当然是你不需要存储以前生成的所有数字。这是一个恒定的空间算法，因为它只需要记住初始配置和以前生成的值。

随着您对序列的进一步了解，它也不会恶化。这是一个解决方案的一个普遍问题，它只是一直生成一个随机数，直到找到一个以前没有遇到的新数。这是因为生成的数字列表越长，您将不太可能用不均匀分布的随机算法命中不在该列表中的数字。所以获得第1000000个数字可能需要很长时间才能用基于内存的随机生成器生成。

但是，当然，仅仅执行一些乘法和一些加法的简单算法并不会显得非常随机。但是你必须记住，这实际上是大多数伪随机数生成器的基础。所以random.random()内部使用这样的东西。这只是m是很大，所以你没有注意到它。

Answer 2

import random 

# number of random entries 
x = 1000 

# The set of all values 
y = {} 
while (x > 0) : 
    a = random.randint(0 , 10**10) 
    if a not in y : 
     a -= 1 

这样，你确定你有完全随机的唯一值 x表示要

Answer 3

对于大量的非重复的随机数的使用加密值的数量。对于给定的密钥，加密数字：0,1,2,3 ...由于加密是唯一可逆的，因此每个加密的数字都保证是唯一的，只要您使用相同的密钥。对于64位数字使用DES。对于128位数字使用AES。对于其他尺寸数字，请使用某些格式保留加密。对于纯数字，您可能会发现Hasty布丁密码非常有用，因为它允许大范围的不同比特尺寸和非比特尺寸，例如[0..5999999]。

记录密钥和加密的最后一个数字。当你需要一个新的唯一的随机数时，只需要加密你到目前为止还没有使用过的下一个数字。

Answer 4

你可以很容易自己做一个：

from random import random 

def randgen(): 
    while True: 
     yield random() 


ran = randgen() 
next(ran) 
next(ran) 
... 

Answer 5

如果你真正关心的内存，你可以使用NumPy阵列（或一个Python array）。

int32（绰绰有余以包含0到1 000 000之间的整数）将只消耗约4MB，Python本身需要约36MB（每个整数约为28byte，每个列表元素约8个字节+过度分配），对于相同的列表：

>>> # NumPy array 
>>> import numpy as np 
>>> np.arange(1000000, dtype=np.int32).nbytes 
4 000 000 

>>> # Python list 
>>> import sys 
>>> import random 
>>> l = list(range(1000000)) 
>>> random.shuffle(l) 
>>> size = sys.getsizeof(l)       # size of the list 
>>> size += sum(sys.getsizeof(item) for item in l) # size of the list elements 
>>> size 
37 000 108 

你只需要独特的价值观和你有一个连续的范围内（100万个请求项目1万个不同的数字），那么你可以简单地洗牌的范围，然后从得到的物品你混洗阵列：

def generate_random_integer(): 
    arr = np.arange(1000000, dtype=np.int32) 
    np.random.shuffle(arr) 
    yield from arr 
    # yield from is equivalent to: 
    # for item in arr:  
    #  yield item 

它可以使用next被称为：

>>> gen = generate_random_integer() 
>>> next(gen) 
443727 

然而，将扔掉使用与NumPy的性能优势，所以如果你想使用NumPy的不与理会发电机，只是执行的操作（矢量化 - 如果可能的话）在数组上。它比Python消耗的内存少得多，它可能快几个数量级（速度快10-100倍并不罕见！）。

Answer 6

考虑到你的数字应该适合一个64位的整数，如果你的处理计算机能够承受最简单的方法是使用shuffle，那么其中一百万个存储在一个列表中的内容将高达64兆字节加上列表对象开销：

import random 
randInts = list(range(1000000)) 
random.shuffle(randInts) 
print(randInts) 

注意，另一种方法是跟踪先前生成的数字，这将让你让它们都存放过的点。