从未知长度的序列中随机选择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

如果您的序列足够短以便将其读入内存并随机排序它是可以接受的,那么直接的方法就是使用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]

根据序列的类型,您可能需要通过调用list(your_sequence)它将其转换为列表,但无论序列中的对象类型如何,这都将起作用.

当然,如果您无法将序列放入内存或者此方法的内存或CPU要求对您来说太高,则需要使用不同的解决方案.

Answer 2

使用水库采样.这是一个非常简单的算法,适用于任何N.

这是一个Python实现,这是另一个.

Answer 3

最简单的我在SO中找到了这个答案:

import random

my_list = [1, 2, 3, 4, 5]
num_selections = 2

new_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]

Answer 4

如果你有3.6+的python版本,你可以使用选择

from random import choices

items = range(1, 10)
new_items = choices(items, k = 3)

print(new_items) 
[6, 3, 1]