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

Sun, 15 Apr 2018 20:13:20 +0900

やりたいこと

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()

ベンチマークの結果

　横軸はの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

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

【python】pythonでボゴソートしてみる

Tue, 07 Mar 2017 23:55:48 +0900

　みんな大好きボゴソート。愚直に実装するならそんなに面倒なことはない。

import random
def bogo(lst):
    while True:
        random.shuffle(lst)
        xb = lst[0]
        flag = True
        for x in lst[1:]:
            if xb > x:
                flag = False
                break
            xb = x
        if flag:
            return None

　色々イケてないところはあるんだろうけど、とりあえず動くだろうというラインを目指した。こんな感じで動かしてみた。

import sys
import time
import numpy as np
def main():
    lens = [3,4,5,6,7,8,9]
    means = []
    for l in lens:
        times = []
        print(l, end=" ")
        for _ in range(30):
            lst = list(range(l))
            random.shuffle(lst)
            start = time.time()
            bogo(lst)
            end = time.time()
            times.append(end-start)
            print(".",end="")
            sys.stdout.flush()
        means.append(np.array(times).mean())
        print(" ", means[-1])

　なんか色々あって気持ち悪い？　見栄えのために頑張ったのであって、本質的な部分は「外側のループでソートするリストの長さを変えて実行」「同じリストの長さに対して内側のループで30回ソートをやってソート時間を平均」だけだ。
　数分じっと待つと、こんな実行結果が出る。

3 ..............................  2.17914581299e-05
4 ..............................  0.000129095713298
5 ..............................  0.000656763712565
6 ..............................  0.00431096553802
7 ..............................  0.0268079439799
8 ..............................  0.239245136579
9 ..............................  3.45656121572

　9要素で3.4秒。理論的な計算量はO(n*n!)らしいので、10要素だとざっと30秒強かかるだろう。30回やって平均を取ると900秒かかる。15分以上。時間の無駄だね。
　15分回す代わりに、numpy+cythonで書き直してみた。

　関数側

import numpy as np
cimport numpy as np

def bogo(lst):
    llen = lst.shape[0]
    bogo_i(lst, llen)

def bogo_i(np.ndarray[np.int64_t, ndim=1] lst, np.int64_t llen):
    cdef long xb = 0
    cdef int x = 0
    cdef int flag = True
    while True:
        np.random.shuffle(lst)
        
        xb = lst[0]
        flag = True
        for x in range(1,llen):
            if xb > lst[x]:
                flag = False
                break
            xb = lst[x]
        if flag:
            return None

　
　呼び出し側

import sys
import time
import pyximport
import numpy as np
pyximport.install(setup_args={'include_dirs':[np.get_include()]}, inplace=True)
import cybogo

def main():
    lens = [3,4,5,6,7,8,9]
    means = []
    for l in lens:
        times = []
        print(l, end=" ")
        for _ in range(30):
            lst = np.random.randint(0,l,l)
            start = time.time()
            cybogo.bogo(lst)
            end = time.time()
            times.append(end-start)
            print(".",end="")
            sys.stdout.flush()
        means.append(np.array(times).mean())
        print(" ", means[-1])

if __name__ == '__main__':
    main()

　これでどこまで正解なのかはよくわからない。なんとなく上手く行ってないような気もする。

　実行結果

3 ..............................  0.000133109092712
4 ..............................  0.000322326024373
5 ..............................  0.000593320528666
6 ..............................  0.00232435067495
7 ..............................  0.00874052842458
8 ..............................  0.0432050784429
9 ..............................  0.451502895355

　10倍は速くなってないけど、要素数9のときで7.5倍高速化した。

　やっぱりcython使ったにしてはイマイチな威力だけど、shuffleが遅いのだろうか？

cython - 静かなる名辞

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

やりたいこと

pure pythonで書いたプログラム

cythonを使う

【python】pythonでボゴソートしてみる