リニアサーチ

12月 5th, 2007 admin Posted in Ruby, アルゴリズムとデータ構造 | 1 Comment »

最初に扱うのはリニアサーチという、配列なら先頭から順番に探索していくという最も単純なアルゴリズムです。
ソートのアルゴリズムで一番単純なバブルソートがバカ扱いされていたのに対して、こちらのアルゴリズムは「応用範囲が広く、意外と頻繁に利用されている」と紹介されています。

番兵（番人）

普通にwhileで書こうと思うと

while (探索の数字ではない) and (配列の最後でない)
   i += 1
end

みたいな感じで、常に配列の最後まで探索したかどうかを調べる必要があると思う（var.eachとかは自動でやってくれる）
しかも毎回毎回それを調べるのはコストがかかる、そのコストをなくすのが番兵である。
どういうことかというと、あらかじめ配列の最後に探索する数字をいれてから探索を行う。こうすれば必ず最後には探索する数字が見つかる。
探索が終わってからキーの値が最後の数字なら、それはNOT FOUNDだったということになる。
この説明では分からない人が多いと思うので「番兵 – Wikipedia」とかをみて欲しい。

コード

#リニアサーチ（番兵版）
require 'pp'
before = Time.now
t = Time.now
srand(t.sec ^ t.usec ^ Process.pid)

#探索する要素数
Num = 10000

def linearSearch(target,a)
	n = 0
	t = a[Num-1]
	a[Num-1] = target
	while target != a[n]
		n+=1
	end

	a[Num-1] = t
	if n < (Num-1)
		return n
	end
	if target == t
		return n
	end

	return -1
end

#ランダムな値の入った配列を作成
a = Array.new
Num.times{|i|
	a.push i
}

#探す数値
target = rand(Num)

#出力
p "serch:" + target.to_s
pp a

p linearSearch(target,a);

#処理時間
p Time.now - before

ふつうのRuby

普通にRubyで書くと関数部分はこう書き換えられる

def linearSearch(target,a)
	a.index(target)
end

キーの値を必要としないのならarray.include?で真偽値を得られる

まとめ

Rubyではi++という書き方がないらしく10分ぐらい悩んだ。MLになぜならiはオブジェクトだからで・・というRubyっぽい説明がありました
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-list/126

※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。