实现随机权重抽取多个元素的高效算法

实现随机权重抽取多个元素的高效算法通常涉及到概率分布和数据结构的结合。例如，可以使用“ reservoir sampling” 或 “weighted random sampling” 的变种。这里有一个基于 reservoir sampling 的简化版本：

1. **Reservoir Sampling**：这是一种在线（streaming）算法，适用于动态流数据。假设你有一个无限大的序列，并且每个元素都有一个独立的随机权重。你维护一个固定大小的“样本池”，每次从新来的元素中按照其权重随机选择一个替换池里的某个元素，直到收集到所需的元素数。

def weighted_reservoir_sampling(data, k, weights):
    pool_size = min(k, len(weights))
    reservoir = [None] * pool_size
    for i, (item, weight) in enumerate(zip(data, weights)):
        if i < pool_size:
            reservoir[i] = (item, weight)
        else:
            r = int(random.uniform(0, sum(weights[pool_size:i+1])))
            if r < weights[i]:
                reservoir[r] = (item, weight)
    return reservoir