キュー

5月 8th, 2008 admin

今日も「アルゴリズムとデータ構造シリーズ」です。本日は「キュー」について。本当はスタックで逆ポーランド記法の式の計算をする予定でしたが面白くないのでスキップします。（逆ポーランド変換ならトライしますが）

キューとは

キューとは最初に入れたデータを最初に取り出すと言う特徴を持つデータ構造。行列などに例えられる。
「先入れ先出し」「First in first out(FIFO)」などと呼ばれる

キューではデータを入力することを「エンキュー」「push」などと表現し、出力させることを「デキュー」「pop」と表現する。
スタックに比べるとキューはWi○MXのあれとかプリンタのあれとか、そもそもqueueの直訳が待ち行列ですって感じで説明しやすい。

キューのデータ構造を配列で表現しようとするととても大きな配列が必要になるため、適当な大きさの配列の頭とお尻をくっつけて使う「リングバッファ」という方法がよくとられます。
リストを使ってキューを実現すればこの問題は発生しないのですが、今回は勉強なのでリングバッファを使ったキューを実装しました。

コード

PLAIN TEXT
RUBY:
  1. #Queue
  2. $KCODE = "SJIS"
  3. QUEUE_EMPTY = -1
  4.  
  5. class Queue
  6.   def initialize(max)
  7.     @queue = Array.new()
  8.     @max = max
  9.     @first = 0
  10.     @last = 0
  11.   end
  12.  
  13.   def enqueue(val)
  14.     if((@last + 1)%@max == @first)
  15.       p "ジョブが満杯です"
  16.     else
  17.       @queue[@last] = val
  18.       @last = (@last+1)%@max
  19.     end
  20.   end
  21.  
  22.   def dequeue()
  23.     ret = nil
  24.     if @first == @last
  25.       return QUEUE_EMPTY
  26.     else
  27.       ret = @queue[@first]
  28.       @first = (@first+1)%@max
  29.       return ret
  30.     end
  31.   end
  32.  
  33.   def print_all()
  34.     i = @first
  35.     while i != @last
  36.       print @queue[i].to_s + " "
  37.       i = (i+1)%@max
  38.     end
  39.     print "\n"
  40.   end
  41. end
  42.  
  43. queue = Queue.new(5)
  44. i = nil
  45. while i != 0 do
  46.   print "現在のキュー\n"
  47.   queue.print_all
  48.   print "コマンドを入力して下さい\n0:終了 1:ジョブをためる 2:ジョブを実行\n"
  49.   i = gets.chomp.to_i
  50.  
  51.   case i
  52.     when 1
  53.       print "ジョブの識別番号（1~1000）を適当に入力してください："
  54.       j = gets.chomp.to_i
  55.       queue.enqueue(j) if (j>= 1 && j <= 1000)
  56.  
  57.     when 2
  58.       j = queue.dequeue
  59.       if j == QUEUE_EMPTY
  60.         print "ジョブがありません\n"
  61.       else
  62.         print "識別番号" + j.to_s + "のジョブを実行\n"
  63.       end
  64.   end
  65. end

実行画面
queue.gif

まとめ

キューを使うようなプログラムを書いてみたいと思った。キューかっこいい！
あと、BASICみたいなプログラムが書けておもしろかった。

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

Posted in Ruby, アルゴリズムとデータ構造, 今日のコード | 1 Comment »

リスト

4月 17th, 2008 admin

久しぶりの「アルゴリズムとデータ構造シリーズ」です。今回はリスト構造についてです。

C言語では配列を使うときは配列のサイズを宣言する必要があります。しかし配列のサイズがあらかじめわかる場合はいいのですが、いくつ入力があるかわからないときは困ったことになります。そこでリストというデータ構造を使って無限に要素数を増やせる配列のようなものを作ります。

C言語でも一つ増やすときに今よりひとつ大きいサイズの配列を確保してそちらに引っ越すという方法がありますが、あまり効率とは言えません。

データ構造

リストの要素（ノードとかいう）を「データ・次のノードへのポインタ・前のノードへのポインタ」という形式で用意して、ノード同士がそれぞれの前後のデータの場所を記憶しておくというデータ構造。

誰が前の人で、誰が後ろの人かは知っている。だけど全体は（そのサイズすら）しらない。
町内の回覧板みたいなシステムですね。

次の人だけを知っているリストを「単方向リスト」、前後の人を知っているリストを「双方向リスト」と言います。

コード

Rubyなのでデータをオブジェクト、ポインタは参照で表現しました。

PLAIN TEXT
RUBY:
  1. class Node
  2.   attr_accessor :prev,:next,:data
  3.  
  4.   def initialize(data)
  5.     @data = data
  6.   end
  7. end
  8.  
  9. firstnode = lastnode = nil
  10.  
  11.  
  12. datas = [1,2,3,4,5,6,7,8,9]
  13. datas.each do |x|
  14.   node = Node.new(x)
  15.   node.next = nil
  16.  
  17.   unless lastnode.nil?
  18.     lastnode.next = node
  19.     node.prev = lastnode
  20.     lastnode = node
  21.   else
  22.     firstnode = lastnode = node
  23.     node.prev = nil
  24.   end
  25. end
  26.  
  27.  
  28. p firstnode.next.next.prev.data

出力

2

まとめ

配列というと僕の場合は入門書とかにでてくる分別できるゴミ箱みたいなのが頭に浮かぶ。2次元配列になったとしても思い浮かぶのは玉子のパックだ。だけどリストを思い浮かべてみるとかなりカッコいい！頭に浮かぶのはイタリアのマフィア。自分の部下とボスは知っているがボスのボスは知らないし（知れない）、自分の部下がどんな部下を使っているのかも知らない（知る必要がない）。組織のサイズも知らないし関係ない。とにかくボスの命令を遂行するだけ・・・単にJOJO脳になってるだけですね。はい。

ちなみに僕の家の回覧板の場合は、誰が持ってくるか知らないので単方向リストです。いつも勝手にポストにはいってます。

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

Posted in Ruby, アルゴリズムとデータ構造 | 7 Comments »

バイナリサーチ

12月 16th, 2007 admin

今回はバイナリサーチ（二分探索です。サーチといえばバイナリサーチというぐらい有名です。
ランダムに並んだ配列データをサーチする場合において、これ以上速い方法はないそうです。

考え方は難しくないし、日常生活でも自然に使っていたりします。

アルゴリズム

データをソートする
まず真ん中の値をチェックして、それより大きいか小さいかを判断する。
大きければ、小さかったほうの探索はもうしない。次に大きいほうの配列の真ん中の値をチェック・・・と半分＞半分＞半分と絞り込んでいく方法

コード

#バイナリサーチ
require 'pp'
before = Time.now
t = Time.now
srand(t.sec ^ t.usec ^ Process.pid)

#探索する要素数
Num = 10

def binarySearch(target,a)
	left = 0
	right = a.size - 1

	while(left < right)
		mid = (left + right) / 2

		if a[mid] == target
			return mid
		end

		if(a[mid] < target)
			left = mid + 1
		else
			right = mid
		end
	end

	if a[left] == target
		return left
	end

	return nil
end

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

#探す数値
target = rand(Num)

#配列をソート
a.sort!

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

#p binarySearch(target,a);

#処理時間
p Time.now - before

ふつうのRuby

RAAにSatoru Takabayashiさんによるbserachというのが登録されています。

まとめ

二分探索という言葉はわかりやすけど、バイナリってのがわかりにくい。バイナリって二分という意味もあるんだろうか？調べてみたけど２進って意味はあるみたいだけど、ちょっと違う気もする･･･けど間違ってるのはどうせ僕のほうなので誰か賢い人に聞いてみようと思う。

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

Posted in Ruby, アルゴリズムとデータ構造 | 1 Comment »

リニアサーチ

12月 5th, 2007 admin

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

番兵（番人）

普通に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でアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。

Posted in Ruby, アルゴリズムとデータ構造 | 1 Comment »

単純挿入ソート（2分挿入ソート）

11月 27th, 2007 admin

今日は単純挿入ソートです。
前から順にひとつずつ値をチェックしていき、自分より前方に自分より大きな値があればそこに値を挿入するというもの。
直感的にも明らかに遅い感じだし、実際に計算量オーダはO（N^2）なのですが、ほとんど整列が終わっているデータに対しては大変効率がよいということです。

#単純挿入ソート
require 'pp'
before = Time.now
t = Time.now
srand(t.sec ^ t.usec ^ Process.pid)

#ソートする要素数
Num = 10000

def simpleSort(sort)
	(Num-1).times{|sorted|
		#ソート済みでない値を取り出す
		insert = sort[sorted+1];
		#挿入する場所を見つける
		for i in 0..sorted
			if sort[i] > insert then
				break
			end
		end

		if i == sorted then
			next
		end

		#ソート済み領域直後の値を挿入する
		while i <= (sorted + 1)
			temp = sort[i]
			sort[i] = insert
			insert = temp
			i+=1
		end
		}

	return sort
end

#ランダムな値の入った配列を作成
sort = Array.new
Num.times{
	sort.push rand(Num)
}

#ソート前の出力
pp sort

sort = simpleSort(sort);

#ソート後の出力
pp sort

#処理時間
p Time.now - before

Num=10000で実行してみると僕の環境では70秒程度かかる。バブルソートよりは早いということですかね。

2分挿入ソート

単純挿入ソートの改良版で2分挿入ソートというのがあるそうです。上記の「挿入する場所を見つける」という部分をバイナリサーチというのを使って改良したものだということです。バイナリサーチについては第2章で取り扱うということなのでとりあえず省略します。

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

Posted in Ruby, アルゴリズムとデータ構造 | 1 Comment »

« Previous Entries
Next Entries »