隠れたアルゴリズム

いま、結構ややこしいjavascriptのプログラムを作っている。

html上に複数の要素が表示されていて、非同期でサーバからデータをとってきて、サーバのデータとHTML上のデータを比較して、なければ消す、あれば作る、変更があれば変える、みたいなことをする。

簡単に言うと配列が2つあって、それぞれの配列を比べなければならない。

 

もし、片方の配列Aをループし、そのそれぞれの要素についてもう片方の配列Bをループして、見つかったら処理をする、という処理を普通に書いたとする。
たぶん、配列数が10個ぐらいなら、それほど大きな問題にはならないだろう。しかし、本当の修羅場ではずらっと配列数が大きくなるようなプログラムだとするとどうだろう。
双方の配列の要素がそれぞれ100個あると仮定する。A1つの要素がBに対応があるかどうかというのは発見できるのは平均で半分の試行で済むとするならば50回、それを100回ループすることになるので、大方5000回の比較が必要になることになる。

しかし、もしB側の配列がソートされていたとしたら?Bの中央値とAの要素を比べ、たとえば中央値より小さいと分かれば、そのまた中央値と比べるというやりかたをすれば、1要素7回程度の試行で見つけ出すことができることになる。したがって、このやり方ならAの100個全部をループしても700回ぐらいの比較で見つけ出せるはずである。

 

そうするとソートとか、検索のプログラムをかなり真剣に書かなければならないわけだが、しかし、普通javascriptあるいはjQueryなどでソートや検索のプログラムぐらいありそうなものではありませんか。自分はそれほどjQueryなんかが詳しくないから、一応調べてみる。

で、sortの関数はjavascript標準であるんです。このsortの関数が、バブルソートを使っているということはいくらなんでもないだろう。ここは信じましょう。

しかし、検索のプログラムは?

自分が知らないだけなのかもしれないが、最初からソートされていることを前提として検索する関数というのは、やっぱりなさそうに見えます。

あらゆる検索のプログラムが、要素がソートされていないことを前提としているなら、基本的には全部をループすると思うのです。仮に関数内でソートを行うとすれば、データが大きくなればそれなりに速くはなるだろうが、それでも関数を呼ぶたびに同じソート作業を行っているとするならプログラム的に良いはずがない。つまり、上の例でいう5000回の比較をするプログラムになってしまうはず。

 

だから、もしなんとなく$.grepみたいな関数をループするプログラムを書くとたぶん処理時間はかかるんだろうと思う。でも、ほとんどの人は、そこは見てないと思うんです。

自分の感覚では、たぶんほとんどの場合コード量が多いほうが、処理速度は速いと思う。それは無駄なコードがいいというんじゃなくて、それなりに考えて書いたコードというのは、結構長くなってしまうということ。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です