從N個記錄的文件中隨機選擇M個記錄

-1

需要從N個記錄（N> M）的文件中隨機選擇M個記錄（表示文件中的每個記錄具有相同的選擇概率）。想知道是否有隻讀文件的解決方案？從N個記錄的文件中隨機選擇M個記錄

我認爲唯一的方法是以M/N的概率選擇每條記錄，但這種方式可能導致M或M以上的記錄。

任何更聰明的想法，讚賞。

問候，林

來源

2016-05-23 Lin Ma

你可能需要的是油藏採樣算法（link）。

不僅它承認您以相同的概率準確獲取M條記錄，而且您只需要只讀取一次輸入，而不需要事先知道N.

複雜性是O（N）。

來源

2016-05-23 06:10:43 Sorin

感謝索林，看起來很聰明，在閱讀更多細節之前先投票。 :) –

嗨索林，研究了算法，並在您提到的維基百科頁面中得出了這個結論 - 「對於我來說，S的第i個元素被選擇包含在水庫中，概率爲k/i。」，我的困惑是因爲對於前k個元素，它被預先填充到庫中，與S中剩餘的元素相比，S的前k個元素是否具有相等的被包括的概率？謝謝。 –

是的，他們有相同的概率。那是因爲它們可以被後來的元素所取代。假設你有一個'k = 1'的庫。所以第一個元素留在水庫中的概率（因爲你默認添加它）就是1/N（你想要的）的乘積（i = 2-> N; 1-1/i）。你應該得到更一般情況下的k/N。你可以對以後的元素進行相同的計算，它們都應該以k/N爲單位。這在整個運行過程中都是如此。所以如果你在中間停下來，那麼水庫將保持迄今爲止所見元素的平等概率樣本。 – Sorin

選擇M獨特隨機數，把它們放在一個數組，對它們進行排序，然後讀取文件中的一次。當你在文件的i記錄中讀取時，如果i在數組中，則保留它，否則丟棄它。這需要O(M)內存，並且正在運行時間O(N + M log M)。

來源

2016-05-23 05:57:21 TheGreatContini

超級聰明，真棒TheGreatContini！ –

在時間允許的情況下投票並將答覆標記爲答案。你回答的太快了。涼。 :) –

順便說一下，TheGreatContini，如果我不知道文件的大小是否重要？謝謝。 –

從N個記錄的文件中隨機選擇M個記錄

回答

相關問題