アルゴリズム
プログラマ失格
二分探索

そのプログラム、遅くないですか?

二分探索ってご存知でしょうか。普段使っていますか?

カーナビなどで文字を入力するときに、ひらがなの五十音表のボタンで
文字を入力することがあります。

わらやまはなたさかあ
をり みひにちしきい
んるゆむふぬつすくう
 れ めへねてせけえ
 ろよもほのとそこお

この五十音表のボタンから、「ね」を探す場合、どのように探すでしょうか。
日本人なら「ね」は「な」行の4番目ということを知っています。
まず1行目から、あかさたな、と「な」行を探し、それから下に、なにぬね
と探すことが多いのではないでしょうか。

一方、あいうえおかきく・・・という順に探していくことは少ないですね。
あいうえおかきく・・・と探すと「ね」までに23文字探すことになります。
いっぽう、「な」行を探し、そこから、なにぬね、と縦に探せば、
8文字で探し出せます。

このように何かの作業を順序だてて手順化する手法を定型化したものを
アルゴリズムと言います。

コンピュータープログラムでは大量のデータからあるデータを探し出すのに
インデックスという機構を通し、二分探索やそれに準ずるアルゴリズムを
利用するのが定石です。

二分探索は大量のデータをまず半分にわけその前後どちらに目的のデータがあるかを
判別して、その半分をさらに半分に区分けして、と探す手法です。

1億件のデータから特定のデータを探し出すとき、上で書いたように、
あいうえおかきく・・、と探すと、最大1億ステップが必要になりますが、
二分探索を使うと、log2(1億)つまりたった27ステップで目的のデータに
辿りつくことができます。
1ステップ1秒だったら大変なことですね。1億ステップは3年以上かかる計算です。
二分探索なら27秒です。

残念ながら一部のプログラマはこの理屈を使いこなせない方が多いようです。
プログラマを何年もやっている人でもこのことに無頓着な方がよく見られます。
悲しいことです。

とっつきは難しいように感じられてもそれを学ぶことで業務効率は
3年かかるか27秒しかかからないかの差になることもあるということを
理解して仕事をしましょう。

コンピューターが爆速でデータを探し出せるのは二分探索を応用したアルゴリズムで
検索を実行するからです。
昨今の一般のプログラム言語・フレームワークでは検索アルゴリズムの基本は
いちいちプログラムしなくても既製のものがあふれています。すでにあるものを
使いこなせばよいだけです。

昨今のコンピューターは性能が高いため、五十音程度では、あいうえおかきく・・と
探しても瞬く間です。二分探索など必要なく思われます。しかし、大量のステップを
必要とするプログラムは、電気代もかかります。ちりもつもれば山となります。
「とりあえず動けばよい」ではなく「きちんと無駄なく動く」ことを目指しましょう。

二分探索以外にも少し勉強するだけで業務速度が爆速になることがあります。
そのような事例は日常の仕事にもあふれています。これまでやってきた仕事の方法が
劇的に効率化できないかいまいちど振り返ってみてはいかがでしょうか。