Битовый массив 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
НТН