今回の学習項目です。
今回と次回で｢探索」(教科書では「検索」とも書いています)の問題を取り上げます。 探索とは、与えられたデータの中から指定された条件を満たす問題をいいます。 もちろんそのような条件を満たすものがない場合もあります。 そのときには「ない」と答えなければなりません。 ここでは数を指定して、所定の配列（やファイルの中）から探索する問題を取り上げます。
ここで、もしも配列の中に数がランダムに配置されていたとすればどうでしょう？ これは例えば、ランダムにおかれたカードの中から特定のカードを探すような場合に相当します。その場合ははっきりいって、良い方法はありません。一つ一つカードを調べるしかありません。
しかし、配列(やファイル)の要素が、ある決まった方法で並んでいたとすると、 とてもよい探索方法があります。 今回は配列の中の数がソートされている(小さい方の数から順に並んでいる） 場合の効率的な探索方法、二分探索を学びます。
教科書35ページから37ページには2進木を用いた二分探索が述べられています。 しかし、今回は教科書とは異なる方法で解説します。 よく考えれば両者は同じことを述べているのですが、 ここで述べる方法の方が実用的でわかりやすい方法(のはず)です。例として、
3, 5, 7, 10, 15, 16, 18, 19, 20, 23, 24, 33, 35, 40, 41, 42, 46
という数の並びが与えられたとし、そこで特定の数を探索することを考えましょう。
ここでは10と38をそれぞれ探索するものとしましょう。
みてわかるように、数が小さいものから大きい数へ順に並んで(ソートされて)います。
このときは、先頭の数から順にみるよりも適当な場所の数をまず調べ、
そしてその数よりも探索対象の数が小さければ小さい数のほうを(この例では左の方を)探し、大きければ大きな数のほうを(この例では右のほうを)探すでしょう。
基本的にはこれでよいのですが、具体的には「どの場所」の数をまず見るか、 ということと、その次はどうするか、という二つの問題があります。
そこで二分探索は次の方法を与えています:
最初に10を探索してみます。 先の配列は 17 個の要素がありましたから、ちょうど真ん中の9個目の要素を取り出してみます。 その数は(先頭の要素を0番目とすると)8番目の要素 20です。 ここで、比較対象の場所「8」(番目)を求めるには、先頭の要素の番号0(探索対象の左端の要素の番号)と探索対象の最後(右端)の要素の番号16を足して2で割って求めました。
探索対象の 10 は20よりも小さいので、今度は配列で小さい(左側)ほう、つまり要素の番号0から(8-1=)7番目の要素までを同じやりかたで探索します。 ここで同じやり方というのは、探索対象の左端の要素の番号(ここでは0)と探索対象の右端の要素の番号(ここでは7)の真ん中、つまり(0+7)/2 = 3 によって、比較対象の要素を取り出す場所「3」(番目)を求め、配列の3番目の要素の10と比べることで、さらに探索範囲を狭めていくことをいいます。 ここで、10は探索対象そのものですから、ここでは探索対象が「見つかった」として答えます。
次に38を探索してみます。 さっきと同様に、真ん中の要素（8番目の要素)である20と比較します。 探索対象の38の方が大きいので、今度は配列の大きい方、つまり(8+1=)9番目の要素から(配列の最後の番号の)16番目の要素までで探索します。
今度はこの配列の真ん中の要素の番号が((9+16)/2 =)12となりますので、12番目の要素、つまり35と比較します。 しかし、38の方が35よりも大きいので、さらに大きい(右側の)ほう、つまり(12+1=)13番目の要素から(配列の最後の要素の)16番目の要素までで探索します。
今度はこの配列の真ん中の要素の番号が((13+16)/2=) 14なので、14番目の要素の41と比較します。探索対象の38はこの41よりも小さいので、今度の探索の範囲は13番目から(14-1=)13番目の要素までが探索範囲となります。つまり13番目の要素が違えば「見つからなかった」ことになります。 ここで13番目の要素は35であり、これは38ではありませんから、探索対象は「見つからなかった」と答えることになります。
3, 5, 7, 10, 15, 16, 18, 19, 20, 23, 24, 33, 35, 40, 41, 42, 46
において1を探索する様子を説明しなさい。
2分探索を用いてn個の要素の配列において特定の数を探索する場合、 今見たように配列から要素を取り出して探索対象の数と比較する。 この比較回数が最も少ない場合は何回だろうか。またもっとも大きい場合は何回だろうか。
二分探索するRubyの関数bSearch(ar, x)を作りなさい。ここで第1引数(ar)は数を要素とする配列、xは探索対象の数を取るものとする。返す値は、配列の中にxがあればtrue、なければfalseを返すものとする。
要素数がたくさんある配列に対して探索を行い正確に答えが返されることを確かめなさい。
この二分探索ではn個のデータを予めソートして配列に入れておけば、
探索のための計算量は
まずは数が入ったファイルを開いて眺めてください。 そこで5543という数があるか調べてみてください(注意: 「検索」コマンドを使わないこと)。
ありましたか？どうやって調べましたか？
たぶん、ファイルを上から順に見ていったのではないでしょうか。 ここで数が小さい方から大きい方へとソートされていることに気が付いたでしょう。 そこでファイルの最後まで見ないですむのでかなり早くできたことと思います。さらに50個くらいを一ページに表示させられるので探索がやりやすかったこととおもいます。 ところが人間ではなくコンピュータが探索する場合は、そうはいきません。コンピュータが探索する場合、一つ一つデータを取り出してみないとできないのです。また人間の場合であっても、この何百倍、何千倍ものデータが入ったファイルの中から特定の数を探すとしたら、とても大変な作業です。
そこで二分探索のような賢い探索が使えないだろうかと思うことでしょう。確かにこのようなファイルでも二分探索が使えます。ただ、それには条件がいくつか必要です。
まずnumbers.txtファイルを配列のように使い、二分探索により目的の数を探索するプログラムを示します。
LineSize = 7 # 1行の文字サイズ
FirstLine = 0 # ファイルの先頭の行番号
LastLine = 999 # ファイルには1000個のデータが入っている
# 先頭を0番目とすると最後は999番目のデータ
def bSearchInFile(fo, x, first, last) # ファイルfoに対して二分探索
return false if (first > last) # 見つからなかった
mid = (first+last)/2 # 真ん中
fo.seek(mid*LineSize) # ファイルからデータを読み込む位置の移動
y = fo.read(LineSize).to_i # データを読んで整数にする
if (x == y) # 一致
return true
elsif (x > y) # 探索対象の方が大きい：大きい方を探索
return bSearchInFile(fo,x,mid+1,last)
else # 探索対象の方が小さい：小さい方を探索
return bSearchInFile(fo,x,first, mid-1)
end # if
end # def
fo = open("numbers.txt","r+") # numbers.txtをランダムアクセスファイルとして開く
target = 5543
print target,"をファイルから探索します:"
if bSearchInFile(fo,target,FirstLine,LastLine)
print "ありました\n"
else
print "ありませんでした\n"
end # if
このプログラムについて解説します。
１行目で「１行の文字列の長さ」が7であることを記憶するために、定数宣言しています。Rubyでは大文字から始まる名前は「定数」として扱われます。 定数とは、変数のように値を持てますが、一旦与えられた値を変更することはできません(この点が変数との違いです)。また、ここでは関数の外側で定数に値が代入されていますが、関数の外側でも関数の中からも定数の値を参照することが可能です。
２行目と3行目も定数宣言です。 ここでは1000個のデータを対象としています。もっともファイルの先頭の行を０番目としていますので、 最後の行は999番目になります。 そこで、最初の行番号をFirstLineという定数で、最後の行番号をLastLineという定数で記憶しています。
5行目からはファイルを配列として見立てた二分探索のための関数を定義しています。 引数のfoは開いたファイルへのポインタ、xは探索対象の数が入ります。 3番目のfirstは探索対象の最初の行の番号、次のlastは探索対象の最後の行番号が与えられます。
ファイルを配列として扱うためには、特定の行のデータを読み込む必要があります。 そこでmid番目のデータを読み込むために、8行目の fo.seek(mid*LineSize)と 9行目の y=fo.read(LineSize).to_iが役立ちます。 fo.seek(z)はファイル(fo)の先頭から数えてzバイト目からデータを読み込む準備をさせます。 また、fo.read(l)はそこからlバイトのデータを「文字列」として読み込みます。 それに対し to_i メソッドにより、そのデータを数に変換する、というわけです。 これ以外は、配列の場合と同じように2分探索が行われていることがわかるでしょう。
このプログラムを改変して、numbers.txt で2分探索により5000がこのファイル中にあるかどうかを判定してください。またこのとき、どんなデータが読み込まれ、比較されるかを表示してください。さらに、ファイルから読み込まれるデータの個数を答えなさい。