接N个项目随机地从未知长度的序列 [英] Pick N items at random from sequence of unknown length

问题描述

我试图写一个算法，将随机挑选一个序列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.

<一个href="http://data-analytics-tools.blogspot.com/2009/09/reservoir-sampling-algorithm-in-perl.html">Here一个Python实现，并 是另一回事。

Here is one Python implementation, and here is another.

这篇关于接N个项目随机地从未知长度的序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！