битовый массив Python (исполнитель)

Встроенный int довольно хорошо оптимизирован и уже поддерживает &, | и <<.

Существует по крайней мере одна альтернативная реализация целых чисел произвольной длины, основанная на GMP, известная как _ 5_. (Есть также оригинальные gmpy, PyGMP, Sophie и несколько других оболочек для той же библиотеки, но я сомневаюсь, что они будут иметь какие-либо реальные различия в производительности.)

И есть две основные реализации идеи "битового массива": bitarray (та, которую вы связали) и bitstring, а также несколько библиотек, например _ 11_, которые вместо этого предоставляют вам интерфейс, похожий на набор (который также должен работать для ваших целей).

Итак, давайте сложим их все вместе и сравним:

import random
import struct
import timeit
import bitarray
import bitstring
import gmpy2

n = random.randrange((1<<31)+1, 1<<32)

bs = bitstring.pack('<q', n)
ba = bitarray.bitarray(64)
ba.frombytes(struct.pack('<q', n))
gm = gmpy2.mpz(n)
py = n

for x in 'bs', 'ba', 'gm', 'py':
    def f(x=locals()[x]): x | x; x & x
    t = timeit.timeit(f, number=10000)
    print(x, t)

На моем Mac, работающем с 64-разрядной версией Python.org CPython 3.3.2, я получаю следующее:

bs 0.7623525890521705
ba 0.006623028079047799
gm 0.0016346259508281946
py 0.002280334010720253

Кажется, этого достаточно, чтобы уволить bitstring.

Кроме того, хотя я не показал здесь intbitset, потому что ни он, ни другие подобные библиотеки, которые я не нашел, работают с Python 3, из множества сравнений (с использованием intbitset.intbitset([i for i, bit in enumerate(bin(n)[2:]) if bit != '0'])) он от 14 до 70 раз медленнее, чем int в каждом тесте, который я бросаю. это, так что я вкратце отклонил это.

Итак, давайте попробуем остальные три с большим количеством повторений:

ba 6.385123810963705
gm 1.5937359740491956
py 2.129726824001409

И цифры остаются в силе. bitarray далеко не так быстр, как встроенный int. Он также более неуклюж в использовании (обратите внимание, что метод класса «альтернативный конструктор» - это метод экземпляра, нет быстрого и простого способа преобразования из или в int, и причина, по которой я тестировал только x | x и x & x, заключается в том, что там ограничения на операторов). Если вам нужно целое число в виде массива битов, это прекрасно; если вам нужно использовать битовое преобразование в стиле C для целого числа, это не то, что лучше всего получается.

Что касается gmpy2, то вроде примерно на треть быстрее родной int. Что, если мы сделаем числа намного больше, например, на 1,5 Кбит?

gm 0.19562570203561336
py 0.29293217696249485

А вот цифры с Apple Python 2.7.5:

('gm', 0.2890629768371582)
('py', 0.36592698097229004)

Итак, оно того стоит? Он менее удобен в использовании, он медленнее, чем быстрее для некоторых других операций, о которых вы не спрашивали, для него требуется сторонняя библиотека C, которая лицензирована LGPL, она имеет гораздо худшее поведение при обработке ошибок в случаях переполнения памяти ( например, ваше приложение может segfault вместо повышения), и есть по крайней мере один человек в StackOverflow, который собирается появиться и сказать вам, что GMP отстой, когда он упоминается (я считаю, из-за ошибки в более старой версии).

Но если вам нужна дополнительная скорость, возможно, оно того стоит.

С другой стороны, здесь PyPy, 3.2.3 / 2.1.0b1 и PyPy 2.7.3 / 2.1.0, использующие собственный тип int - сравните с результатами 0.19562570203561336 и 0.2890629768371582 из gmpy2 выше:

py 0.2135779857635498
('py', 0.20878291130065918)

Таким образом, переход с CPython на PyPy дает вам почти такое же преимущество, как переключение с int на gmpy2.mpz в Python 3, и значительно больше преимуществ в Python 2. И почти наверняка это ускорит остальную часть вашего кода.

Отказ от ответственности: я являюсь основным разработчиком intbitset :-), который был упомянут выше в одном из Комментарии. Это просто для того, чтобы вы знали, что через несколько недель intbitset теперь совместим с Python 3.3 и 3.4. Вдобавок похоже, что WRT работает почти вдвое быстрее, чем нативная int функциональность:

import random
from intbitset import intbitset
x = random.sample(range(1000000), 10000)
y = random.sample(range(1000000), 10000)
m = 0
for i in x:                 
    m += 1 << i
n = 0
for i in x:                 
    n += 1 << i
mi = intbitset(x)
ni = intbitset(y)

%timeit m & n ## native int
10000 loops, best of 3: 27.3 µs per loop

%timeit mi & ni ## intbitset
100000 loops, best of 3: 13.9 µs per loop

%timeit m | n ## native int
10000 loops, best of 3: 26.8 µs per loop

%timeit mi | ni ## intbitset
100000 loops, best of 3: 15.8 µs per loop

## note the above were just tested on Python 2.7, Ubuntu 14.04.

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

Для получения дополнительной информации о intbitset производительности наборов WRT Python см. Вместо этого: http://intbitset.readthedocs.org/en/latest/#performance

Возможно, зацените это. Это чистый питон и использует массив int: http://stromberg.dnsalias.org/svn/bits/trunk/

Кроме того, уже существует несколько цветных фильтров Python. Проверьте Pypi: https://pypi.python.org/pypi?%3Aaction=search&term=bloom+filter&submit=search

HTH