python 位数组(性能)

Question

我正在设计布隆过滤器，我想知道 Python 中性能最高的位数组实现是什么。

Python 的优点在于它可以开箱即用地处理任意长度的整数，这就是我现在使用的，但我对 Python 的内部结构了解不够，无法知道这是否是在 Python 中执行此操作的最高效方法.

我找到了 bitarray 但它处理很多其他事情，比如切片，我不需要。我只需要 &和 |和 <<操作。

Answer 1

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

至少有一种基于 GMP 的任意长度整数的替代实现，称为 gmpy2 。 (还有原始的 gmpy 、 PyGMP 、 Sophie 和其他一些围绕同一个库的包装器，但我怀疑它们是否有任何真正的性能差异。)

“位数组”思想有两个主要实现， bitarray (您链接的那个)和 bitstring ，还有一些像 intbitset 这样的库，它们为您提供了一个类似集合的接口(interface)(它也适用于你的用途)。

所以，让我们把它们放在一起比较一下:

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 快。它使用起来也更笨拙(请注意，应该是“替代构造函数”的类方法是一个实例方法，没有快速简便的方法来从 int 转换或向 int 转换，我只测试 x | x 和 x & x 的原因是是对运营商的限制)。如果您需要一个整数作为位数组，那很好；如果您需要对整数进行 C 风格的位元处理​​，那不是它最擅长的。

---

至于 gmpy2 ，它似乎比原生 int 快三分之一。如果我们让数字大很多，比如 1.5kbits，会怎样？

gm 0.19562570203561336
py 0.29293217696249485

这里是 Apple Python 2.7.5 的数字:

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

那么，值得吗？它使用起来不太友好，在你没有询问的其他一些操作上它更慢而不是更快，它需要一个第三方 C 库，它是 LGPL 许可的，它在内存溢出情况下有更糟糕的错误处理行为(例如，您的应用程序可能会出现段错误而不是引发错误)，并且 StackOverflow 上至少会有一个人会出现并告诉您 GMP 一提到它就糟透了(我相信是因为旧版本中的错误)。

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

---

另一方面，这里是 PyPy、3.2.3/2.1.0b1 和 PyPy 2.7.3/2.1.0，使用 native int 类型——与上面 gmpy2 的 0.19562570203561336 和 0.2890629768371582 结果相比:

py 0.2135779857635498
('py', 0.20878291130065918)

因此，从 CPython 切换到 PyPy 给您带来的好处几乎与在 Python 3 中从 int 切换到 gmpy2.mpz 一样多，在 Python 2 中的好处要多得多。而且它几乎肯定也会加速您的其余代码。