Python在大清单上随机抽样非常慢

Question

我期望下面的算法性能非常慢.我有一个包含大字符串的非常大的(1.000.000+)列表.

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

num_reads是从此列表中随机选择的最大元素数.我的想法是随机选择其中一个字符串ID,id_list直到num_reads达到并添加(我说添加,而不是附加,因为我不关心random_id_list订单)它们random_id_list在开头是空的.

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

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()调用仍然可以为您提供之前已选择的元素的样本.如果您需要重复生成样本,直到列表用完为止,那么随后将从末尾随机抽取元素:

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

然后用它来制作你的样品; 无论是循环还是k:

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

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