缓慢的按位运算

Question

我正在开发一个 Python 库，它对长位字符串执行大量按位运算，我想找到一种可以最大限度提高速度的位字符串类型。我尝试了内置的 Python int 类型、numpy、bitstring, and bitarray，令人惊讶的是，Python int 似乎在按位运算方面胜出。我用谷歌搜索过的所有内容都表明 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 ints/longs 上的单个操作如何与整个 numpy 位数组上的向量操作相比较，似乎存在很多混淆。一个 10,000 位的 Python int/long 值，当被视为位掩码时（使用 & 运算符，就像我们在 C/C++ 中对整数或长整数所做的那样）直接与长度为 10,000 的 numpy bool 数组，因为它们都包含相同数量的位数，尽管以两种不同的方式表示。我尝试过的其他表示 10,000 位的方法也是如此，包括使用 numpy 压缩位数组、numpy int 数组和来自其他库的位 array/string 类型。它们都是可比较的，因为它们都在相同的位序列上计算相同的函数。这里重要的是我可以表示所有 10,000 位并且我可以对它们执行按位运算。如果有人能提出一种更有效的方法来表示允许使用按位运算符（&、| 和 ~）的固定长度的长位序列，那么这就是我正在寻找的。

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

Answer 1

您要测试的是这些向量运算吗？您只是在尝试比较 1 次操作的速度，而 python 将获胜，因为它不必设置 numpy 数组或位数组。

尝试跟随怎么样？

x = np.array([random.randrange(2**31)]*1000) 
y = np.array([random.randrange(2**31)]*1000) 

%timeit x & y # in ipython

%timeit [ a & b for (a,b) in zip(x,y)] # even though x and y are numpy arrays, we are iterating over them - and not doing any vector operations

有趣的是，如果

xxx = [random.randrange(2**31)] * 1000
yyy = [random.randrange(2**31)] * 1000

然后

%timeit [a & b for (a,b) in zip(xxx,yyy)]

纯 python 列表，遍历它们比遍历 numpy 数组更快..有点违反直觉。不知道为什么。

同样，您可以尝试使用位串和位数组

这是你正在看的吗？

Answer 2

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

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

相比之下，int 运算采用 15 位或 30 位数字，具体取决于 the compile-time parameter PYLONG_BITS_IN_DIGIT 的值。我不知道哪个设置是默认设置。

您可以通过使用压缩表示和更大的 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

缓慢的按位运算

Slow bitwise operations

python

numpy

bitwise-operators

bitstring

bitarray