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

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

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

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

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

python numpy random performance random-access
person user972432    schedule 19.10.2011    source источник
comment
Вы разделяете свою коллекцию на две части? Те, которые обрабатываются (фиксированный размер), и те, которые не обрабатываются? Почему вы заменяете? Почему бы не создать новую коллекцию из двух подколлекций? 'a= (f(x) для x в S[:limit]) + (x для x в s[limit:])` Если s перемешивается, это должно работать, верно? Зачем делать замену в списке?   -  person S.Lott    schedule 19.10.2011
comment
Вычисление по каждому элементу зависит от других элементов в списке, я не знаю никаких способов векторизации такого процесса.   -  person user972432    schedule 19.10.2011
comment
расчет по каждому элементу зависит от других элементов в списке? Пожалуйста, объясните и это. Зависимость от других элементов не принуждает вас к процессу замены. Укажите код, который вы используете.   -  person S.Lott    schedule 19.10.2011

Ответы (3)


arrow_upward
7
arrow_downward

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

person ruakh    schedule 19.10.2011

arrow_upward
4
arrow_downward

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

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
person Raymond Hettinger    schedule 19.10.2011
comment
Почему это не s[i] = your_calculation( s[i] )? Почему все отдельные операторы присваивания? - person S.Lott; 19.10.2011
comment
Для ясности, чтобы ОП мог ясно видеть, что каждое предложение в его спецификации задачи соответствует строке кода, реализующей это предложение. - person Raymond Hettinger; 29.10.2011

arrow_upward
2
arrow_downward

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, примерно?

person denis    schedule 21.10.2011