Производительность небольших наборов в Python

Question

Я ищу наиболее эффективный способ представления небольших наборов целых чисел в заданном диапазоне (скажем 0-10) в Python. В этом случае эффективность означает быструю конструкцию (из несортированного списка), быстрый запрос (пару запросов на каждый набор) и достаточно быструю конструкцию сортированной версии (возможно, один раз на десять наборов или около того). Априори, кандидаты используют встроенный тип набора Python (быстрый запрос), используя отсортированный массив (возможно, быстрее для constrct?) Или используя бит-массив (быстро все, если я был в C ... но я сомневаюсь, что Python будет что эффективный (?)). Любой совет, из которого выбрать?

Спасибо.

Answer 1

Мой совет - придерживаться встроенного set(). Будет очень сложно написать код Python, который превосходит встроенный код C для производительности. Скорость построения и скорость поиска будут самыми быстрыми, если вы полагаетесь на встроенный код C.

Для отсортированного списка, лучше всего использовать встроенную функцию сортировки:

x = set(seq) # build set from some sequence 
lst = sorted(x) # get sorted list from set 

В общем, в Python, тем меньше кода вы пишете, тем быстрее она. Чем больше вы можете полагаться на встроенные C-основы Python, тем быстрее. Интерпретированный Python во многих случаях медленнее, чем код C, от 20x до 100x, и очень сложно быть настолько умным, что вы выходите вперед, а просто используете встроенные функции по назначению.

Если ваши наборы гарантированно всегда будут целыми числами в диапазоне от [0, 10], и вы хотите, чтобы размер памяти был как можно меньше, тогда битовые флаги внутри целого числа будут способом идти.

pow2 = [2**i for i in range(32)] 

x = 0 # set with no values 
def add_to_int_set(x, n): 
    return x | pow2[n] 

def in_int_set(x, n): 
    return x & pow2[n] 

def list_from_int_set(x): 
    return [i for i in range(32) if x & pow2[i]] 

Я буду держать пари, что это на самом деле медленнее, чем при использовании встроенного set() функций, но вы знаете, что каждый набор будет только быть int объект: 4 байта, плюс накладные расходы объекта Python.

Если вы буквально нуждались в миллиардах из них, вы могли бы сэкономить место, используя NumPy array вместо списка Python; NumPy array просто сохранит простые целые числа. Фактически, NumPy имеет 16-разрядный целочисленный тип, поэтому, если ваши наборы действительно находятся только в диапазоне [0, 10], вы можете получить размер хранилища до двух байтов с помощью NumPy array.

http://www.scipy.org/FAQ#head-16a621f03792969969e44df8a9eb360918ce9613

Answer 2

Я хотел бы использовать bitmapping и сохранить членов «набор» в int ... который на самом деле может быть быстрее, чем встроенный в set типа в этом случае, - хотя убежище I Это не проверено. Это, безусловно, потребует меньше места для хранения.

Update

У меня нет времени прямо сейчас, чтобы сделать полный подобный набор реализации и бенчмарк это против Python встроенный в классе, но вот то, что я считаю, это рабочий пример, иллюстрирующий мое предложение , Как я думаю, вы согласитесь, код выглядит довольно быстро, а память эффективнее.

Учитывая почти прозрачные «неограниченные» длинные целочисленные возможности Python, то, что написано, будет автоматически работать с целыми значениями в гораздо большем диапазоне, чем вам нужно, хотя это может немного замедлить работу.;)

class BitSet(object): 
    def __init__(self, *bitlist): 
     self._bitmap = 0 
     for bitnum in bitlist: 
      self._bitmap |= (1 << bitnum) 

    def add(self, bitnum): 
     self._bitmap |= (1 << bitnum) 

    def remove(self, bitnum): 
     if self._bitmap & (1 << bitnum): 
      self._bitmap &= ~(1 << bitnum) 
     else: 
      raise KeyError 

    def discard(self, bitnum): 
     self._bitmap &= ~(1 << bitnum) 

    def clear(self): 
     self._bitmap = 0 

    def __contains__(self, bitnum): 
     return bool(self._bitmap & (1 << bitnum)) 

    def __int__(self): 
     return self._bitmap 

if __name__ == '__main__': 

    bs = BitSet() 

    print '28 in bs:', 28 in bs 
    print 'bs.add(28)' 
    bs.add(28) 
    print '28 in bs:', 28 in bs 

    print 
    print '5 in bs:', 5 in bs 
    print 'bs.add(5)' 
    bs.add(5) 
    print '5 in bs:', 5 in bs 

    print 
    print 'bs.remove(28)' 
    bs.remove(28) 
    print '28 in bs:', 28 in bs 

Answer 3

В этом случае вы можете просто использовать список значений True/False. Хэш-таблица, используемая set, будет делать то же самое, но она будет включать в себя накладные расходы для хэширования, назначения ведра и обнаружения столкновений.

myset = [False] * 11 
for i in values: 
    myset[i] = True 
mysorted = [i for i in range(11) if myset[i]] 

Как всегда, вам нужно самому самостоятельно узнать, как это работает в ваших обстоятельствах.