如何優化加權隨機數產生的效率？

產生加權隨機數

加權隨機數產生涉及從一個範圍中選擇一個隨機數，其中每個數字的機率由重量。此任務出現在各種應用中，例如模擬和遊戲。

初始解決方案

常見的方法是拒絕取樣，如提供了 ColdFusion 程式碼。此方法涉及建立一個查找表，其中元素根據權重分佈。但是，這種方法有局限性，例如構建表的線性開銷和潛在的記憶體消耗問題。

替代策略

• 線性求和： 另一種策略涉及對權重進行迭代求和，直到總和超過[0 ,1) 範圍內隨機產生的數字。然後傳回關聯的值。這種方法沒有前期成本，但具有線性時間複雜度。
• 儲層取樣：此方法涉及從元素流中選擇隨機樣本。當遇到每個元素時，它會以與其重量成比例的機率添加到儲存器中。儲存庫大小保持固定，確保恆定的時間複雜度。
• 別名取樣：此技術利用預先計算的表格從加權分佈中選擇隨機數。它保證了恆定的時間複雜度，並且對於大的或高度傾斜的權重分佈通常比其他方法更有效。

實作

加權隨機的實作使用別名取樣在 JavaScript 中產生數字：

function weightedRand(weights) {
  // Build the alias table
  let table = [];
  let totalWeight = 0;
  for (let i = 0; i < weights.length; i++) {
    totalWeight += weights[i];
  }
  for (let i = 0; i < weights.length; i++) {
    let prob = weights[i] / totalWeight;
    let alias = i;
    table.push({ prob: prob, alias: alias });
  }
  
  // Generate a random number
  return function() {
    let r = Math.random() * totalWeight;
    let i = 0;
    let alias = -1;
    while (i < table.length && alias === -1) {
      if (r < table[i].prob) {
        alias = i;
      } else {
        r -= table[i].prob;
        i = table[i].alias;
      }
    }
    return alias;
  }
}

以上是如何優化加權隨機數產生的效率？的詳細內容。更多資訊請關注PHP中文網其他相關文章！