静かなる名辞

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



【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使うのはフェアな比較じゃないって? まあ大目に見て下さい。

ベンチマークの結果2
ベンチマークの結果2

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