:-): 朝ったー, 通勤ったー, 仕事, がらくたを読む - bsearch.rb, おやつ

2008-02-27 :-)

_ 朝ったー

0540 起床。ふむ

_ [仲野順也][浜渦正志][植松伸夫][ファイナルファンタジーX]通勤ったー

ファイナルファンタジーX

ゲームは 1 度プレイしました。作曲は仲野順也さん、浜渦正志さん、植松伸夫さん。プレイステーション2での最初の FF です。PS2 であるからか、音が FF 9 までと比べて格段にリアルになっています。作曲 3 人が各々の味を生かした曲を書いているので多様な曲を楽しめます。とくに各々の特徴が出ている曲がラストダンジョンでのバトル曲です。以下 3 つ。

シーモアバトル：シーモア戦。作曲は植松伸夫さん。裏切るような曲[ 20071020#p01 ]です。
召喚獣バトル：召喚獣戦。仲野順也さん。基礎になるゆったりしたメロディの上に速いリズムの音を乗せています。とても激しい曲です。仲野順也さんらしいバトル曲です。
決戦：エボン・ジュ戦。浜渦正志さん。基礎のメロディに「祈りの歌」を使い、その上に力強いピアノの音を乗せています。

リアルに近い音というかまさにリアルの音だろう、という曲が「スピラの情景」です。実際にアコースティックギターで演奏してるのではないかという曲です。ボディーを叩く音や弦を引く(？)「キュイッ」という音が聴こえます。ライブで演奏するひとが居たら惚れます。

B00025E1UI

_ 仕事

0830 出勤。

_ [珠玉のプログラミング][Ruby][2分探索][コードリーディング][がらくた][高林哲]がらくたを読む - bsearch.rb

配列を 2 分探索するライブラリです。配列要素はあらかじめソートしておく必要があります。

http://0xcc.net/attic/bsearch.rb

これの多機能版が Ruby/Bsearch: 配列を 2分探索する Ruby用のライブラリにあるんですが「がらくた」のほうを読みます。Ruby/Bsearch のほうに説明図があるのであわせて読むといいです。

コメント部分にアルゴリズムの説明が書いてあります。

 #
 # This method searches the FIRST occurrence which satisfies a
 # condition of a given block in binary fashion.
 #
 # This algorithm is extracted from Jon Bentley's
 # Programming Pearls 2nd ed. p.93
 #

Programming Pearls 2nd ed の p.93 にあるよ、ということですが私は Programming Pearls 2nd ed は持ってません。その邦訳「珠玉のプログラミング」は持ってるので珠玉のプログラミングを見てみます。おそらく珠玉のプログラミング「 9.3 大手術的なコードチューニング - 2 分探索で」 p.117 のことだと思います。p.117 に擬似コードがあります。

l = -1; u = n
while l+1 != u
  /* 不変な表明:x[l] < t && x[u] >= t && l < u */
  m = (l + u) / 2
  if x[m] < t
    l = m
  else
    u = m

/* l+1 = u && x[l] < t && x[u] >= t となっているはず */
p = u
if p >=n || x[p] != t
  p = -1

ここで

x: 探索する配列
t: 探索する値
p: 発見した位置。存在しなければ -1
u: 探索範囲の上限( Upper )
l: 探索範囲の下限( Lower )

「不変な表明」とは「 assert みたいなもの」とのことです( p.44 )

コードを読みます。

class Array
  def bsearch_first
   :
  def bsearch_last
   :
  def search
   :

Array クラスを再定義し Array クラスに bsearch_first, bsearch_last, search メソッドを追加しています。

簡単なところから def search を読みます。

 #
 # brute force sequential search.
 #
 def search
   self.each_with_index {|x, i|
     return i if yield(x) == 0
   }
   nil
 end

コメントにあるとおり、線形探索します。Ruby の Array クラスが持っている each_with_index メソッドを使って Array の要素をすべて処理します。x に要素、i にインデックス番号が入ります。以下のように使います。

% ruby -rbsearch.rb -e 'p [0, 1, 2, 3, 4, 5].search{ |x| x <=> 3 }'
3

面白いのは整数だけでなくて文字でも探索できるところです。

% ruby -rbsearch.rb -e 'p ["a", "b", "c", "d"].search{ |x| x <=> "c" }'
2

yield(x) は Array.search メソッドの呼び出し側のブロックへ x を渡します。yield を初めて見たときにさっぱり理解できなくて「Ruby プログラマってのはすごいなあ」とカルチャーショックを受けたのですが、荒く言うと、メソッドにブロックをぶん投げて処理させる、という機能です( らしいです )。

def bsearch_first を読みます。Programming Pearls 2nd ed. p.93 を実装してます。

  def bsearch_first
    low = -1
    high = self.length
    while low + 1 != high
      mid = (low + high) / 2
      if yield(self[mid]) < 0
        low = mid
      else
        high = mid
      end
    end

    if high >= self.length || yield(self[high]) != 0
      return nil
    else
      return high
    end
  end

この下で alias してます。