給定字典 {'A':2, 'B':2, 'C':4, 'D':10, 'E':20},值代表權重。需實現函式 weighted_choice(data),按權重比例隨機返回鍵。例如 E 被選中機率應為 20/(2+2+4+10+20) ≈ 54%。
import random
def list_method(weights):
"""將元素按權重展開為列表,隨機選索引"""
expanded = []
for item, weight in weights.items():
expanded.extend([item] * weight)
return random.choice(expanded)
優點:實現簡單、random.choice 為 O(1)。
缺點:權重大、元素多時記憶體佔用大(O(總權重))。
import random
import bisect
def weighted_choice(weights):
"""基於前綴和與二分查找的加權隨機選擇"""
items = list(weights.keys())
prefix_sums = []
total = 0
for w in weights.values():
total += w
prefix_sums.append(total)
r = random.random() * total # [0, total)
idx = bisect.bisect_left(prefix_sums, r)
return items[idx]
優點:記憶體 O(n)、查找 O(log n)、無浮點誤差風險。
適用:大權重、高頻調用、記憶體敏感場景。
def iter_method(weights):
total = sum(weights.values())
r = random.uniform(0, total)
cumsum = 0
for item, weight in weights.items():
cumsum += weight
if r <= cumsum:
return item
時間 O(n),無需額外空間,適合元素較少(<100)的情況。
import timeit
weights = {f'item_{i}': i+1 for i in range(1000)} # 1000 項,權重 1~1000
print('列表法:', timeit.timeit(lambda: list_method(weights), number=1000))
print('迭代法:', timeit.timeit(lambda: iter_method(weights), number=1000))
print('二分法:', timeit.timeit(lambda: weighted_choice(weights), number=1000))
預期結果:列表法最慢(記憶體分配)、迭代法中等、二分法最快(大數據量時)。
numpy.random.choice (支援 p 參數) 或 random.choices (Python 3.6+ 內建支援權重)。random.seed()。