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

Question

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

Answer 1

使用储层取样。这是一个非常简单的算法，适用于任何算法N。这是一个Python实现，这是另一个。

Answer 2

如果您的序列足够短，以至于可以将其读入内存并对其进行随机排序，那么一种简单的方法就是使用random.shuffle：import randomarr=[1,2,3,4]# In-place shufflerandom.shuffle(arr)# Take the first 2 elements of the now randomized arrayprint arr[0:2][1, 3]根据序列的类型，您可能需要通过调用将其转换为列表list(your_sequence)，但是不管序列中对象的类型如何，此方法都可以工作。自然，如果您无法将序列适合内存，或者此方法对内存或CPU的要求过高，则需要使用其他解决方案。

Answer 3

import randommy_list = [1, 2, 3, 4, 5]num_selections = 2new_list = random.sample(my_list, num_selections)# To preserve the order of the list, you could do:randIndex = random.sample(range(len(my_list)), n_selections)randIndex.sort()new_list = [my_list[i] for i in randIndex]