我正在尝试编写一种算法,该算法 将从序列中随机选择N个不同的项目,而无需事先知道序列的大小,并且在一个以上的序列上进行多次迭代会很昂贵 。例如,序列的元素可能是一个巨大文件的行。
当N = 1(即“从巨大序列中随机选取一个元素”)时,我找到了一种解决方案:
import random items = range(1, 10) # Imagine this is a huge sequence of unknown length count = 1 selected = None for item in items: if random.random() * count < 1: selected = item count += 1
但是,对于其他N值(例如N = 3),我如何实现相同的目标呢?
使用储层取样。这是一个非常简单的算法,适用于任何算法N。
N
这是一个Python实现