从未知长度的序列中随机选取N个项目
我试图编写一个algorithm，从一个随机序列中selectN个不同的项目，而不必事先知道序列的大小，以及在不止一次遍历序列的过程中，花费的昂贵。 例如，序列的元素可能是一个巨大的文件的行。
当N = 1时，我find了一个解决scheme（也就是说，当试图从一个巨大的序列中随机挑选一个元素时）：
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）呢？
使用油藏采样 。 这是一个非常简单的algorithm，适用于任何N
这是一个Python实现， 这里是另一个。
如果你的序列足够短，将它读入内存并随机sorting是可以接受的，那么直接的方法就是使用random.shuffle ：
import random arr=[1,2,3,4] # In-place shuffle random.shuffle(arr) # Take the first 2 elements of the now randomized array print arr[0:2] [1, 3]
根据序列的types，您可能需要通过调用list(your_sequence)将其转换为列表，但是无论序列中的对象是什么types，都可以工作。
当然，如果你不能把你的序列放到内存中，或者这种方法的内存或CPU要求对你来说太高，你将需要使用不同的解决scheme。
以下将给你N个数组X的随机项
import random list(map(lambda _: random.choice(X), range(N)))
只要接受或拒绝每一个新项目就足够了，如果你接受，就扔掉一个随机select的旧项目。
假设你已经select了N个K项，你会看到第（K + 1）个项目。 以概率N /（K + 1）接受它，概率是可以的。 （N /（K + 1）） （1 / N）= 1 /（K + 1），以概率（N / K） K /（K + 1））= N /（K + 1），所以它们的概率也是可以的。
是的，我看到有人指出你的油藏采样 – 这是如何工作的一个解释。
@NPE是正确的，但被链接到的实现是次优的，不是很“pythonic”。 这是一个更好的实现：
def sample(iterator, k): """ Samples k elements from an iterable object. :param iterator: an object that is iterable :param k: the number of items to sample """ # fill the reservoir to start result = [next(iterator) for _ in range(k)] n = k - 1 for item in iterator: n += 1 s = random.randint(0, n) if s < k: result[s] = item return result
编辑为@pandas34指出原来的版本是有缺陷的，但不是因为我使用randint vs randrange 。 问题是，我的初始值没有考虑到randint包含在范围的两端的事实。 考虑到这个问题解决了这个问题。 （注意：你也可以使用randrange因为它包含在最小值上，而在最大值上是排它的。）
正如艾克斯提到的油藏采样工程。 另一个选项是为每个您看到的数字生成一个随机数，并select前k个数字。
迭代地做，保持一堆k（随机数，数字）对，每当你看到一个新的数字插入到堆中，如果它大于堆中的最小值。
这是我的一个重复问题的答案（closures之前，我可以发布）有点相关（“生成随机数字没有任何重复”）。 因为它是一个不同于其他答案的方法，所以我会把它留在这里以防止它提供更多的信息。
from random import randint random_nums = [] N = # whatever number of random numbers you want r = # lower bound of number range R = # upper bound of number range x = 0 while x < N: random_num = randint(r, R) # inclusive range if random_num in random_nums: continue else: random_nums.append(random_num) x += 1
for循环的while循环的原因在于它允许在随机生成中更容易地实现不跳过（即，如果得到3个副本，则不会得到N-3个数字）。
