小编典典

仅一次迭代即可从未知长度的序列中随机选择N个不同的项目

algorithm

我正在尝试编写一种算法,该算法 将从序列中随机选择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),我如何实现相同的目标呢?


阅读 262

收藏
2020-07-28

共1个答案

小编典典

使用储层取样。这是一个非常简单的算法,适用于任何算法N

是一个Python实现

2020-07-28