Keep on moving

あんまりまとまってないことを書きますよ

ソート勉強中

どうも今晩は、よく本業で何やってるのか謎の人と言われます。今後ともよろしくお願いします。

調子に乗って何回か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"

「なるほど、これはバケットソートなんじゃねーの。配列の代わりに時間を使ってるけどね。」ってことらしいですね。

実はバケットソートって初めて聞いたので調べてみました。

バケットソート - Wikipedia

なるほど、

  1. 最大の数分の入れ物をつくる
  2. 配列の中身を全て見て、入れ物に入れて行く
  3. 入れ物の中身をみて、出現数結果用の配列に格納して返す

ってことみたいです。

早速書いてプロファイルをとってみました。比較対象は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

やっぱりビルトイン関数は速いですね。