我有一個數據文件，其中有大量的值（53,000,000+），我想抽出這些值（比如2,000,000）的隨機子集n。我實現了一個將列表拖入內存的Perl腳本，使用Fisher-Yates method對數組進行混洗，然後在混洗列表中輸出第一個和值。然而，即使在更小的測試集（50,000個值）上，該洗牌過程也會花費大量的時間。從一個巨大的清單中進行有效的隨機抽樣
我正在尋找更高效，可擴展的方式來識別一組巨大的值的隨機子集並打印出來。有什麼建議麼？
更新：根據答案和一些更多的搜索，它看起來像正確的術語是「隨機抽樣」。
在上面的aix的回答中詳細說明，要從項目流中選擇k，請一次一個地讀取項目。將第一個k項目保留在一組S中。
現在讀m個項目I（m>k現在）時，使之與概率k/m。如果確實保留，請從S隨機選擇一個項目U，並用I替換U。
證明這產生所有子集的大小爲k等概率是基於對m的歸納。請注意，您無需事先知道n（項目總數），並且每個步驟中的S都適用。該算法是「流式傳輸」 - 它不需要存儲所有項目，或者進行第二遍。
這是一個在線算法，非常適合未知大小的流。但大小在這裏是已知的，所以你可以做得比 –
好，你可以做得更好，因爲當你預先知道n時，你需要減少對隨機數發生器的調用（k而不是n），並且你可以存儲在內存中設置。時間複雜性，兩者都是O（n），並且在線算法使用O（1）空間，而不是\ Theta（n） – adnan
nope，如果該集合已經在內存中，則時間複雜度僅爲O（k） 。如果沒有，那麼這是一個記憶vs速度的折衷，所以從這個意義上說，你是對的。 –
首先，檢查你的shuffle的實現。如果實施正確，應該給你線性時間。此外，修改算法以在所需數量的元素被洗牌後停止：不需要（實際上和理論上）洗牌比您實際輸出更多的數字。
如果你問k個數字，這會花費你k元素的操作。我懷疑你可以做得比這更好。
這是最好的算法，如果你有足夠的內存 –
不要洗牌，這是不必要的昂貴。
在Jon Bentley的"Programming Pearls"中討論過simple linear algorithm（賓利說他從Knuth的"Seminumerical Algorithms"瞭解到）。改用此方法。
有一些Perl implementations約：
這兩個片段來自Knuth的藝術編程實現Algortihm S（3.4.2）和Algortihm R（3.4.2） 。第一個從元素數組中隨機選擇N個項目 ，並返回對包含元素的數組 的引用。請注意，它不一定會考慮 列表中的所有元素。
第二個從不確定大小的文件 中隨機選擇N個項目，並返回包含所選元素的數組。 文件中的記錄被假定爲每行，並且行被讀取，而 讀取。這隻需要1次通過列表。輕微 修改，可向使用情況的片段，其中N 記錄將超過內存限制，但是這需要 略多於1通（/味精，如果你需要這個解釋）
閱讀和洗牌數組會涉及大量不必要的數據移動。
這裏有一些想法：
一：當你說你需要一個隨機子集，你到底在這方面的意思是「隨機」？我的意思是，記錄是以任何特定的順序出現的，還是與您試圖隨機化的相關的順序？
因爲我的第一個想法是，如果記錄沒有任何相關的順序，那麼您可以通過簡單計算總大小除以樣本大小，然後選擇每個第n條記錄來獲得隨機選擇。例如，如果你有5300萬條記錄，而你想要200萬的樣本，則需要5300萬/ 200萬〜26，所以每26條記錄讀一遍。
二：如果這還不夠，更嚴格的解決方案是生成200萬個隨機數，範圍在0到5300萬之間，確保沒有重複。 2-A：如果你的樣本量與總記錄數相比很小，就好像你剛剛挑選了幾百或幾千個樣本一樣，我會生成一個包含很多條目的數組，併爲每個條目，將其與以前的所有條目進行比較以檢查重複項。如果它是重複的，請循環並重試，直到找到唯一值。
2-B：假設你的數字不僅僅是實例而是實際值，那麼你的樣本量與總人口相比是很大的。在那種情況下，考慮到現代計算機上有足夠的內存，您應該能夠通過創建一個5300萬個布爾值的數組來初始化爲false來實現這一點，當然每個布爾值代表一個記錄。然後運行200萬次循環。對於每次迭代，生成一個從0到53百萬的隨機數。檢查數組中相應的布爾值：如果爲false，則將其設置爲true。如果確實如此，則生成另一個隨機數並重試。
三：或者等等，給出相對較大的百分比，這裏有一個更好的主意：計算你想包括的記錄的百分比。然後循環遍歷所有記錄的計數器。對於每一個，生成從0到1的隨機數並將其與所需的百分比進行比較。如果更少，請閱讀該記錄並將其包含在樣本中。如果更大，請跳過該記錄。
如果確定樣本記錄的確切數量很重要，則可以重新計算每條記錄的百分比。例如 - 爲了保持簡單的例子，讓我們假裝你想要100條記錄中的10條：
你會以10/100 = .1開頭所以我們生成一個隨機數，比方說它出現.04。 .04 <.1，所以我們包含了記錄＃1。
現在我們重新計算百分比。我們還需要99個剩餘的9個記錄給出9/99〜= .0909說我們的隨機數是.87。這是更大的，所以我們跳過第2條記錄。
再次重新計算。我們仍然需要98個剩餘的9個記錄。所以魔術數字是9/98，無論如何。等等
一旦我們獲得了儘可能多的記錄，未來記錄的概率將爲零，所以我們永遠不會過去。如果我們接近尾聲並沒有拿到足夠的記錄，概率將會非常接近100％。就像，如果我們仍然需要8條記錄，而只剩下8條記錄，概率將會是8/8 = 100％，所以我們將保證採取下一條記錄。
你如何交換）？ I/O是瓶頸還是洗牌？也許有些代碼也會有幫助。 – delnan
@delnan我嘗試了鏈接線程上描述的兩種方法。 I/O絕對不是問題。它很快加載到內存中，但隨後在洗牌步驟花費大量時間。它永遠不會完成並開始打印。現在我已經嘗試過了，我認爲洗牌方法對於這麼多值不會有足夠的效率，所以我可能對替代方法更感興趣。 –
你需要的數據是隨機的嗎？您可能可以使用循環，通過隨機標記進行跳轉，然後在檢索後將該元素標記爲「已使用」以防止出現重複。 –