隨機數生成器，每次只返回一個數字

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) 

注意，另一種方法是跟蹤先前生成的數字，這將讓你讓它們都存放過的點。