Python 对大列表的随机抽样非常慢

Question

我预计以下算法的性能会非常低。我有一个非常大的 (1.000.000+) 列表，其中包含大字符串。

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

num_reads 是要从此列表中随机选择的最大元素数。这个想法是随机选择 id_list 中的一个字符串 id，直到达到 num_reads 并添加(我说添加，而不是附加，因为我不关心 random_id_list order) 放入开头为空的random_id_list。

我不能重复相同的 id，所以我在随机选择后将其从原始列表中删除。我怀疑这就是脚本真正变慢的原因。也许我错了，这是这个循环的另一部分，负责缓慢的行为。

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

使用random.sample()生成一个没有重复的 N 个元素的样本:

random_id_list = random.sample(read_id_list, num_reads)

从一个大列表的中间删除元素确实很慢，因为超出该索引的所有内容都必须向上移动一个步骤。

当然，这不会再从原始列表中删除元素，因此重复 random.sample() 调用仍然可以为您提供包含已删除元素的样本以前选的如果您需要重复生成样本直到列表耗尽，则洗牌一次，然后从洗牌后的列表中取出 k 元素的连续切片:

def random_samples(k):
    random.shuffle(id_list)
    for i in range(0, len(id_list), k):
        yield id_list[i : i + k]

然后使用它来生产您的 sample ；在循环中或使用 next():

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

因为列表是完全随机打乱的，所以这样产生的切片也是有效的随机样本。