takulab

前回の Rubyでアルゴリズム 第01回 ~バブルソート編~ に続いて、今回はクイックソートに取り組んでいく。

クイックソートって？

例のごとくWikipediaを見てみると、

クイックソートは、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。

最良計算量および平均計算量はO(n log(n))>である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO(n^2)である。また数々の変種がある。 安定ソートではない。

wikipedia:クイックソート

どういう風にソートを行うのかはこれだけでは分かりにくいが、安定ソートでないといった特徴を把握した上で活用すれば役立ちそうだと推測できる。

具体的なソートの方法は？

簡単に説明すると、

1. 要素の中から軸(ピポット)を1つ決める
2. その軸より小さい値と大きい値のグループに分ける
3. それぞれのグループで1.2を実行する
4. それ以上は分割できない状態になればソーティング終了

という方法によりソーティングが可能である。

ちなみに軸の選び方は
 (1)完全にランダムに選ぶ
 (2)適当な３つの値の中央値を選ぶ
といった様々な変形パターンが存在する。

実装

今回の実装は様々な戦略のうち、軸をランダムに選ぶ方法で実装を行った。

class Array
  def sort
    quickSort(self, 0, self.length-1)
  end
 
  def quickSort array, left, right
    if left > right then
      pi = partition(array, left, right)
      quickSort(array, left, pi-1)
      quickSort(array, pi+1, right)
    end
  end
 
  def partition array, left, right
    p = left + rand(right - left)
    self[p], self[right] = self[right], self[p]
    store = left
    (left..right-1).each do |i|
      if array[i] <= array[right] then
        self[i], self[store] = self[store], self[i]
        store += 1
      end
    end
    self[store], self[right] = self[right], self[store]
    return store
  end
end

まとめ

• 最良時、平均時には O(n log(n)) でソートが可能。
• 軸を選択するときに常に左端、または右端を選んでしまうと最悪時になり、O(n^2)の計算時間がかかる
• 軸の選択方法、要素が少なくなると挿入ソートに切り替える等の亜種が存在する

追記 2010/07/28

よく考えるとquicksortとpartitionの引数arrayは必要なさそう...。

そのうちもう一度考える。

デバッグしていて、あるメソッドが複数の場所から呼ばれることがある場合、どこからメソッドが呼ばれているのか特定したいときがある。そんな時にはスタックトレースを表示するのが便利。

Javaでは、以下のように記述すれば、呼び出し元のクラス名、メソッド名を出力できる。

StackTraceElement[] e = new Exception().getStackTrace();
for (StackTraceElement element : e)
System.out.println(element.getClassName() + "," + element.getMethodName());

参考サイト

Java: メソッドの呼び出し元を調べる方法 – sardineの日記

Rubyを学びつつアルゴリズムも復習し直そうということで、1日1記事を目標にやっていけたらと思っている。記念すべき初回である今回はバブルソートを実装。

バブルソートって？？

Wikipediaにはこんな風に書いてある。

バブルソート(bubble sort)は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n^2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。

wikipedia:バブルソート

簡単に言うと、隣り合う要素を順々に比較して要素の順序を入れ替えるという操作を全ての要素に行うことで整列を行うといったとこだろうか。

実装

Arrayクラスのsortメソッドをオーバーライドしてみた。

class Array
    def sort
        unsorted_length = self.length-2
        begin
            unsorted = false
            (0..unsorted_length).each do |i|
                if(self[i] > self[i+1])
                    unsorted = true
                    self[i], self[i+1] = self[i+1], self[i]
                end
            end
            unsorted_length -= 1
        end while (unsorted)
    end
end

今回Rubyを書いていて、

self[i], self[i+1] = self[i+1], self[i]

Cだと、一時変数なんかを使って、

tmp = self[i]
self[i] = self[i+1]
self[i+1] = tmp

この辺が、Rubyが直感的に理解しやすいコードが書けると言われている所以なのかと想像。

バブルソートのまとめ

少し脇道に反れたが、最後にまとめ。

• アルゴリズムが簡単で、実装も楽
• 最悪時は計算時間がO(n^2)かかってしまう

manを引けば分かる話だが、よく使い方を忘れるので一度まとめてみる。

構文

$ nkf オプション ファイル名 [> 出力ファイル名]

オプション一覧

-j 　        : JISコード(ISO-2022-JP)を出力
-e           : EUCコードを出力
-s           : Shift-JISコードを出力
-w           : UTF-8コードを出力（BOM無し）
-Lu          : unix改行形式(LF)に変換
-Lw          : windows改行形式(CRLF)に変換
-Lm          : macintosh改行形式(CR)に変換
-g(--guess)  : 自動判別の結果を表示
--overwrite  : 引数のファイルに直接上書き
--version    : バージョン情報を表示(インストール済チェック)

使用例

以下は使い方の例。

文字コードチェック

$ nkf -g example.csv
Shift_JIS

文字コード変換(UTF-8)

$ nkf -w--overwrite example.csv

よくやってしまう失敗例

$ nkf -w example.csv > example.csv

上書きでいい場合は–overwriteオプションをつける。

そうでない場合はmvなどでファイル名を変更して使う必要がある。

何かの処理時間を測定したいときに便利。

Benchmarkモジュールを利用する。

require "benchmark"
puts Benchmark::CAPTION
puts Benchmark.measure{
    process()
}

require "benchmark"
N = 1000
array = Array.new( N )
(0..N).each do |i|
    array[i] = rand(10000)
end
puts Benchmark::CAPTION
puts Benchmark.measure{
    array.sort
}

ちなみに単位は秒。

user     system      total        real
0.000000   0.000000   0.000000 (  0.000158)

参考サイト

benchmark – Rubyリファレンスマニュアル

そろそろ夏休みということで、授業もなくなり少し時間ができそう。

ということで、時間があるうちに基礎的なことを勉強し直したいと思い、以下の本を購入。

Operating System Concepts

こちらは、Operating Systemについての標準的な教科書。

Operating System Concept

アルゴリズムクイックリファレンス

クイックリファレンスといいながらも、アルゴリズムの定量的な比較までしてあり、よくまとまっているという印象。実用的なコードも数多く書いてあるので、手元に1冊は欲しい本。

アルゴリズムクイックリファレンス

ちなみに、コンピュータサイエンスについての良著はこのブログによくまとまっている。

Leo’s Chronicle: ぜひ押さえておきたいコンピューターサイエンスの教科書

Bashによる引数の展開

以下のように記述すると、bashによって自然に展開される。

$ cp some/deep/path/{foo,bar}.xml
↓
$ cp some/deep/path/foo.xml some/deep/path/bar.xml

深い階層のファイルをバックアップする場合

普通にコマンドを書くと次のように結構記述が長くなるが、以下のように書くこともできる。

$ cp some/deep/path/hoge.txt some/deep/path/hoge.txt.bak
↓
$ cp some/deep/path/hoge.txt{,.bak}

Bashによる引数の再利用

次のようにファイルをコピーしたうえで、そのファイルをエディタを使って編集などの作業をよく行うことがある。

$ cp some/path/hoge.txt some/path/fuga.txt
$ vi some/path/fuga.txt

$ cp some/path/hoge.txt some/path/fuga.txt
$ vi !:2

基本的に「ビックリマーク＋コロン＋引数の位置」の組み合わせなので覚えやすい。