takulab

「Webスケールとインターネットクラウド」開催

第2回「Webスケールとインターネットクラウド」｜情報処理学会 連続セミナー2010

7月26日に東京電機大学で丸山先生や首藤先生によるクラウド関連のセミナーがあったらしい。

丸山先生による「クラウドの成立過程と、その技術的特徴について」の講演資料を

http://maruyama.cloud-market.com/download/IPS2010.pdf

で見ることができる。

内容はこれまでに出てきてる話のまとめ。

クラウド全体を俯瞰するにはいい資料だと感じた。

「Googleクラウドの核心」 発売決定

Googleが語るデータセンター「The Datacenter as a Computer」の翻訳版「Googleクラウドの核心」が発売 | P2P today ダブルスラッシュ

ということで、The Datacenter as a Computerの日本語版が出版されるとのこと。

Googleクラウドの核心

なお、英語版であれば

The Datacenter as a Computer

で読むことができるので、こっちを読んだ方が正しい情報が得られる可能性は高そう。

Cassandra入門

Cassandra入門と、さらに詳しく知るためのリソース集 ? Publickey

というCassandraのまとめ記事。

様々な資料を見ることができる点がGood。

興味はあるものの今まで触ったことはないので、夏休み中に少し触ってみる予定。

CassandraをJavaやRubyで使ってみたというコチラの記事も参考になりそう。

Cassandra まとめ – akishin999の日記

前回の 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は必要なさそう...。

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

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)かかってしまう