加權隨機選擇和替換的合適方法是什麼？

加權隨機選擇：克服替換限制

最近，許多開發者都遇到了從清單中加權隨機選擇元素的挑戰，既有和沒有更換。雖然存在未加權選擇和無替換加權選擇的有效演算法，但事實證明，為具有替換的加權選擇找到合適的解決方案很困難。

一種實現高效和簡單的創新方法是別名方法。它的工作原理是為加權清單創建相同大小的箱。這些 bin 使用位元操作有效地索引，避免了耗時的二進位搜尋。

要形成別名查找表：

1. 將權重歸一化為1.0（例如，從(1 , 1, 1, 1, 1) 到(0.2, 0.2, 0.2 , 0.2, 0.2))。
2. 確定大於或等於變數數量的最小 2 次冪並建立該數量的分區。在我們的五個選擇的範例中，我們將建立八個分區。
3. 將最小的剩餘權重分配給空分區（例如，分區 1 的權重為 0.075）。
4. 如果分區未滿，也為其分配最大權重（例如，分區 2 現在的權重為 0.075 和 0.15）。

重複步驟 3 和 4，直到分配所有原始權重。

期間運行時：

1. 產生 [0, 1] 範圍內的隨機數（例如 0.001100000）。
2. 將隨機數移位 log2(num_partitions) 以找到相關分區 (例如，001.1 對應到分區 2)。
3. 如果分區被分割，則使用移位隨機數的小數部分來決定分割。

此方法有效地處理加權隨機透過替換進行選擇，與基於儲存庫的方法相比，可顯著提高效能，尤其是在選擇清單的大部分時。

以上是加權隨機選擇和替換的合適方法是什麼？的詳細內容。更多資訊請關注PHP中文網其他相關文章！