如何在讀取數組時從數組中隨機選擇任意數量的元素

Question

我需要隨機地（以相同的概率）從文件中的數組中挑選一些固定數量的元素。我想讀取一次文件，只保留拾取的元素，因爲數組可能很長，我不想將它保存在內存中。應該有相同的概率選擇每個子陣列。而且在開始時我不知道數組的大小。

我該怎麼辦？

Answer 1

你需要一種叫做油藏採樣的東西。

它解釋得很好，在這個博客：

http://gregable.com/2007/10/reservoir-sampling.html

Answer 2

如果你不關心你正在拾取的元素的確切數量，一個簡單的解決方案是讀取文件並以固定的概率選取每個元素。

如果你想要一個確切的數字，你需要在讀取整個文件之前知道這個文件中有多少個元素，計算一個你想要的元素列表（作爲一個整數列表），然後讀取文件並選擇正確的元素。