我正在开发一个 Python 库，该库对长位字符串执行大量按位运算，我想找到一种可以最大限度提高其速度的位字符串类型。我尝试了内置的 Python int 类型，numpy，bitstring , 和 bitarray ，而且令人惊讶的是，Python 整数似乎在按位运算方面胜出。我用谷歌搜索过的所有内容都表明 numpy 对于这样的矢量化操作应该更快。我以某种方式错误地使用了 numpy 吗？有没有我可以使用的另一个 Python 库，它实际上改进了 Python 的内置 int 类型？

from timeit import timeit
import random


size = 10000


def int_to_bits(i):
    result = []
    for _ in range(size):
        result.append(i % 2)
        i >>= 1
    return result



x = random.randrange(2**size)
y = random.randrange(2**size)

print(x.bit_length(), y.bit_length())

x_bits = int_to_bits(x)
y_bits = int_to_bits(y)

t = timeit(
    stmt='a & b',
    setup='a = %d; b = %d' % (x, y)
)
print("raw ints:", t)

t = timeit(
    stmt='a & b',
    setup=('import numpy;'
           'a = numpy.array(%r, dtype=int);'
           'b = numpy.array(%r, dtype=int)') % (x_bits, y_bits)
)
print('numpy int array:', t)

t = timeit(
    stmt='a & b',
    setup=('import numpy;'
           'a = numpy.array(%r, dtype=bool);'
           'b = numpy.array(%r, dtype=bool)') % (x_bits, y_bits)
)
print('numpy bool array:', t)

t = timeit(
    stmt='a & b',
    setup=('import numpy;'
           'a = numpy.packbits(%r);'
           'b = numpy.packbits(%r)') % (x_bits, y_bits)
)
print('numpy packed bits:', t)

t = timeit(
    stmt='a & b',
    setup=('import bitstring;'
           'a = bitstring.BitString(%r);'
           'b = bitstring.BitString(%r)') % (x_bits, y_bits)
)
print('bitstring:', t)

t = timeit(
    stmt='a & b',
    setup=('import bitarray;'
           'a = bitarray.bitarray(%r);'
           'b = bitarray.bitarray(%r)') % (x_bits, y_bits)
)
print('bitarray:', t)

结果:

10000 10000
raw ints: 0.29606562735373115
numpy int array: 7.400762747057885
numpy bool array: 1.1108355715984288
numpy packed bits: 1.3064737574273284
bitstring: 380.9796937642803
bitarray: 1.4451143449501842

编辑:

关于 Python 整数/长整数上的单个操作如何与整个 numpy 位数组上的向量操作相比较，似乎存在很多混淆。一个 10,000 位的 Python int/long 值，当被视为位掩码时(使用 & 运算符，就像我们在 C/C++ 中对 int 或 long 所做的那样)可以直接与长度为 10,000 的 numpy bool 数组相比较，因为它们都是包含相同数量的位数，尽管以两种不同的方式表示。我尝试过的其他表示 10,000 位的方法也是如此，包括使用 numpy 压缩位数组、numpy int 数组和来自其他库的位数组/字符串类型。它们都是可比较的，因为它们都在相同的位序列上计算相同的函数。这里重要的是我可以表示所有 10,000 位并且我可以对它们执行按位运算。如果有人可以建议一种更有效的方法来表示允许使用按位运算符(&、| 和 ~)的固定长度长位序列，那么这就是我正在寻找的。

如果您仍然对 Python int/long 值如何存储与 numpy bool 数组或 numpy 二进制值 int 数组相同的信息感到困惑，请参阅 int_to_bits 函数在上面的代码中；它演示了如何从 Python int/long 中提取位，这表明对两个 10,000 位整数执行 & 操作与对包含 10,000 个 bool 值的列表或数组逐个元素地执行它基本相同。

最佳答案

据我所知，内置的 Python 3 int 是您测试的唯一一个以多个 block 的形式计算 & 的选项一次一个字节。 (我还没有完全弄清楚 NumPy source 中这个操作的所有内容，但看起来它没有优化来计算比 dtype 更大的 block 。)

• bitarray 逐字节，
• bool 和 1-bit-per-int NumPy 尝试一点一点地进行，
• 打包的 NumPy 尝试逐字节进行，并且
• bitstring source 一个字节接一个字节地进行，并做一些事情搞砸了它通过 Cython 提高速度的尝试，使其成为迄今为止最慢的。

相比之下，int 操作根据 the compile-time parameter PYLONG_BITS_IN_DIGIT 的值进行 15 位或 30 位数字。 .我不知道哪个设置是默认设置。

您可以通过使用压缩表示和更大的 dtype 来加速 NumPy 尝试。看起来在我的机器上，32 位数据类型运行速度最快，超过了 Python 整数；我不知道你的设置是什么样的。用每种格式的 10240 位值进行测试，我得到

>>> timeit.timeit('a & b', 'import numpy; a = b = numpy.array([0]*160, dtype=num
py.uint64)')
1.3918750826524047
>>> timeit.timeit('a & b', 'import numpy; a = b = numpy.array([0]*160*8, dtype=n
umpy.uint8)')
1.9460716604953632
>>> timeit.timeit('a & b', 'import numpy; a = b = numpy.array([0]*160*2, dtype=n
umpy.uint32)')
1.1728465435917315
>>> timeit.timeit('a & b', 'a = b = 2**10240-1')
1.5999407862400403

关于python - 缓慢的按位运算，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30679139/