Pythonでスリープソートっぽいことをやる。

最近スリープソートが話題になってたのでPythonでやってみる

import time
import threading

num = [9,4,1,6,0,30,2,5,7,8,20,14]    #今回はこいつをソートする。別にグローバル変数である必要はない。

def sleep_sort(i, result):
    result.append(i)
    print result

def main():
    global num
    result = []
    for i in range(len(num)):
        t = threading.Timer(num[i], sleep_sort, args = [num[i], result])
        t.start()

if __name__ == '__main__':
    main()

実行結果

[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 4]
[0, 1, 2, 4, 5]
[0, 1, 2, 4, 5, 6]
[0, 1, 2, 4, 5, 6, 7]
[0, 1, 2, 4, 5, 6, 7, 8]
[0, 1, 2, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 4, 5, 6, 7, 8, 9, 14]
[0, 1, 2, 4, 5, 6, 7, 8, 9, 14, 20]
[0, 1, 2, 4, 5, 6, 7, 8, 9, 14, 20, 30]

ソートにかかった時間は約30秒。リストに格納されてる数値で1番でっかいのが30だからまあそうなるよね。

リストに格納されている数値をresultに入れなおしている。今回はthreading.Timerを使った。

・http://www.python.jp/doc/2.6/library/threading.html#timer

threading.Timer(止める秒数, 実行する関数, args = [関数の引数])

こんな感じで、引数は[]で囲まないといけない。
t.start()でスレッドを実行する。
forループの中でスレッドを入れてる変数がどんどん上書きされてしまっているので、どっかのスレッドにアクセスしたい場合には空リストでも作ってappendしながらループさせるといいかもしれない。

参考
・常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream
・常識を覆すソートアルゴリズム！その名も「sleep sort」！ | ◆めっつぉ：スクエニ&ガジェットニュース
・http://d.hatena.ne.jp/mizchi/20110520/1305837948