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

Я проектирую фильтр Блума, и мне интересно, какова наиболее эффективная реализация битового массива в Python.

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

я нашел bitarray но он обрабатывает много других вещей, таких как нарезка, которая мне не нужна. Мне нужно только & а также | а также << операции.

Источник

3 ответа

Решение

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

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

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

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

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 под управлением Python.org 64-bit 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 вместо повышения), и в Stackru есть по крайней мере один человек, который собирается показать и сообщить вам, что GMP сосет всякий раз, когда упоминается (я полагаю, из-за ошибки в более старой версии).

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

С другой стороны, вот PyPy, 3.2.3/2.1.0b1 и PyPy 2.7.3/2.1.0, используя нативный int type - сравните с результатами 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/

Источник

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

Также уже есть несколько фильтров цветения Python. Проверьте Pypi: https://pypi.python.org/pypi?%3Aaction=search&term=bloom+filter&submit=search

НТН

Источник
Другие вопросы по тегам