はじめてのrubyプログラム

オライリーの「はじめてのruby」と「プログラミング言語 ruby」を読みながら、とりあえずrubyで初めてのプログラムを書いてみた。

Arrayクラスを拡張して、二分探索メソッド(binary_search)を追加。

まぁ……そんな大した実装ではないんだけどね　笑

---

# MyArray.rb
#
class Array

private
  def _bsearch(val, begin_idx, end_idx)
    
    center_idx = begin_idx + ((end_idx + 1) - begin_idx) / 2
    
    element_val = self[center_idx]
    
    ret_index = if val == element_val then
                  center_idx
                elsif begin_idx == end_idx then
                  nil
                elsif val < element_val then
                    _bsearch(val, begin_idx, center_idx - 1)
                else
                    _bsearch(val, center_idx + 1, end_idx)
                end
    ret_index
  end
  
public
  def binary_search(val)
    _bsearch(val, 0, self.length - 1)
   end
end

# test

#↓の配列は 20.times.map{|i| srand(i); rand(100)} をirb上で実行して入手
arr = [44, 37, 40, 24, 46, 99, 10, 47, 67, 92, 9, 25, 75, 82, 88, 72, 41, 15, 42, 93]
arr.sort!
p arr

index = arr.binary_search( 67 )
puts "index of '67' is #{index}"

実行結果：

C:\Users\admin\rb_workspace>ruby MyArray.rb
[9, 10, 15, 24, 25, 37, 40, 41, 42, 44, 46, 47, 67, 72, 75, 82, 88, 92, 93, 99]
index of '67' is 12

この２分探索メソッド、普通にArray#eachメソッド(先頭からシーケンシャルに配列アクセスして要素を調べる方法)でデータを探すのと比べた場合、少量の要素の配列では差が出ない。
そこでランダム数値の要素を100万個まで増やしてみたら、ほぼ平均して二分探索の方が速いことが分かった。

これは上記のクラス定義をそのままにしてテストコードを以下のように変えて試してみると良くわかる。

arr = 1000000.times.map{|i| srand(i); rand(9999999)}
arr << 1000000
arr.compact!
arr.sort!
puts("size of array is #{arr.length}")
puts(Time.now.to_i)
index = arr.binary_search( 1000000 )
puts "index of '1000000' is #{index}"
puts(Time.now.to_i)

puts(Time.now.to_i)
arr.each_with_index do |v, i|
  if v == (1000000) then
    puts "index of '1000000' is #{i}" 
    puts(Time.now.to_i)
    break;
  end
end

上記コードの「1000000」となっている部分は検索対象の配列要素の値で、これが大きい値ほど、検索する配列の後方に配置される仕掛けになっている。
それでこの値を「2000000」としたり、「5000000」、「9999999」としてみると、筆者の環境では要素の値が「1000000」、配列上のインデックスが99933のとき、両者の速度はほぼ一致した。従って配列上のインデックスがそれよりも前の場合、両者の速度はほとんど遜色ないと思われる。

逆に値が「2000000」、先頭からのインデックスが200046の要素を検索したときには既に1秒近くの差が開き始めており、その差は配列の後半にある要素を検索すればするほど大きくなっていった。つまり、約7割から8割の要素の検索において二分探索アルゴリズムの方が高速に動作したと結論づけられる。

この例はアルゴリズムの理論の確認には役にたつかもしれないが、極端に大きな配列でないとこの効果を確かめることはできないので、実用上ほとんどの場合は無視しても構わないだろう。大体はArray#eachで事足りると推測できそうだ。

---

それにしても組込データ型ですら実行時に拡張できるとは恐れ入った。（恐らく発想自体はLispあたりから受け継いだのではないかと思うのだけれども定かではない）。これはC/C++にはない発想だし、Javaにもないんじゃないの？