大lis上Python非常慢的随机抽样

Question

我预计下面的算法性能会非常慢。 我有一个非常大的（1.000.000+）列表，其中包含大字符串。在

即：id_list = ['MYSUPERLARGEID:1123:123123', 'MYSUPERLARGEID:1123:134534389', 'MYSUPERLARGEID:1123:12763']...

{cd2>从这个列表中选择^个随机元素。 其思想是随机选择id_list中的一个字符串id，直到到达num_reads，并将它们添加（我说add，而不是append，因为我不在乎random_id_list的顺序）到random_id_list中，这个开头是空的。在

我不能重复同一个身份证，所以我把它从原来的名单上删除后，被选中。我怀疑这就是为什么剧本进展得很慢。。也许我错了，这是这个循环的另一部分，慢行为的责任。在

for x in xrange(0, num_reads):
    id_index, id_string = random.choice(list(enumerate(id_list)))
    random_id_list.append(id_string)
    del read_id_list[id_index]

Answer 1

使用^{}生成不重复的N个元素的示例：

random_id_list = random.sample(read_id_list, num_reads)

从一个大列表中删除元素确实很慢，因为索引之外的所有元素都必须向上移动一步。在

当然，这不会再从原始列表中删除元素，因此重复的random.sample()调用仍然可以给您提供包含以前选择过的元素的示例。如果您需要重复生成示例，直到列表耗尽，那么随机播放一次，然后从无序列表中取出k元素的连续切片：

^{pr2}$

然后使用此方法生成您的样本；可以是在循环中，也可以是使用next()：

sample_gen = random_samples(num_reads)
random_id_list = next(sample_gen)
# some point later
another_random_id_list = next(sample_gen)

因为列表是完全随机的，所以以这种方式生成的切片也是有效的随机样本。在

Answer 2

“硬”的方法，而不是简单地乱翻列表，而是按顺序评估列表中的每一个元素，并以一种既依赖于你仍然需要选择的项目的数量，也依赖于可供选择的项目数量来选择项目。如果您没有将整个列表一次呈现给您（一种所谓的在线算法），这将非常有用。在

假设您需要选择k，其中N项。{cd3>每一个项目都有一次被选中的可能性。但是，如果您接受第一个项目，那么您只需要从N-1个项目中选择k-1个项目。如果您拒绝它，您仍然需要k个项目，这些项目来自N-1个项目。所以算法看起来像

N = len(id_list)
k = 10  # For example
choices = []
for i in id_list:
    if random.randint(1,N) <= k:
        choices.append(i)
        k -= 1
    N -= 1

最初，第一个项目的选择概率为k/N。当你浏览你的列表时，N会逐渐减少，而{}则会随着你实际接受项目而减少。请注意，总的来说，每个项目仍然有p = k/N被选中的机会。以列表中的第二项为例。让pi是您选择列表中第i个元素的概率。p1显然是{}，给定k和{}的起始值。以p2为例。在

^{pr2}$

类似的（但更长的）分析适用于p3，p4等