Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Bookable.jp開発中

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート

はじめに

　恐らく、プログラマの中で配列内の要素を整列させたりするソートにお世話にならなかった人、というのは余り考えられないのではないでしょうか。しかし、とはいえ、大抵はソートを自前で実装せず、組み込み関数であったり、あるいは何らかのライブラリで済ませることが殆どだと思う。

　車輪の再発明というよりも、バグとか、自分が考慮していなかった挙動などを避けるために、自前でソートを組むことは余りないのですが、とはいえ、自分なりにソートを実装して見ると、それがどういう特徴を持ったソートであるか、というのがわかりますし、また、ソートというのはいったいどういう操作で実現されるのかという洞察が深まってくるなあ、という実感があったりする。

　なので、今回はあるソート二つについての話を書くのが趣旨です。

最高のアルゴリズムはある、だが最悪のアルゴリズムは何か

　一口にソートといったところで、ソート自体にも銀の弾丸があるというわけではない。

　例えば配列の要素数によって、爆発的にオーダーが増えたり、早かったとしてもメモリを食いまくったり、あるいはどれだけ汎用的に使われるかとか、色々なことが考えられます。「これを使っとけば完璧！」というのはないにしろ、ある程度「最適化されたソート」というのはそれなりにあったりするようす。

　で、そういうソートはたいてい課題になったり、実装する機会があるためか、大抵は少し漁れば言及されます。例えば、その典型例としてはクイックソート。

　とはいえ、ここでひとつ疑問が生まれる。

　「あれ、じゃあ実用的にならない遅いソート」って何だ、ということだ。

まずはバブルソート

　さて、この手のアルゴリズムにおいて、まず基準というか、簡単にして計算量が多いアルゴリズムとしてバブルソートがあります。バブルソートとは何か、ということに関しては、下の陽気な動画を見るのが手っ取り早い。


Bubble-sort with Hungarian ("Csángó") folk dance ...

　要するに、配列すべての要素に対して、次々と順番を入れ替えていく。要するに「泡があがってくる」かのようにソートされるわけだから、バブルっぽいよね、ということでバブルソートらしい。

　でまあ、この程度のソートくらいだったらRubyの練習がてらに書くのもいいかな、と思ったので、そういう風に書いて見た。

def my_bad_bubble_sort(target)
  target.each_with_index do |v1, p1|
    target.each_with_index do |v2, p2|
      if !(target[p2 + 1].nil? || target[p2].nil?) && v2 > target[p2 + 1]
        target[p2], target[p2 + 1] = target[p2 + 1], target[p2]
      end
    end
  end
  target
end

　明らかにRubyっぽくないのは勘弁してください。ポイントは、この関数を、ランダムにシャッフルした要素数100のArrayに対して1000回行ったときの回数です。とりあえずこれが一番簡単でかつ「そこそこに効率の悪い」ソートアルゴリズムの基準と出来ると思う。ちなみに、実行時間は下の通り。

real  0m3.055s
user  0m3.031s
sys   0m0.015s

　実は、バブルソートはもう少し効率のよい方法があるのだけれど、今回のブログの記事はそういう意図ではないので、今回は省略。

ボゴソートは非効率アルゴリズム界の王様なので考えない

　さて、そこでかの悪名高き「ボゴソート」。ボゴソートの擬似コード的概要は下の通り。

define ボゴソート(配列)
  もし配列がソートされてたら、配列の値を返す
  もし配列がソートされていなかったら、配列をシャッフルする
  最初に戻る

　これを繰り返したさい、ボゴソートの最悪オーダー数はInfinity、つまり無限回数の試行が必要になる。確かに、配列をランダムに入れ替えても「たまたま」それが意図した順番通りである可能性はある、というのはぱっとわかる。

　恐らく問題は、このソートは、次の試行によって、前の配列よりも、次の配列のほうがゴールに近くなるという保障が出来るないというところに起因するのかなと。で、このような性質、つまり「ゴールにたどり着くことはわかっているけれど、試行回数がゴールに向かうことを保障するわけではない」という意味で、ボゴソート自体は、もうこれは殿堂入りというか、非効率ソートにおいてのゴールとしておいていいという風に、いまのところは考えている。

そこでストゥージソートだ!

　さて、だいたい非効率ソートというのは、「ボゴソートよりも効率がよく、かつバブルソートよりも効率が悪い」範囲のソートである、という基準を設ければよいことがわかる。

　バブルソートは平均計算量がO(n2)として表現できる。このO()の部分が大きければ大きいほど、時間がかかるといえる。

　さて、そこで平均オーダー数O(nlog3/log1.5) = O(n2.7...)という遅いソートというのが存在している。それがストゥージソートだ。ストゥージソートというのは「三馬鹿大将」のスゥトージからきているようだ。要するにアホってことだ。

　ストゥージソート自体のアルゴリズムについては、実はWikipediaにのっている。そっちを参考にしてほしい。

　コードにすると、下のようになる。

def slowsort_p(target, i, j)
  if i >= j
    return target
  end
 
  m = (i + j) / 2
 
  target = slowsort_p(target, i, m)
  target = slowsort_p(target, m + 1, j)
 
  if target[m] > target[j]
    target[m], target[j] = target[j], target[m]
  end
  slowsort_p(target, i, j - 1)
end

　さて、バブルソートと同じ条件で実測してみると、下のようになる。

real  0m39.140s
user  0m39.010s
sys   0m0.093s

　馬鹿なんじゃないか。

おまけ

　実はプロトタイピングでClojureのやつも書いていたので、へっぽこだけど、そちらも公開しておく。

(defn stooge-sort 
  ([l] (stooge-sort l 0 (- (count l) 1)))
  ([l i j] 
     (let [prev-elem (nth l i)
           next-elem (nth l j)
           result-list (if (> prev-elem next-elem)
                         (change! l i j) l)]
       (if (>= (+ (- j i) 1) 3)
         (let [t (int (/ (+ (- j i) 1) 3))]
           (stooge-sort 
            (stooge-sort 
             (stooge-sort result-list i (- j t))
             (+ i t) j) i (- j t)))
           result-list))))

しかし、上には上が存在する。それがスローソートだ！

　しかし、ソートアルゴリズムで「クイックソート」という名前を見たときに、あることが思い浮かぶ筈だ。

　「あれ、クイックソートがあるんだったら、スローソートがあるんじゃないのか」

　そうだ、実際にスローソートはあるのだ。どういうものかについては、下の動画を見てほしい。


Slow Sort - YouTube

　ちなみに、slowsortについては論文もある。

　さて、これも愚直に実装してみよう。

def slowsort_p(target, i, j)
  if i >= j
    return target
  end

  m = (i + j) / 2

  target = slowsort_p(target, i, m)
  target = slowsort_p(target, m + 1, j)

  if target[m] > target[j]
    target[m], target[j] = target[j], target[m]
  end
  slowsort_p(target, i, j - 1)
end

　なんも問題がなさそうに見える。では、これを実測すると。

real  12m9.378s
user  12m3.486s
sys   0m2.420s

　馬鹿じゃないのか(二回目)。

おまけ: Clojure

　これも、Clojure版を書いているので、それも参考がてらに貼っておく。

(defn slowsort 
  ([l] (slowsort l 0 (- (count l) 1)))
  ([l i j]
     (if (not (>= i j))
       (let [m (int (/ (+ i j) 2))]
         (let [result-list
               (slowsort 
                (slowsort l i m)
                (+ m 1) j),
         prev-elem (nth result-list m)
         next-elem (nth result-list j)
         swap-result-list (if (> prev-elem next-elem)
                            (do (println result-list) 
                              (change! result-list m j))
                            result-list)]
           (slowsort swap-result-list i (- j 1)))) 
       l)))

さあ、最弱アルゴリズムの世界へ

　というわけで、今回はバブルソートよりも非効率なソートアルゴリズム二つについて紹介してみた。実はほかにもあるようだし、またそういう情報があって実装してほしいものがあれば、ご教授頂ければ幸いである。実際、「画期的に遅いソート」を実装するのは案外面白かったというのが正直な感想だ。

　もちろん、プログラムというのは、ある部分は効率性を求めるような仕事であることはわかる。しかし、それは同時に「非効率」というのが何なのか、という裏の理解もまた重要であるような気がする。そういう意味で「ダメアルゴリズム」を実装するというのは、そういう洞察を得られてよい。

補足:　スリープソートについて

　とはいえ、ここまで書くと「あれ、スリープソートを抜かした理由は?」というのがあるかもしれない。スリープソートはそもそも、アルゴリズムとしては別ベクトルのもの(ある意味、外部環境を利用したソート)ではあるので、単純に「非効率か」といわれれば、なかなか難しいところではある。そのあたりの議論については、下が参考になる。

元ネタ

　ちなみに、この記事は、下のStackoverflowを参考にした。

　いろいろ面白いネタはあるんだけど、個人的にツボになったのは、MiracleSortだ。

def MiracleSort(some_array)
  some_arrayがソートされているなら、値を返す
　some_arrayがソートされていなければ、暫く待ち、最初に戻る
end

参考文献

入門 データ構造とアルゴリズム

入門 データ構造とアルゴリズム

　個人的にお気に入り。もちろん解りにくかったり、演習が多かったりなどの、かなり硬派な本ではあり、鈍器のように、中身もページ数も重い本だけど、手元にあると安心するという意味で、とてもよい。