Counting Sort(Python/Numpy)

理論的には,「分布の範囲が分かっている時最速」と云われるが,
実際的には,最大,最小を求める計算コストはそれ程大きくないので,
分布形状によってどっちのほうが速いかって感じ.

Pythonの標準ソート(Tim sort)と比べても遜色ない結果.
Cythonizeすれば,counting sortの方がリーズナブルかも(空間効率は悪いけど).

import numpy as np


def counting_sort(arr, low=None, high=None):
  if low is None:  low = min(arr)
  if high is None:  high = max(arr)
  res = [0] * len(arr)
  cnt_arr = [0] * (high+1 - low)
  for x in arr:
    cnt_arr[x-low] += 1
  for i in range(1, len(cnt_arr)):
    cnt_arr[i] += cnt_arr[i-1]
  for k in reversed(arr):
    res[cnt_arr[k-low] - 1] = k
    cnt_arr[k-low] -= 1
  return res


lst = [3, 1, 2, 5, 5, 3, 4, -1, -5, 10]
print(sorted(lst))
print(counting_sort(lst))
%timeit sorted(lst)
%timeit counting_sort(lst)
%timeit counting_sort(lst, -5, 10)

lst *= 10000
%timeit sorted(lst)
%timeit counting_sort(lst)
%timeit counting_sort(lst, -5, 10)

lst = np.random.randint(-100, 100, size=10000).tolist()
%timeit sorted(lst)
%timeit counting_sort(lst)

lst = np.random.randint(-10000, 10000, size=10000).tolist()
%timeit sorted(lst)
%timeit counting_sort(lst)

lst = np.random.randint(-1000, 1000, size=1000000).tolist()
%timeit sorted(lst)
%timeit counting_sort(lst)

lst = np.random.randint(-10000, 10000, size=1000000).tolist()
%timeit sorted(lst)
%timeit counting_sort(lst)
[-5, -1, 1, 2, 3, 3, 4, 5, 5, 10]
[-5, -1, 1, 2, 3, 3, 4, 5, 5, 10]
1000000 loops, best of 3: 501 ns per loop
100000 loops, best of 3: 5.07 µs per loop
100000 loops, best of 3: 4.41 µs per loop

100 loops, best of 3: 9.46 ms per loop
10 loops, best of 3: 27.7 ms per loop
10 loops, best of 3: 24.9 ms per loop

100 loops, best of 3: 2.18 ms per loop
100 loops, best of 3: 2.94 ms per loop

100 loops, best of 3: 2.52 ms per loop
100 loops, best of 3: 6.66 ms per loop

1 loop, best of 3: 386 ms per loop
1 loop, best of 3: 399 ms per loop

1 loop, best of 3: 555 ms per loop
1 loop, best of 3: 515 ms per loop

NumpyでCounting Sort

counting sortはNumpyで実装すると本当にシンプルに書けて,

def np_counting_sort(a):
  arr = np.asarray(a)
  return np.arange(arr.max()+1).repeat(np.bincount(arr))

上記同様,負値も考える場合は,

def np_counting_sort(a):
  arr = np.asarray(a)
  r = arr.min()
  arr -= r
  return np.arange(arr.max()+1).repeat(np.bincount(arr)) + r


lst = [3, 1, 2, 5, 5, 3, 4, -1, -5, 10]
np_counting_sort(lst)
array([-5, -1,  1,  2,  3,  3,  4,  5,  5, 10])

numpy.sort(デフォルトはクイックソート)よりもかなり速い.

lst = [3, 1, 2, 5, 5, 3, 4, -1, -5, 10]
%timeit np.sort(lst)
%timeit np_counting_sort(lst)

lst *= 10000
%timeit np.sort(lst)
%timeit np_counting_sort(lst)

a = np.random.randint(-100, 100, size=10000)
%timeit np.sort(a)
%timeit np_counting_sort(a)

a = np.random.randint(-10000, 10000, size=10000)
%timeit np.sort(a)
%timeit np_counting_sort(a)

a = np.random.randint(-1000, 1000, size=1000000)
%timeit np.sort(a)
%timeit np_counting_sort(a)

a = np.random.randint(-10000, 10000, size=1000000)
%timeit np.sort(a)
%timeit np_counting_sort(a)
100000 loops, best of 3: 3.74 µs per loop
100000 loops, best of 3: 12.7 µs per loop

100 loops, best of 3: 7.31 ms per loop
100 loops, best of 3: 6.18 ms per loop

1000 loops, best of 3: 444 µs per loop
10000 loops, best of 3: 85.4 µs per loop

1000 loops, best of 3: 586 µs per loop
1000 loops, best of 3: 268 µs per loop

10 loops, best of 3: 61.7 ms per loop
100 loops, best of 3: 8.95 ms per loop

10 loops, best of 3: 76.8 ms per loop
100 loops, best of 3: 9.92 ms per loop
広告
カテゴリー: 未分類 パーマリンク

Counting Sort(Python/Numpy) への2件のフィードバック

  1. ピンバック: numpyで異なる繰り返し値を持つインデックスを繰り返す | 粉末@それは風のように (日記)

  2. ピンバック: 2D Numpy配列で最初の要素が重複している行の平均 – 2Dなnumpy.ndarrayの最初の要素(1列目)で各行をグルーピングして集計(平均を算出) | 粉末@それは風のように (日記)

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中