可以将查找表与int.to_bytes
(仅限 Python 3)结合使用:
popcount8bit = bytes([popcount(x) for x in range(1<<8)]) # use any method to initialize this lookup table
popcount = lambda x: sum(map(popcount8bit.__getitem__,
x.to_bytes((x.bit_length()+7)//8, "little")))
不幸的是,这个解决方案比bin(x).count('1')
Python 3 慢 20%,但在 PyPy3 上快两倍。
这是一个基准脚本,针对不同的位数比较了这里介绍的几种不同的解决方案:
from __future__ import print_function #for Python 2
import sys
from timeit import timeit
import random
def popcount(x): return bin(x).count("1")
version3=sys.version.startswith("3")
for numBit in (2, 4, 8, 16, 31, 32, 63, 64, 1000, 10000):
maximum=int((1<<numBit)-1) #int cast just in case it overflows to long in Python 2
functions=[
(popcount, "bin count"),
(lambda x: "{:b}".format(x).count("1"), "format string count"),
]
try:
import gmpy
functions.append((gmpy.popcount, "gmpy"))
except ImportError:
pass
if sys.version.startswith("3"):
exec('''functions.append((lambda x: f"{x:b}".count("1"), "f-string count"))''')
if numBit<=16:
table1=[popcount(x) for x in range(maximum+1)]
functions.append((lambda x: table1[x], "lookup list"))
functions.append((table1.__getitem__, "lookup list without lambda"))
table2="".join(map(chr, table1))
functions.append((lambda x: ord(table2[x]), "lookup str"))
if version3:
table3=bytes(table1)
functions.append((lambda x: table3[x], "lookup bytes"))
if numBit==8:
functions.append((
b'\x00\x01\x01\x02\x01\x02\x02\x03\x01\x02\x02\x03\x02\x03\x03\x04'
b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
b'\x04\x05\x05\x06\x05\x06\x06\x07\x05\x06\x06\x07\x06\x07\x07\x08'
.__getitem__, "lookup bytes hard coded 8 bit"))
table_hardcoded=(
b'\x00\x01\x01\x02\x01\x02\x02\x03\x01\x02\x02\x03\x02\x03\x03\x04'
b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
b'\x04\x05\x05\x06\x05\x06\x06\x07\x05\x06\x06\x07\x06\x07\x07\x08')
functions.append((
table_hardcoded.__getitem__, "lookup bytes hard coded 8 bit local variable"))
functions.append((table3.__getitem__, "lookup bytes without lambda"))
if version3:
popcount8bit=bytes([popcount(x) for x in range(1<<8)]) #bytes because benchmark says that it's fastest
functions.append((
lambda x: sum(popcount8bit[x] for x in x.to_bytes((x.bit_length()+7)//8, "big")),
"to_bytes"
))
functions.append((
lambda x: sum(map(popcount8bit.__getitem__, x.to_bytes((x.bit_length()+7)//8, "big"))),
"to_bytes without list comprehension"
))
functions.append((
lambda x: sum(map(popcount8bit.__getitem__, x.to_bytes((x.bit_length()+7)//8, "little"))),
"to_bytes little endian, without list comprehension"
))
#for x in (2, 4, 8, 16, 32, 64):
# table1=[popcount(x) for x in range(1<<8)]
print("====== numBit=", numBit)
data=[]
numRepeat=10**7//(numBit+100)
for popcountFunction, description in functions:
random.seed(10) #make randint returns the same value
data.append((
timeit(lambda: popcountFunction(random.randint(0, maximum)), number=numRepeat),
description
))
time1, name1=data[0]
assert name1=="bin count"
data.sort()
maxLength=0
for time, description in data:
maxLength=max(maxLength, len(description))
for time, description in data:
print("{:{}} -> {:2f} = {} * {:2f}".format(description, maxLength+2, time, name1, time/time1))
它适用于 Python 2 和 3;但是,如果解决方案不适用于 Python 2,则不会对其进行测量。
此处未列出某些解决方案。
结果:
- Python 2:对于 <= 16 位,“没有 lambda 的查找列表”是最快的(比“bin 计数”快 25%,比“查找列表”(使用 lambda)快 6%),大于“bin 计数”是最快的。(我没有为 Python 2 安装 gmpy)
- Python 3:大致相同的结果。
- “没有 lambda 的查找字节”具有可比性(与“没有 lambda 的查找列表”相比 +/-2%)。
- gmpy 在所有情况下都比“bin count”快,但在 numBit <= 16 时比“没有 lambda 的查找列表”慢约 5%。
- “to_bytes”是可比较的。
- 使用 f-string 比“bin count”慢大约 10%。
- PyPy3:lambda 不再产生太多成本,并且
to_bytes
版本变得更快(比“bin count”快两倍);但是,我无法安装 gmpy。