【python】bitのリストを高速にintに変換する

やりたいこと

input:[0,1,0,0]
output:4

　極めて単純明快ですが、やるだけなら簡単なので速度を測ります。

　さらに、pure pythonでやると遅いことが目に見えているのでcythonで高速にしようというネタです。

pure pythonで書いたプログラム

　素晴らしいことに（？）、bitリストのintへの変換は既出ネタです。

arrays - Bits list to integer in Python - Stack Overflow

　書き方はだいたい数パターンなので、ここの回答の一つから引用します。

def mult_and_add(bit_list):
    output = 0
    for bit in bit_list:
        output = output * 2 + bit
    return output

def shifting(bitlist):
     out = 0
     for bit in bitlist:
         out = (out << 1) | bit
     return out

　リンク先は後者の方がじゃっかん遅いと主張しています。本当でしょうか？

　自分でも動かしてみます。

# coding: UTF-8

import time
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

def mult_and_add(bit_list):
    output = 0
    for bit in bit_list:
        output = output * 2 + bit
    return output

def shifting(bitlist):
     out = 0
     for bit in bitlist:
         out = (out << 1) | bit
     return out

def bench(lst):
    t1 = time.time()
    mult_and_add(lst)
    t2 = time.time()
    res1 = t2-t1

    t1 = time.time()
    shifting(lst)
    t2 = time.time()
    res2 = t2-t1

    return np.array((res1, res2))

def main():
    result_lst = []
    for i in range(50):
        i = 10**i
        binlst = [int(x) for x in bin(i)[2:]]
        lst = []
        for j in range(100):
            lst.append(bench(binlst))
        result_lst.append(np.mean(lst, axis=0))
    df = pd.DataFrame(result_lst, columns=["muladd", "shift"])
    print(df)
    df.plot()
    plt.savefig("fig1.png")

if __name__ == "__main__":
    main()

　横軸は $10^n$ のnです。本当らしい。なんでだろう。

cythonを使う

　どうせpure pythonは遅いと思ったんです。だからcythonで書きました。

cython_bit2int.pyx

# coding: UTF-8
import array

def muladd_cy(lst):
    return _muladd(array.array("Q", lst))

def shift_cy(lst):
    return _shift(array.array("Q", lst))

cdef int _muladd(unsigned long[:] bitlist):
    cdef unsigned long int out = 0
    cdef int i = 0

    for i in range(len(bitlist)):
        out = out * 2 + bitlist[i]
    return out

cdef int _shift(unsigned long[:] bitlist):
    cdef unsigned long int out = 0
    cdef int i = 0

    for i in range(len(bitlist)):
        out = (out << 1) | bitlist[i]
    return out

bit2int.py

# coding: UTF-8

import time
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

import pyximport; pyximport.install()
import cython_bit2int as cyb2i


def mult_and_add(bit_list):
    output = 0
    for bit in bit_list:
        output = output * 2 + bit
    return output

def shifting(bitlist):
     out = 0
     for bit in bitlist:
         out = (out << 1) | bit
     return out

def bench(lst):
    t1 = time.time()
    mult_and_add(lst)
    t2 = time.time()
    res1 = t2-t1

    t1 = time.time()
    shifting(lst)
    t2 = time.time()
    res2 = t2-t1

    t1 = time.time()
    cyb2i.muladd_cy(lst)
    t2 = time.time()
    res3 = t2-t1

    t1 = time.time()
    cyb2i.shift_cy(lst)
    t2 = time.time()
    res4 = t2-t1

    return np.array((res1, res2, res3, res4))

def main():
    result_lst = []
    for i in range(50):
        i = 10**i
        binlst = [int(x) for x in bin(i)[2:]]
        lst = []
        for j in range(100):
            lst.append(bench(binlst))
        result_lst.append(np.mean(lst, axis=0))
    df = pd.DataFrame(result_lst, columns=["muladd", "shift", 
                                           "muladd_cy", "shift_c"])
    print(df)
    df.plot()
    plt.savefig("fig2.png")

if __name__ == "__main__":
    main()

　array使うのはフェアな比較じゃないって？　まあ大目に見て下さい。

　桁数が少ない領域では速度差が少ない（というかヘタしたら負けてる）ので微妙かも。恐らくlistからarrayへの変換が重いのでしょう。こっちだとshiftの方が速くなるのは理屈通りでした。

静かなる名辞

pythonとプログラミングのこと

【python】bitのリストを高速にintに変換する

やりたいこと

pure pythonで書いたプログラム

cythonを使う