在Python中将二进制列表（或数组）转换为整数的最快方法
假设有一个列表（或者说数组），里面包含了1和0。
gona = [1, 0, 0, 0, 1, 1]
我想把这个列表转换成一个整数，这个整数是由二进制值100011表示的（也就是列表中的元素组合成的数字）。
我知道可以这样做。
int("".join(map(str, gona)),2)
或者
补充说明：可以用int("".join([str(i) for i in gona]),2)来实现。
有没有更快的方法可以做到这一点呢？
4 个回答
1
我试了这个：
int(str(gona).replace(', ','')[1:-1])
然后和这个进行比较（这是@Sohcahtoa82的最快情况）：
sum(x << i for i, x in enumerate(reversed(gona)))
在我的电脑上，第一个方法执行1000000次大约需要5.97秒。第二个方法大约需要8.03秒。
我尝试了另一种方法，并把它插入到@Sohcahtoa82的代码中：
T61 = """
l = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
digits = ['0', '1']
s = ''
for y in l:
s += digits[y]
int(s, 2)
"""
T60 = """
l = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
digits = ['0', '1']
s = ''
for y in l:
s += digits[y]
int(s, 2)
"""
T6mix = """
l = [1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0]
digits = ['0', '1']
s = ''
for y in l:
s += digits[y]
int(s, 2)
"""
然后得到了这些结果。我的结果是最后一组时间。
5.45334255339
1.89000112578
4.14859673729
.
4.39018410496
4.21122597336
4.57919181895
.
3.59095765307
3.25353409619
3.78588067833
.
6.53343932548
6.33234985363
6.65685678006
.
2.74509861151
2.6111819044
2.83928911064
.
2.79519545737
2.66091503704
2.9183024407
2
我决定写一个脚本来试试四种不同的方法来完成这个任务。
import time
trials = range(1000000)
list1 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0]
list0 = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
listmix = [1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0]
def test1(l):
start = time.time()
for trial in trials:
tot = 0
n = 1
for i in reversed(l):
if i:
tot += 2**n
n += 1
print 'Time taken:', str(time.time() - start)
def test2(l):
start = time.time()
for trial in trials:
int("".join(map(str, l)),2)
print 'Time taken:', str(time.time() - start)
def test3(l):
start = time.time()
for trial in trials:
sum(x << i for i, x in enumerate(reversed(l)))
print 'Time taken:', str(time.time() - start)
def test4(l):
start = time.time()
for trial in trials:
int("".join([str(i) for i in l]),2)
print 'Time taken:', str(time.time() - start)
test1(list1)
test2(list1)
test3(list1)
test4(list1)
print '.'
test1(list0)
test2(list0)
test3(list0)
test4(list0)
print '.'
test1(listmix)
test2(listmix)
test3(listmix)
test4(listmix)
我的结果是：
Time taken: 7.14670491219
Time taken: 5.4076821804
Time taken: 4.7349550724
Time taken: 7.24234819412
.
Time taken: 2.29213285446
Time taken: 5.38784003258
Time taken: 4.70707392693
Time taken: 7.27936697006
.
Time taken: 4.78960323334
Time taken: 5.36612486839
Time taken: 4.70103287697
Time taken: 7.22436404228
结论：@goncalopp 的方案可能是最好的。它的速度一直很快。不过，如果你可能会有比1更多的0，那么逐个查看列表，手动计算2的幂并加起来会是最快的。
补充：我重新写了我的脚本，用了 timeit，源代码在 http://pastebin.com/m6sSmmR6
我的输出结果是：
7.78366303444
2.79321694374
5.29976511002
.
5.72017598152
5.70349907875
5.66881299019
.
5.25683712959
5.17318511009
5.20052909851
.
8.23388290405
8.24193501472
8.15649604797
.
3.94102287292
3.95323395729
3.9201271534
如果你全是0，我从后往前加2的幂的方法仍然是最快的，但如果不是的话，@sxh2 的方法绝对是最快的，而且我实现的版本甚至没有包含他的缓存优化。
2
你可以这样做：
sum(x << i for i, x in enumerate(reversed(gona)))
虽然这样做速度提升不大
4
这是我想到的最快的方法。稍微改动了一下你最初的解决方案：
digits = ['0', '1']
int("".join([ digits[y] for y in x ]), 2)
%timeit int("".join([digits[y] for y in x]),2)
100000 loops, best of 3: 6.15 us per loop
%timeit int("".join(map(str, x)),2)
100000 loops, best of 3: 7.49 us per loop
顺便说一下，在这种情况下，使用列表推导式比使用生成器表达式要快。
补充说明：
我不想显得聪明，但你总是可以用内存换取速度：
# one time precalculation
cache_N = 16 # or much bigger?!
cache = {
tuple(x): int("".join([digits[y] for y in x]),2)
for x in itertools.product((0,1), repeat=cache_N)
}
然后：
res = cache[tuple(x)]
这样会快得多。当然，这样做也有个限度……
补充说明2：
我现在看到你说你的列表有32个元素。在这种情况下，缓存的方案可能不太可行，但我们还有其他方法可以用速度换取内存。例如，使用 cache_N=16，这肯定是可行的，你可以访问两次：
c = 2 ** cache_N # compute once
xx = tuple(x)
cache[xx[:16]] * c + cache[xx[16:]]
%timeit cache[xx[:16]] * c + cache[xx[16:]]
1000000 loops, best of 3: 1.23 us per loop # YES!