接N个项目随机地从未知长度的序列

本文介绍了接N个项目随机地从未知长度的序列的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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