加權隨機 (Weighted Random) 讓不同選項依權重機率被抽中,適用於「抽餐廳 (想去的店權重高)」、「遊戲掉寶 (稀有度權重低)」、「廣告輪播 (曝光權重)」等場景。本文提供可重複使用的泛型 `WeightedRandom
public class WeightedRandom<T> {
private readonly List> _items = new();
private readonly List _prefixSum = new(); // 前綴和陣列
private readonly Random _rng = new Random();
public void Add(T item, int weight) {
if (weight < 1) throw new ArgumentException("權重必須 >= 1");
_items.Add(new WeightedItem { Item = item, Weight = weight });
_prefixSum.Add(_prefixSum.Count == 0 ? weight : _prefixSum.Last() + weight);
}
public T Next() {
if (_items.Count == 0) throw new InvalidOperationException("集合為空");
int total = _prefixSum.Last();
int roll = _rng.Next(total); // 0 ~ total-1
int idx = _prefixSum.BinarySearch(roll);
if (idx < 0) idx = ~idx; // BinarySearch 回傳 bitwise complement of next larger
return _items[idx].Item;
}
public void Clear() { _items.Clear(); _prefixSum.Clear(); }
public int Count => _items.Count;
public int TotalWeight => _prefixSum.Count > 0 ? _prefixSum.Last() : 0;
private class WeightedItem { public TItem Item; public int Weight; }
}
<%@ Page Language="C#" AutoEventWireup="true" CodeBehind="Default.aspx.cs" Inherits="WeightedRandomDemo.Default" %>
<!DOCTYPE html>
<html><head><title>加權隨機抽獎</title>
<style> body {font-family:Microsoft JhengHei; padding:20px;} .result {margin-top:20px; font-size:1.2em; color:#d00;} </style></head>
<body>
<form id="form1" runat="server">
<h2>加權隨機抽獎示範</h2>
<div>
迭代次數: <asp:TextBox ID="txtIterations" runat="server" Text="100" Width="60px" />
<br />
public partial class Default : Page {
private readonly WeightedRandom _gearRandom = new WeightedRandom();
private readonly WeightedRandom _foodRandom = new WeightedRandom();
protected void Page_Load(object sender, EventArgs e) {
if (!IsPostBack) InitData();
}
private void InitData() {
// 裝備池 (夢三國範例)
_gearRandom.Add("寒冰爪 (神器)", 2);
_gearRandom.Add("重毛皮", 300);
_gearRandom.Add("小毛皮", 1000);
_gearRandom.Add("輕毛皮", 1000);
_gearRandom.Add("神之防具打造書", 5);
_gearRandom.Add("傳說武器打造書", 20);
_gearRandom.Add("紫檀樹枝", 300);
_gearRandom.Add("硬毛皮", 600);
_gearRandom.Add("勾魂水晶", 8);
// 餐廳池
_foodRandom.Add("滷肉飯", 50);
_foodRandom.Add("牛肉麵", 40);
_foodRandom.Add("壽司", 20);
_foodRandom.Add("火鍋", 30);
_foodRandom.Add("便當", 60);
}
protected void btnGear_Click(object sender, EventArgs e) => RunDraw(_gearRandom, "裝備");
protected void btnFood_Click(object sender, EventArgs e) => RunDraw(_foodRandom, "餐廳");
private void RunDraw(WeightedRandom rnd, string label) {
int times = int.TryParse(txtIterations.Text, out int t) ? t : 100;
var stats = new Dictionary();
for (int i = 0; i < times; i++) {
string item = rnd.Next();
stats[item] = stats.GetValueOrDefault(item) + 1;
}
var sb = new StringBuilder();
sb.AppendLine($"{label} 抽獎結果 ({times} 次)
項目 權重 實際次數 實際機率 理論機率 ");
int totalW = rnd.TotalWeight;
foreach (var kv in stats.OrderByDescending(k => k.Value)) {
double actual = (double)kv.Value / times * 100;
double theory = (double)GetWeight(rnd, kv.Key) / totalW * 100;
sb.AppendLine($"{kv.Key} {GetWeight(rnd, kv.Key)} {kv.Value} {actual:F2}% {theory:F2}% ");
}
sb.AppendLine("
");
litResult.Text = sb.ToString();
}
private int GetWeight(WeightedRandom rnd, string item) {
// 簡易反查,實際專案建議保留 Dictionary
return 1; // 略
}
protected void btnClear_Click(object sender, EventArgs e) => litResult.Text = "";
}
| 演算法 | 建構 | 取樣 | 動態增刪 | 適用場景 |
|---|---|---|---|---|
| 前綴和 + 二分搜尋 | O(n) | O(log n) | O(n) 需重建 | 靜態/低頻變動池 (推薦) |
| 別名法 | O(n) | O(1) | 困難 | 極高頻取樣、固定池 |
| 線性掃描 (累加) | O(1) | O(n) | 容易 | 項目極少 (<20) 或頻繁增刪 |
public void UpdateWeight(T item, int newWeight) {
int idx = _items.FindIndex(i => EqualityComparer.Default.Equals(i.Item, item));
if (idx < 0) throw new KeyNotFoundException();
int diff = newWeight - _items[idx].Weight;
_items[idx].Weight = newWeight;
for (int i = idx; i < _prefixSum.Count; i++) _prefixSum[i] += diff;
}
若多執行緒共用實例,請鎖定 `_rng` 並使用 `ThreadLocal
加權隨機演算法簡單卻強大,封裝為泛型類別後即可在任何 .NET 專案 (Web/Console/Service) 重複使用,快速實作各類抽獎、機率遊戲、負載均衡選節點等功能。