B18  データ探索方法



努力目標

  理解する




技術士試験の問題からは必要最小限の引用にとどめる。(問題)が記されている部分はその引用である。

問題および解答は日本技術士会のホームページより必要に応じて入手してください。

  技術士第一次試験の問題   



問題番号が赤字のものは、ボーナス問題

H17年 1-2-4




H17年 1-2-4

正答: ① 

(解答)

ハッシュ探索 探索時間を一定にできる。データの大小比較には適さない。
線形探索   探索時間はデータ量に比例する。探索のための前処理は不要である。
二分探索   探索時間はデータ量の対数に比例する。更新処理の多い用途には適さない。



((参考)

ハッシュ検索(Wikipedia)

ハッシュ法とは、データ検索アルゴリズムの一種で、もっともポピュラーなものの一つ。検索対象のデータを一定の規則にしたがってハッシュ値と呼ばれる整数に変換し、ハッシュ値を比較して検索を行う方式。

文字列検索のように個々のデータが大きい場合、データ全体を比較しながら検索するよりも比較にかかるコストが節約でき、高速に検索できる。ただし、検索するデータの大きさが小さければ、ハッシュ値に変換する手間が増えるためにかえって効率が悪くなることもある。

線形探索(Wikipedia)

線形探索
は、検索アルゴリズムの一つ。 リスト配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。

二分検索(Wikipedia)

ソート済みのリスト配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。

n個のデータの中央の値を見ることで、1回の操作でn/2個程度(奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個)の要素を無視することができる。





                問題一覧表へ戻る