所以我试图在Python中创建一个函数，以返回数字二进制中使用的所有二次幂。
例如：二进制中的123是1111011。我希望我的函数尽可能快地返回与123(1、2、8、16、32和64(的True位相对应的2的幂。
现在我发现最好的是：
def true_bits(num):
while num:
temp = num & -num
num -= temp
yield temp
一些(非更快(替代方案：
使用numpy并假定8位无符号整数：
import numpy as np
def numpy_bits(num):
bits = np.unpackbits(np.uint8(num), bitorder='little')
return 2**np.arange(8)[bits.astype(bool)]
numpy_bits(123)
# array([ 1, 2, 8, 16, 32, 64])
# 6.8 µs ± 293 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
使用python循环(按位递减顺序(：
def python_bits(num):
for i in range(7,-1,-1):
if num >= (x:=2**i):
yield x
num -= x
list(python_bits(123))
# [64, 32, 16, 8, 2, 1]
# 2.26 µs ± 61.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
OP的方法：
list(true_bits(123))
# [1, 2, 8, 16, 32, 64]
# 1.14 µs ± 37.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
用一堆随机的64位数字和24个真位进行基准测试(基于您在评论中所说的(：
47.7 ms true_bits_original
16.0 ms true_bits_Kelly
45.6 ms true_bits_original
15.7 ms true_bits_Kelly
47.4 ms true_bits_original
16.3 ms true_bits_Kelly
我使用了八个查找表，每个查找表负责八个位。带有基准测试的完整代码(在线试用！(：
intern = {2**i: 2**i for i in range(64)}.get
table0 = [()]
for i in range(8):
table0 += [(*bits, intern(2**i)) for bits in table0]
table0 = tuple(table0)
table1 = tuple(tuple(intern(bit << 8) for bit in bits) for bits in table0)
table2 = tuple(tuple(intern(bit << 8) for bit in bits) for bits in table1)
table3 = tuple(tuple(intern(bit << 8) for bit in bits) for bits in table2)
table4 = tuple(tuple(intern(bit << 8) for bit in bits) for bits in table3)
table5 = tuple(tuple(intern(bit << 8) for bit in bits) for bits in table4)
table6 = tuple(tuple(intern(bit << 8) for bit in bits) for bits in table5)
table7 = tuple(tuple(intern(bit << 8) for bit in bits) for bits in table6)
def true_bits_Kelly(num):
return chain(table0[num & 0xff],
table1[(num >> 8) & 0xff],
table2[(num >> 16) & 0xff],
table3[(num >> 24) & 0xff],
table4[(num >> 32) & 0xff],
table5[(num >> 40) & 0xff],
table6[(num >> 48) & 0xff],
table7[num >> 56])
def true_bits_original(num):
while num:
temp = num & -num
num -= temp
yield temp
funcs = true_bits_original, true_bits_Kelly
import timeit
from itertools import repeat, chain
from random import getrandbits, sample
from collections import deque
# Correctness
for _ in range(1000):
num = getrandbits(64)
expect = list(funcs[0](num))
for func in funcs:
assert list(func(num)) == expect
# Speed
for _ in range(3):
nums = [sum(2**i for i in sample(range(64), 24))
for _ in range(10000)]
for func in funcs:
def run():
gens = map(func, nums)
consumes = map(deque, gens, repeat(0))
deque(consumes, 0)
t = min(timeit.repeat(run, number=1))
print('%4.1f ms ' % (t * 1e3), func.__name__)
print()
您的初始代码已经非常高效了。问题是CPython解释器使其速度变慢。
事实上，解释器使用引用计数的可变大小整数，这些整数的管理成本很高。因此，-num分配一个新的整数对象以及num & ...和num -= temp。这意味着完成了3个昂贵的分配。yield也是一个相当昂贵的操作(它会导致低级别的上下文切换(。
即时编译器(JIT(可以最大限度地消除此类开销。例如，PyPy基于JIT的通用解释器能够在很大程度上消除对象分配的开销(这也要归功于快速垃圾收集器(，尽管PyPy还没有很好地优化yield。或者，可以在此处使用Numba。Numba是一个JIT编译器，旨在优化CPython执行的代码中可以使用的数字代码。例如，以下代码稍微快一点：
import numba as nb
@nb.njit('(uint64,)')
def true_bits(num):
while num:
temp = num & -num
num -= temp
yield temp
也就是说，它被限制为64位整数(或更小(，就像Numpy一样Cython还可以通过使用基本编译器提前编译代码来提供帮助。这类似于编写自己的C模块，但不需要编写C代码，Cython使这个过程变得更容易。
如果您想进一步优化代码，那么您当然需要在调用方函数中使用这些工具，这样就不会为从CPython解释器调用函数付出高昂的开销(这至少比本机调用慢10倍(。
如果这不可能(无望的情况(，您可以使用以下方法与Numba：
@nb.njit('(uint64,uint64[::1])')
def true_bits(num, buffer):
cur = 0
buffer.fill(0)
while num:
temp = num & -num
num -= temp
buffer[cur] = temp
cur += 1
return cur
buffer = np.empty(64, dtype=np.uint64)
written_items = true_bits(154781, buffer)
# Result stored in in buffer[:written_items]
其想法是将结果写入预先分配的缓冲区(因为在这种情况下创建Numpy数组很慢(。然后，函数在需要时将值写入缓冲区，并返回写入的项目数。您可以使用buffer[:written_items]获得实际项，也可以对数组进行迭代，但要注意，这样做几乎与计算本身一样昂贵(同样是由于CPython解释器(。尽管如此，它还是比最初的解决方案更快。