ハッシュテーブル

真魚の色分けで、準予約語、準々予約語を追加して、PHPに対する仕事を増やしたので、
その分遅くなるであろう処理をどうにか速くしたい。
そしてその方法は定番として既にあるが、現時点で遅くないので、やるのを面倒くさがっている。
しかし、真魚はBM法も導入しているわけで、趣味で高速化するのも悪くはない。



何が遅いのかというと、テキスト中に出てきた文字列がPHPキーワードかどうか調べるのが遅い。
例えばahoと書かれていたら、67個のPHP予約語のどれかに該当するか一つ一つ調べ、
次は452個のPHP関数に該当するか調べ、最後に236個の定数と該当するか調べる。
ahoはまず、abstractと比較されるが、コンパイラがどのように比較させるかはブラックボックス。
たぶん文字数が違う時点で該当しないと判断するのが一番スマートだが、そうはしてないだろう。
おそらく、最初の1文字を比べて、aがあってるから2文字目も比べて、hとbだから×だろうな。
次はandと比べるが、また1文字目あってる、2文字目違ってる、って比較するだろう。
それを、数百回やらないと、ahoが色分けの対象かどうかわからないのが遅い。
いや、体感は遅くないけど、無駄なことをしてるから理論上は絶対遅い。
全部の単語と一文字ずつ比較するより、もっと効率的にやろうという方法を導入したい。
その方法として、考えているのがハッシュテーブルだ。

普通に比較する方法が遅い理由は二つあり、文字数の問題と単語数の問題に分かれる。
比較する1単語につき、最大で文字数回の思考が行われると言うことを回避するのが、
「ハッシュテーブル」の「ハッシュ」の部分が担当する問題だ。
ハッシュというのはP2Pをやってる人にはおなじみの、ファイルを区別するIDに当たる。
今回は、比較すべきキーワードを、数字だけで構成するハッシュに変換する。
すなわち、全てのキーワードを数字に変えちゃえば、数字同士1回の比較で終われるのだ。
次に「テーブル」については、真魚でも高速化のために良くやってる方法で、
いったん数字に変換されてしまえば、テーブルに持つ事で比較ナシに出来る。
使うか使わないかもわからないような余分なメモリーを確保しなければいけないが、
高速化のために余分なメモリーを確保するというのは真魚の基本方針でもある。

そんな感じで、ハッシュテーブルを導入すれば高速化できるのは間違いない。
しかし問題は、そのハッシュテーブルのためにどれほどのメモリーを割り当てるかだ。
または、より少ないメモリーでも高速化できるように、構想を練らなければいけない。
無限に使っても良いメモリーがあり、一番簡単に実現する方法なら今すぐ出来るが、
なるべく少ないメモリーで上手いことやろうとすると、どうやるのが良いかなと考えちゃう。
なにせ、いろんな言語ごとに3種類のキーワードを持つとなると、
それら全てに対して無駄にテーブルを持つ事のはどうかなと思ってしまう。
まして、現時点で自分の環境で遅いと感じていないのに、
体感できない高速化のためにメモリーを消費する気にはなれない。
また、ハッシュテーブル作成の仕事をアプリ起動時にやらせるのもまずいので、
あらかじめ作ったテーブルを持たせたら実行ファイルもまた大きくなる。
知的好奇心により、無駄な高速化はしたいが、その分のマイナスも気になる。
いや、試してみようという気になってはいるが、使い物になるかどうか微妙。

ハッシュテーブルに関しては、昨日たまたま目にしたあるもので初めて知り、納得した。
でも、あたしみたいな素人ではなく、ちゃんと勉強してる人には当たり前のものらしい。
だからテキストエディタは素人ではなく、ちゃんとした人が知識を持って作るべきだとまた実感。
おそらく真魚も、ちゃんとした人の手にかかればものすごく効率化されるはずだ。

たぶん関連のある記事:

コメントは終了しています。