萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 加權隨機選擇算法:兩種高效實現方案

問題定義

給定字典 {'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()。
  • 權重動態變化時,考慮分段樹或 Fenwick Tree 實現 O(log n) 更新與查詢。
copyright © 萬盛學電腦網 all rights reserved