線形探索(2)
2006.03.16 22:44 探索
単純な線形探索よりも効率の良い線形探索のアルゴリズムを考えます。繰り返しになりますが、単純な線形探索のプログラムでは、
の2つをチェックしなければなりませんでした。これから考えるアルゴリズムでは、データに「番兵」と呼ばれる特別な値を設置することによって、比較演算の回数を半減させます。下図は整数のデータが格納された配列から与えられた値を探索している様子を示しています。

この例でも、要素数が12個の配列の中から8を探していて、配列の先頭から順番に各要素が8であるかどうかをチェックしています。重要なポイントは、データの末尾に番兵として目的の値である8を追加していることです。番兵を設置することによってデータの中に目的の値が存在することが保障されるので、探索している範囲がデータ数を超えてしまわないかのチェックを行う必要がなくなります。目的のデータが見つかったときの index がデータのサイズを超えていた場合(index が size と等しい場合)、それは番兵を示すので、データに目的の値が存在しなかったことを示します。番兵を用いた線形探索のプログラムの例を以下に示します。
09 行目でデータの末尾に番兵である key を設置します。その結果、メインループでの比較処理はdata[ ++index ] != key の1つしかありません。番兵がいるのでメインループの while( data[ ++index ] != key ); は必ず終了することが保障されます。つまり、データの範囲を超えてチェックしていまうという危険な処理を"番兵"が阻止します。メインループが終了した時の index の値が、目的の値を指します。データが見つからなかった場合は、index が番兵にたどりついてしまった場合、すなわち index が size に達してしまった場合です。
- index < size: indexがデータの末尾を越えていないかのチェック
- data[ index ] == key : indexが指すデータの中身が目的の値でないかのチェック
の2つをチェックしなければなりませんでした。これから考えるアルゴリズムでは、データに「番兵」と呼ばれる特別な値を設置することによって、比較演算の回数を半減させます。下図は整数のデータが格納された配列から与えられた値を探索している様子を示しています。

この例でも、要素数が12個の配列の中から8を探していて、配列の先頭から順番に各要素が8であるかどうかをチェックしています。重要なポイントは、データの末尾に番兵として目的の値である8を追加していることです。番兵を設置することによってデータの中に目的の値が存在することが保障されるので、探索している範囲がデータ数を超えてしまわないかのチェックを行う必要がなくなります。目的のデータが見つかったときの index がデータのサイズを超えていた場合(index が size と等しい場合)、それは番兵を示すので、データに目的の値が存在しなかったことを示します。番兵を用いた線形探索のプログラムの例を以下に示します。
09 行目でデータの末尾に番兵である key を設置します。その結果、メインループでの比較処理はdata[ ++index ] != key の1つしかありません。番兵がいるのでメインループの while( data[ ++index ] != key ); は必ず終了することが保障されます。つまり、データの範囲を超えてチェックしていまうという危険な処理を"番兵"が阻止します。メインループが終了した時の index の値が、目的の値を指します。データが見つからなかった場合は、index が番兵にたどりついてしまった場合、すなわち index が size に達してしまった場合です。
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |