我试图写一个算法,将随机挑选一个序列N个不同的项目,不知道该序列的大小提前,以及它是昂贵的遍历序列超过一次。例如,该序列中的元素可能是一个巨大的文件的行
I am trying to write an algorithm that would pick N distinct items from an sequence at random, without knowing the size of the sequence in advance, and where it is expensive to iterate over the sequence more than once. For example, the elements of the sequence might be the lines of a huge file.
我已经找到了解决办法,当N = 1(即,试图从一个巨大的顺序挑选一个元素是随机的时候):
I have found a solution when N=1 (that is, when trying to pick exactly one element at random from a huge sequence):
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)?
But how can I achieve the same thing for other values of N (say, N=3)?
推荐答案使用水库取样。这是一个非常简单的算法,适用于任何 N 。
Use reservoir sampling. It's a very simple algorithm that works for any N.
Here一个Python实现,并 是另一回事。
Here is one Python implementation, and here is another.
更多推荐
接N个项目随机地从未知长度的序列
发布评论