Python очень медленная случайная выборка по большому списку

Question

Я ожидаю очень медленной работы с алгоритмом ниже. У меня очень большой (1.000.000+) список, содержащий большие строки.

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

num_reads является максимальное число элементов для случайного выбора из этого списка. Идея состоит в том, чтобы случайно выбрать один из идентификаторов строки в id_list до тех пор, пока не будет достигнут num_reads и добавим (скажем, добавьте, а не добавьте, потому что я не забочусь о 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

Использование random.sample() производить выборку из N элементов, без повторов:

random_id_list = random.sample(read_id_list, num_reads) 

Удаление элементов из середины большого списка действительно медленно, так как все, за что индекс должен быть перемещен вверх шаг.

Это не значит, конечно, удалить элементы из исходного списка больше, поэтому повторилrandom.sample() вызовов все еще может дать вам образцы с элементами, которые были выбраны ранее. Если вам необходимо произвести образцы, пока ваш список не будет исчерпан, то перетасовать раз и оттуда на выбрать элементы с конца:

def random_samples(k): 
    random.shuffle(id_list) 
    while id_list: 
     res, id_list = id_list[-k:], id_list[:-k] 
     yield res 

затем использовать это, чтобы произвести ваши образцы; либо в цикле или с 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 элементов. Это означает, что каждый элемент имеет вероятность быть выбранным, если вы можете рассмотреть все предметы сразу. Однако, если вы принимаете первый элемент, вам нужно всего лишь выбрать k-1 предметов из N-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 неуклонно уменьшается, а k уменьшается, когда вы на самом деле принимаете предметы. Обратите внимание, что у каждого предмета в целом все еще есть шанс на выбор. В качестве примера рассмотрим второй элемент в списке.Пусть pi - вероятность того, что вы выберете i-й элемент в списке. p1, очевидно, k/N, с учетом начальных значений k и N. Рассмотрим, например, p2.

p2 = p1 * (k-1)/(N-1) + (1-p1) * k/(N-1) 
    = (p1*k - p1 + k - k*p1)/(N-1) 
    = (k - p1)/(N-1) 
    = (k - k/N)/(N-1) 
    = k/(N-1) - k/(N*(N-1) 
    = (k*N - k)/(N*(N-1)) 
    = k/N 

Похожие (но больше) анализ выполняется для p3, p4 и т.д.