如何有效率地進行加權隨機選擇和替換？

帶替換和不帶替換的加權隨機選擇

從列表中選擇帶或不帶替換的隨機元素是編程中的常見任務。雖然已建立了未加權選擇和無需替換的加權選擇的方法，但選擇替換的加權元素提出了獨特的挑戰。

取代加權選擇的別名方法

一個對於這種情況，最有效的方法是 Alias 方法。它涉及創建有效表示加權清單的相同大小的 bin。

實現步驟：

1. 標準化權重：調整權重，以便它們的總和為 1.0，代表選擇機率。
2. 建立分區：確定大於元素數量的最小 2 次冪並建立那麼多分區。
3. 分配權重：將權重最小的元素放置在空分區中，盡可能填充它。
4. 填滿分區：如果分區未滿，則添加具有最高權重的元素來填充剩餘空間。
5. 重複：繼續分配權重，直到所有元素都被考慮在內。

運行時選擇：

1. 產生一個 0 到 1 之間的隨機數。
2. 按分區數的對數對數字進行位移（假設位移在您的平台上很快） ).
3. 如果分區被分割，則使用移位數的小數部分來決定選擇哪個元素。

別名方法的優點：

• 透過替換進行快速且有效率的選擇。
• 避免使用儲庫方法進行大量選擇。
• 實現簡單且記憶體高效。

以上是如何有效率地進行加權隨機選擇和替換？的詳細內容。更多資訊請關注PHP中文網其他相關文章！