閱讀和洗牌數組會涉及大量不必要的數據移動。
這裏有一些想法:
一:當你說你需要一個隨機子集,你到底在這方面的意思是「隨機」?我的意思是,記錄是以任何特定的順序出現的,還是與您試圖隨機化的相關的順序?
因爲我的第一個想法是,如果記錄沒有任何相關的順序,那麼您可以通過簡單計算總大小除以樣本大小,然後選擇每個第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%,所以我們將保證採取下一條記錄。
來源
2011-09-20 16:47:19
Jay
你如何交換)? I/O是瓶頸還是洗牌?也許有些代碼也會有幫助。 – delnan
@delnan我嘗試了鏈接線程上描述的兩種方法。 I/O絕對不是問題。它很快加載到內存中,但隨後在洗牌步驟花費大量時間。它永遠不會完成並開始打印。現在我已經嘗試過了,我認爲洗牌方法對於這麼多值不會有足夠的效率,所以我可能對替代方法更感興趣。 –
你需要的數據是隨機的嗎?您可能可以使用循環,通過隨機標記進行跳轉,然後在檢索後將該元素標記爲「已使用」以防止出現重複。 –