どうも今晩は、よく本業で何やってるのか謎の人と言われます。今後ともよろしくお願いします。
調子に乗って何回かsleep sortの話を書きました。
http://dis.4chan.org/read/prog/1295544154/22
Genius sorting algorithm: Sleep sort 22 Name: Anonymous : 2011-01-20 17:12 This is sort of like a simple bucket/radix sort but instead of using a space-based array, it's effectivly using a time-based "array"
「なるほど、これはバケットソートなんじゃねーの。配列の代わりに時間を使ってるけどね。」ってことらしいですね。
で
実はバケットソートって初めて聞いたので調べてみました。
なるほど、
- 最大の数分の入れ物をつくる
- 配列の中身を全て見て、入れ物に入れて行く
- 入れ物の中身をみて、出現数結果用の配列に格納して返す
ってことみたいです。
早速書いてプロファイルをとってみました。比較対象はpythonクックブックに載っていた1行クイックソートを使ってみます。
#!/usr/bin/env python def bucket_sort(arr): """ >>> bucket_sort([9, 4, 3, 6, 7, 8, 2, 5, 1, 10]) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] >>> bucket_sort([0, 1, 0, 3, 2, 0, 1, 2, 0, 1]) [0, 0, 0, 0, 1, 1, 1, 2, 2, 3] """ count = [0] * ( max(arr) + 1) for value in arr: count[value] +=1 result = [] for num, times in enumerate(count): result.extend([num] * times) return result # Pythonクックブックより def qsort(L): if len(L) <= 1: return L return qsort([lt for lt in L[1:] if lt < L[0]]) + L[0:1] + qsort([ge for ge in L[1:] if ge >= L[0]])
In [1]: import bucket_sort In [2]: import random In [3]: p_list = random.sample(range(100),100) In [4]: timeit -n 100 bucket_sort.bucket_sort(p_list) 100 loops, best of 3: 80.9 us per loop In [5]: timeit -n 100 bucket_sort.qsort(p_list) 100 loops, best of 3: 346 us per loop In [6]: timeit -n 100 sorted(p_list) 100 loops, best of 3: 21.9 us per loop
やっぱりビルトイン関数は速いですね。