慢按位操作

Question

我正在开发一个Python库,它对长位字符串执行许多按位操作,我想找到一个能够最大化其速度的位串类型.我已经尝试了内置的Python int类型,numpy,bitstring和bitarray,而且令人惊讶的是,当涉及到按位操作时,Python int似乎赢了.我用google搜索的所有内容都说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值,当被视为一个位掩码时(使用&运算符就像我们可以用int或C/C++中的long一样)可以直接比作长度为10,000的numpy bool数组,因为它们都是包含相同数量的位,尽管以2种不同的方式表示.对于我尝试的表示10,000位的其他方式也是如此,包括使用numpy压缩位数组,numpy int数组和其他库中的位数组/字符串类型.它们都是可比较的,因为它们都在相同的位序列上计算相同的功能.这里最重要的是我可以表示所有10,000位,并且我可以对它们执行按位操作.如果有人能够建议一种更有效的方式来表示允许使用按位运算符(&,|和〜)的长的固定长度位序列,那就是我正在寻找的.

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

Answer 1

据我所知,内置的Python 3 int是您测试的唯一一个选项,它一次计算&多个字节的块.(我还没有完全弄清楚NumPy源代码中此操作的所有内容,但看起来它没有优化来计算大于dtype的块.)

• bitarray 逐字节,
• bool和1-bit-per-int NumPy尝试一点一点地进行,
• 压缩的NumPy尝试逐字节地进行,并且
• 在bitstring源去逐字节,以及做一些事情搞砸了其试图通过用Cython来提高速度,目前为止最慢使得它.

相反,int操作由15位或30位数字组成,具体取决于编译时参数PYLONG_BITS_IN_DIGIT的值.我不知道哪个设置是默认设置.

您可以使用压缩表示和更大的dtype来加速NumPy尝试.看起来在我的机器上,一个32位的dtype工作速度最快,击败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