【調べ物の作業効率】ITエンジニアなら知っている、インデックス検索の時間短縮ワザ


プログラマーなら知っている
時間短縮技があります。

今回はそれを紹介します。

どういうケースか?

図書館で、図書カードを探すときや、
昔の紙の辞書で探すとき、
1~10000の中から探すときなどです。

例えば、
ハイ&ロー  ゲームのように、
数の当てっこするときに、
当てるほうが数字を言い、
問題を出した側は、外れていたら
数字が大きいか小さいかを伝えます。

そういう状況で、大抵のケースで一番回数を小さくして探す方法があるんです。

やり方と考え方

それは常に、真ん中の値を取って、調べていく方法です。
感で一発であてられたらば負けますが、
平均的に必ず当てるために、
最小になります。

1~100の中の時は
まず 50 を言い、
大きければ 75 を言います。
更に大きければ、 87などと言っていきます。

こうすることで、効率よく正解に近づくことになります。

先程の例のように、図書カードを全部見なければいけないけど
順番になっている時は、
おおよそ半分あたりをチェックしつつ進めると効率的です。
indexsearch_ratio-min

10%ずつ前から進めていくやり方よりは
効率的なのはなんとなくわかると思います。

補足説明や応用例

これは簡単な例なので、1回の調査あたり数秒だけで済みますが
1回の調査あたり数時間とか、数日かかるときなんか
こういうことを意識するだけで仕事のスピードが
がぜん変わってきます。

単なる数字以外でも
調整のやり方も変わってきますよね。

例えば、スケジュールの調整にしても
ピンポイントの日程と、可能性を半分にする日程を入れて
メールのやり取りの回数を極力減らすう方法とかです。

また、慣れていて勘が働くのであれば
毎回きっちり1/2にしなくても、
微調整(可能性が高い方を選択)して進めても
もちろん良いです。

数理的補足(ちょっとだけ)

細かく言えば、オーダの考え方で
母数を n と置いたときに
nの定数倍なのか
nの2乗倍なのか
logn倍時間がかかるのかを 考えます。

今回のケースでは、真ん中を取ることにより
n → 1/2n → 1/4n と候補が絞られるため
2^k = nですので
kを求める式から、 log n オーダになります。
(定数倍は、オーダレベルで見ると小さく
ボリューム感を表現する目的であるため、省略して書きます)

アルゴリズム的には、
もちろん 定数倍のほうが圧倒的に短いので、
そちらのアルゴリズムが優秀と言われますし、
n^2オーダから  logn オーダにするだけでも
論文になります。

全体の数が100ぐらいではオーダの違いはそれほど変わらないけれども
1万、1億と 進むに連れ、計算量が天文的な違いになります。
(実際には人間の寿命では困難なレベルから、
すぐ回答が出るレベルになるくらい違う)

コメントを残す

メールアドレスが公開されることはありません。