Python位数组（高性能）

Question

我正在设计一个bloom过滤器，我想知道Python中性能最好的位数组实现是什么。

Python的好处是它可以处理任意长度的整数，这就是我现在使用的，但是我对Python内部的了解还不够，不知道这是否是Python中最有效的方法。

我找到了^{}但是它可以处理很多其他的事情，比如切片，我不需要。我只需要&和|和<<操作。

Answer 1

也许看看这个。它是纯python，使用int数组： http://stromberg.dnsalias.org/svn/bits/trunk/

另外，已经有几个Python bloom过滤器。检查Pypi： https://pypi.python.org/pypi?%3Aaction=search&term=bloom+filter&submit=search

高温高压

Answer 2

免责声明：我是intbitset：-）的主要开发人员，上面在一条评论中提到过。这只是为了让您知道，由于几个星期以来，intbitset现在与Python 3.3和3.4兼容。此外，与本机功能相比，它的速度几乎是后者的两倍：

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性能的详细信息，请参见：http://intbitset.readthedocs.org/en/latest/#performance

Answer 3

内置的int经过了很好的优化，它已经支持&、|和<<。

至少有一个任意长度整数的替代实现，基于GMP，称为^{}。（还有原始的gmpy、PyGMP、Sophie，以及同一个库周围的一些其他包装，但我怀疑它们是否有任何真正的性能差异。）

“位数组”的思想有两个主要的实现，^{}（您链接的那个）和^{}，还有一些库，比如^{}，它们给您提供了一个类似集合的接口（这也适用于您的使用）。

所以，让我们把它们扔在一起比较一下：

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位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'])）来看，它的速度比我每次测试的int慢14到70倍，所以我也简要地忽略了它。

---

那么让我们用更多的重复来尝试其他三个：

ba 6.385123810963705
gm 1.5937359740491956
py 2.129726824001409

数字还挺得住。bitarray远不及内置的int快。使用起来也比较笨拙（注意，应该是“alternate constructor”类方法的是一个实例方法，没有从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许可的，它在内存溢出情况下有更糟糕的错误处理行为（如，你的应用可能会出现segfult而不是raise），并且StackOverflow上至少有一个人会一提到GMP就告诉你GMP很烂（我相信是因为老版本的bug）。

但如果你需要额外的速度，也许这是值得的。

---

另一方面，这里是PyPy，3.2.3/2.1.0b1和PyPy 2.7.3/2.1.0，使用本机int类型与gmpy2上面的0.19562570203561336和0.2890629768371582结果进行比较：

py 0.2135779857635498
('py', 0.20878291130065918)

因此，在Python 3中，从CPython切换到pypypy与从int切换到gmpy2.mpz的好处几乎一样多，而在Python 2中则明显更大。而且它几乎肯定会加速剩下的代码。