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

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

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が遅いのだろうか？

静かなる名辞

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

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