浮動小数点数と数値計算

7月 15th, 2008 admin

あいかわらず「アルゴリズムとデータ構造シリーズ」です。今回は第8章「浮動小数点数と数値計算」です。

浮動小数点数

float型やdouble型の数値はコンピュータの内部では
符号と指数（ｎ）と基数（a）で表現されている。
たとえば１２．８なら
基数＝０．８
指数＝4
で
０．８＊２＾４
という具合です。なのでその表現の都合で、あまりにも大きかったり小さかったりする数字は正確には表せないということがあるというお話

数値計算

簡単な数値計算の例として5次方程式を解くというもののコードを書きました。
バイナリサーチを用いて、答えのある範囲をだんだんと絞っていくものです。

PLAIN TEXT

RUBY:

#func
def func(x)
x = (x * x * x * x * x) - (10.0 * x * x * x * x) + (25.0 * x * x * x) + ( 40.0 * x * x) + ( 200.0 * x) - 500.0
return x
end
def binary_search
epsilon = 0.00001
left = 1.0
right = 3.0
while((right-left).abs> epsilon && func(left).abs> epsilon)
mid = (left+right)/2.0
if(func(left)*func(mid)>=0.0)
left=mid
else
right=mid
end
end
return left
end
d = binary_search
p d
printf("answer is %1f. and func(x) is %1f \n",d,func(d))

まとめ

コンピューターなのに不正確な答えを出すと言うのがなんだか面白いですね。

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

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

マップとハッシュ（ハッシュマップ）

7月 13th, 2008 admin

今回は「アルゴリズムとデータ構造シリーズ」です。前回に続いて第7章「マップとハッシュ」のハッシュマップの実装について。

ハッシュ値が重複した場合の対策

ハッシュ値が重複した場合には「k^2番目に再ハッシュする」という方法で対応した。
たとえばハッシュ値が2だった場合には
・３（２＋１＊１）
・６（２＋２＊２）
・１１（２＋３＊３）
と試していく方法だ。

コード

検索と削除の部分は少しずるをしました。

PLAIN TEXT

RUBY:

#Hash Map
$KCODE = "SJIS"
class WordSet
attr_accessor :english, :japanese
def initialize(english = nil, japanese = nil)
@english = english
@japanese = japanese
end
end
class HashMap
def initialize(size)
@hash_table_size = size
@hash_table = Array.new
end
def make_hash(str)
weight = 0
hash = 0
str.each_byte{|s|
weight = 0 if weight> 7
hash += s * (256 ** weight)
weight+=1
}
hash % @hash_table_size
end
def add_data(ws)
hash_val = self.make_hash(ws.english)
unless @hash_table[hash_val].nil?
hash_val = self.rehash(hash_val)
if(hash_val == -1)
printf("%sをマップに挿入しようとしましたが、空き位置がありませんでした",ws.english)
return
end
end
@hash_table[hash_val] = ws
end
def rehash(first_hash_val)
#k^2に再ハッシュする
(1...(@hash_table_size/2)).each do |k|
hash_val = (first_hash_val+k*k) % @hash_table_size
return hash_val if @hash_table[hash_val].nil?
end
return -1
end
def find(str)
hash_val = self.make_hash(str)
return @hash_table[hash_val]
end
def delete(str)
hash_val = self.make_hash(str)
@hash_table[hash_val] = nil
return true
end
def print_all_data
@hash_table.each do |val|
printf("%s\t\t%s\n",val.english,val.japanese) unless val.nil?
end
end
end
init_data = [
WordSet.new("lisp","リスプ"),
WordSet.new("C","シー"),
WordSet.new("ruby","ルビー"),
WordSet.new("perl","パール"),
WordSet.new("python","パイソン"),
WordSet.new("PHP","ピーエイチピー"),
WordSet.new("JavaScript","ジャバスクリプト")
]
hash_map = HashMap.new(503)
init_data.each do |ws|
hash_map.add_data(ws)
end
i = nil
loop do
print "コマンドを入力して下さい\n1:表\�� 2:検索 3:削除\n"
i = gets.chomp.to_i
case i
when 1
hash_map.print_all_data
when 2
print "検索する文字列を入力してください："
j = gets.chomp
if ws = hash_map.find(j)
printf("%sは日本語で「%s」です。 \n\n",ws.english,ws.japanese)
else
print("見つかりませんでした。\n\n")
end
when 3
print "削除する文字列を入力してください："
j = gets.chomp
if hash_map.delete(j)
printf("削除しました。 \n\n")
else
print("見つかりませんでした。\n\n")
end
end
end

まとめ

ハッシュというものがどういうものか（そもそもなんでハッシュと呼ばれているのか）わかって非常にすっきりできた。

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

Posted in Ruby, アルゴリズムとデータ構造 | コメントは受け付けていません。

マップとハッシュ（ハッシュ値生成）

7月 8th, 2008 admin

今回も「アルゴリズムとデータ構造シリーズ」です。本日は第7章「マップとハッシュ」について。

マップとハッシュ

この章で学びたいのは「文字列をキーにして値を取り出せるデータ構造」である。それを実現するにはまずツリーマップという方法があり、それを改良したものがハッシュマップと呼ばれる一般的なハッシュというやつですよ。というのが今回のお勉強である。

ツリーマップ

まず前章でやったツリー構造を使うのがツリーマップである。キーとなる文字列をstrcmp()関数などで数値化して2分木で保持するというものだ。ツリーのどこにデータがあるかによって計算時間にばらつきがでるので安定していないのが欠点である。

ハッシュマップ

ツリーマップの欠点を克服したのがハッシュマップになる。メモリの消費量は多くなるが、なんと計算量オーダはO(1)と最速。すごい！
これはどのようにやるかと言うと
(1)データの検索キーを数値化する（ハッシュ値）
(2)ハッシュ値を記憶する大きな配列を用意し（ハッシュ表という。array[100]とか）、ハッシュ値に対応する位置にデータを格納する（ハッシュ値が78ならarray[78]に）
(3)データを検索するときには、検索キーを数値化し配列の要素を参照する
という感じだ。僕はなんだか本の索引を思い出しました。検索キーからページ番号がわかるので、そのページを開くと情報が得られるという一旦数字に直すところが面白い。

んで、この段階で以下のような疑問が出てきた
・ハッシュ値は重複しないのか
・ハッシュのサイズに合わせていたらハッシュ表がいくら大きくても足りないのではないか
だけど当然こういうのはクリアされているみたいだ。

コード

今回はまずハッシュ値の生成コードを書くところまで行った。
ハッシュ値はハッシュ表のサイズを抑えるために、ある程度小さい数に抑える必要があるため必ず重複してしまうが、重複に対応できるようにするので多少は問題ない。

PLAIN TEXT

RUBY:

#make hash
def make_hash(str, hashmax)
weight = 0
hash = 0
str.each_byte{|s|
weight = 0 if weight> 7
hash += s * (256 ** weight)
weight+=1
}
hash % hashmax
end

まとめ

今回はハッシュマップの実装の前準備だけを行った。不思議なのはハッシュ表のサイズを素数にすると（上記のコードのhashmax）ハッシュ値の重複が、それが素数でない場合より少なくなるというTipsだ。んーだれか教えて。

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

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

ツリー構造（２分木）

7月 6th, 2008 admin

今回も「アルゴリズムとデータ構造シリーズ」です。本日は「ツリー構造」について。

ツリー構造とは

ツリー構造とは樹形図のようになったデータ構造のことです。Windowsのファイル構造はツリー構造ですね。
難しそうに感じますが、以前やったリスト構造では、データが次のノードへのポインタを一つしかもっていなかったものを複数にするというだけで実現できます。

2分木

今回はツリー構造の中でも２分木と呼ばれるものを実装しました。2分木とはツリー構造の中でも各ノードが最大2個の子ノードしかもたない構造のことです。さらに今回は2分木の中でも、子ノードの並べ方に順序をつけ検索性をアップしたタイプ（左が小さい、右が大きい）にし、挿入・検索・削除ができるようにしました。

まとめ

挿入や、検索よりも削除が面倒でした。
ツリー構造にはいろいろな応用パターンがあっておくが深そうです。本書では常に検索効率の良いAVL木やデータベースエンジンでよく使用されているB木（B+木）の解説もあり非常に勉強になりました。

コード

今回はコードが長いので最後にしました

PLAIN TEXT

RUBY:

#Binary Tree
$KCODE = "SJIS"
class Node
attr_accessor :left,:right,:value
def initialize(value)
@value = value
@left = nil
@right = nil
end
end
class BinaryTree
attr_accessor :tree_root
def initialize
@tree_root = nil
end
def create_new_node(value)
Node.new(value)
end
def insert_tree(value, node)
if node.nil?
@tree_root = self.create_new_node(value)
return
end
if node.value> value
unless node.left.nil?
self.insert_tree(value,node.left)
else
node.left = self.create_new_node(value)
end
else
unless node.right.nil?
self.insert_tree(value,node.right)
else
node.right = self.create_new_node(value)
end
end
end
def find(node, value)
if node.value> value
return nil if node.left.nil?
return self.find(node.left, value)
end
if node.value <value
return nil if node.right.nil?
return self.find(node.right, value)
end
node
end
def delete(value)
direction = 0
parent_node = nil
node = @tree_root
while(node != nil && node.value != value) do
if(node.value> value)
parent_node = node
node = node.left
direction = -1
else
parent_node = node
node = node.right
direction = 1
end
end
return 0 if node.nil?
if(node.left.nil? || node.right.nil?)
#左右どちらかがnilだった場合
if(node.left.nil?)
parent_node.left = node.right if direction == -1
parent_node.right = node.right if direction == 1
@tree_root = node.right if direction == 0
else
parent_node.left = node.left if direction == -1
parent_node.right = node.left if direction == 1
@tree_root = node.left if direction == 0
end
else
#両者共nilでなかった場合
left_biggest = node.left
parent_node = node
direction = -1
while(left_biggest.right != nil) do
parent_node = left_biggest
left_biggest = left_biggest.right
direction = 1
end
node.value = left_biggest.value
if(direction == -1)
parent_node.left = left_biggest.left
else
parent_node.right = left_biggest.left
end
end
true
end
def print_tree(depth, node)
return if node.nil?
self.print_tree(depth+1, node.left)
(0...depth).each{|i|
printf(" ")
}
printf("%d\n",node.value)
self.print_tree(depth+1,node.right)
end
end
tree = BinaryTree.new
10.times{|i|
tree.insert_tree(rand(99),tree.tree_root)
}
tree.print_tree(0,tree.tree_root)
i = nil
while i != 0 do
print "現在のツリー\n"
tree.print_tree(0,tree.tree_root)
print "コマンドを入力して下さい\n0:終了 1:追加 2:検索 3:削除\n"
i = gets.chomp.to_i
case i
when 1
print "1~100の範囲で、追加する数字を入力してください："
j = gets.chomp.to_i
tree.insert_tree(j ,tree.tree_root) if (j>= 1 && j <= 100)
when 2
print "検索する数字を入力してください："
j = gets.chomp.to_i
if tree.find(tree.tree_root,j)
printf("%dは見つかりました。 \n",j)
else
print("見つかりませんでした。\n")
end
when 3
print "削除する数字を入力してください："
j = gets.chomp.to_i
if tree.delete(j)
printf("%dは削除しました。 \n",j)
else
print("見つかりませんでした。\n")
end
end
end

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

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

再帰呼び出し

7月 4th, 2008 admin

今日も「アルゴリズムとデータ構造シリーズ」です。本日は「再帰呼び出し」について。

再帰呼び出しとは

関数が自分自身を呼び出すのが「再帰呼び出し」。再帰が何かといわれれば、それはエッシャーの「描く手」であり落語の「頭山」でありGNUの名前の由来であったり、そしてなんといっても亜空の瘴気ヴァニラ・アイス様と答えるのが妥当でしょうか

今回は再帰呼び出しを使って2つ以上の数の最大公約数を求めるスクリプトを書きました。a,b,cと3つの数字があったら、b,cの最大公約数をもとめて、aと（b,cの最大公約数）の最大公約数を求めるというアルゴリズムです。

コード

PLAIN TEXT

RUBY:

#recursive
class Gcd
def initialize
@list = Array.new
end
def execute
multi_gcd(@list.size - 1)
end
def set(i)
@list.push(i)
end
#二つの数の最大公約数を求める
def gcd( a, b)
a.downto(1) do |num|
return num if(a%num == 0 && b%num==0)
end
nil
end
def multi_gcd(n)
#数が2以下ならgcdを呼ぶだけ
return self.gcd(@list[0],@list[1]) if n == 1
#数が3以上ならmulti_gcdよ呼びなおす
return self.gcd(@list[n], self.multi_gcd(n-1))
end
end
mg = Gcd.new
mg.set(9)
mg.set(6)
mg.set(27)
p mg.execute

まとめ

再帰をイメージするときいつも、子どもの頃に遊んだ、見た目はアイスの棒みたいな10cm幅ぐらいのロール紙の玩具を思い出します。振ると伸びて戻ってくるあれです。

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

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

浮動小数点数と数値計算