Очень быстрая выборка из набора с фиксированным количеством элементов в Python

Question

Мне нужно равномерно случайным образом сэмплировать число из набора с фиксированным размером, выполнить некоторые вычисления и вернуть новое число в набор. (Количество необходимых образцов очень велико)

Я пытался сохранить числа в списке и использовать random.choice (), чтобы выбрать элемент, удалить его, а затем добавить новый элемент. Но это слишком медленно!

Я думаю сохранить числа в массиве numpy, сэмплировать список индексов и для каждого индекса выполнить вычисление.

• Есть ли более быстрый способ сделать этот процесс?

Answer 1

Списки Python внутренне реализованы в виде массивов (например, Java ArrayList s, C ++ std::vector s и т. Д.), Поэтому удаление элемента из середины происходит относительно медленно: все последующие элементы необходимо переиндексировать.(Подробнее об этом см. http://www.laurentluce.com/posts/python-list-implementation/.) Поскольку порядок элементов не имеет к вам отношения, я рекомендую вам просто использовать random.randint(0, len(L) - 1), чтобы выбрать индекс i, а затем использовать L[i] = calculation(L[i]) для обновления i-го элемента.

Answer 2

Мне нужно равномерно случайным образом сэмплировать число из набора с фиксированным размером, выполнить некоторые вычисления и вернуть новое число в набор.

s = list(someset)           # store the set as a list
while 1:
    i = randrange(len(s))   # choose a random element
    x = s[i]
    y = your_calculation(x) # do some calculation
    s[i] = y                # put the new number back into the set

Answer 3

random .sample (набор или список или массив Numpy, Nsample) очень быстрый, но мне неясно, хотите ли вы что-нибудь подобное:

import random

Setsize = 10000
Samplesize = 100
Max = 1 << 20
bigset = set( random.sample( xrange(Max), Setsize ))  # initial subset of 0 .. Max

def calc( aset ):
    return set( x + 1 for x in aset )  # << your code here

    # sample, calc a new subset of bigset, add it --
for iter in range(3):
    asample = random.sample( bigset, Samplesize )
    newset = calc( asample )  # new subset of 0 .. Max
    bigset |= newset

Выможно использовать массивы Numpy или bitarray вместо set, но я ожидаю, что время в calc () будет доминировать.

Каковы ваши Setsize и Samplesize?