快速隨機選擇算法

給定一個真/假值數組，什麼是最有效的算法來隨機選擇一個真值的索引。快速隨機選擇算法

草圖簡單的算法是

a <- the array 
c <- 0 
for i in a: 
    if a[i] is true: c++ 
e <- random number in (0, c-1) 
j <- 0 
for i in e: 
    while j is false: j++ 
return j

誰能想出一個更快的算法？也許有一種方法只能遍歷列表中的一次，即使最初不知道真正元素的數量？

來源

2009-12-03 momeara

只是想知道，在哪些應用程序中使用了這些類型的算法？前一段時間，我遇到了類似的問題，給定了一個無限大小的數組，前n個地方都填滿1，剩下的都是零。現在這個數組被賦予給一個新用戶（不知道n的值）。現在找出一個算法來標記最後1位的地方。這我通過二分查找解決。請給出一些使用它們的例子。 – avd 2009-12-03 15:33:45

近似重複：http://stackoverflow.com/questions/1133942/what-is-the-most-efficient-way-to-pick-a-random-card-from-a-deck-when-some-cards。在這個問題中，數組大小爲52，但是，這可能會影響答案（例如，您非常確定52號文件適合內存，而'a'可能不適合）。 – 2009-12-03 15:40:33

使用「從無限列表中選擇隨機元素」算法。

保留當前選擇的索引，並計算您已經看到多少真實值。

當您看到一個真值時，遞增計數，然後用P =（1/count）的概率替換您的選擇與當前索引。（所以你總是挑你發現第一個...那麼你威力切換到第二個，概率爲1/2，那麼你威力切換到第三個與probabilty 1/3等）

這隻需要對列表和恆定存儲進行一次掃描。（然而，它確實需要你計算大量的隨機數）。特別是，它永遠不會要求你緩衝列表或返回到開始 - 所以它可以在無界輸入流上工作。

請參閱this answer瞭解簡單的「挑選隨機元素」算法的示例LINQ實現;它只需要很小的調整。

來源

2009-12-03 15:32:06

更多的細節和證明在這裏：http://stackoverflow.com/questions/1133942/what-is-the-most-efficient-way-to-pick-a-random-card-from-a-deck-當-一些卡/ 1134286＃1134286。這個問題在功能上是該問題的一個重複，雖然措辭有點不同。我的直覺是，假設數據在內存中，它最有可能比兩遍算法慢。但值得測試的是，無論出於何種原因，雙程表現都是不可接受的。 – 2009-12-03 15:37:42

@Steve：它取決於「真實」值與產生隨機數的成本的稀疏性。如果列表中有一百萬條記錄，其中只有兩條是「真實的」，那麼這很可能是一場勝利。另一方面，如果您有一百萬個條目*全部*是真實的，那麼兩遍算法可能會更快。一般來說，我只是喜歡一次傳遞常量存儲算法的優雅:) – 2009-12-03 15:44:50

嘿，我只是對約翰內斯的答案提出了關於稀疏性的相同評論。我也同意優雅，儘管我稍微擔心使用大量隨機數字會使分析RNG中任何弱點的影響變得更加困難。 – 2009-12-03 15:50:05

構建一個列表，索引指向true值，然後從中隨機選擇一個。需要O（n）進行列表遍歷，並嘗試一次隨機數。

來源

2009-12-03 15:27:31 Joey

雖然它使用O（n）工作空間，但我的工作空間不變，這當然比我想出來的要快。所以仍有可能有改進的餘地。 – momeara 2009-12-03 15:34:15

它當然更快嗎？如果真正的價值非常罕見，那麼它幾乎肯定會更快。如果虛假值非常罕見，那麼它幾乎肯定會變慢。盈虧平衡點在哪裏，我不知道。 – 2009-12-03 15:45:26

是的，當然，真/假值的分佈對於哪個算法更高效的問題確實很重要。但是，如果不知道所有投注都像往常一樣關閉。不過，我發現喬恩的回答非常好，可能會比這更好。 – Joey 2009-12-03 15:52:08

快速隨機選擇算法

回答

相關問題