IDA Session Records

井田 昌之の日々の記録。自己紹介等。

タブコンプの話

関数の呼び出し、もっと単純に言えばある特定機能の呼び出し、これは状況の変化すなわち副作用がなければ同じパラメータを与えれば同じ答えを返してくれる。パラメータが一つでも、仮に1万あったとしてもこれは同じ理屈になる。そして、ほぼ直感的に1秒もかからないで答えがでるような簡単な場合でも、100時間とかかかって計算しないと答えが出ないような場合でも同じ理屈になる。

経験則の活用ということがある。これは、ここでの話の延長で言えば、膨大な数のパラメータを与えればおそらく正しい答えがでるかもしれない機能に対して、過去の経験の蓄積に学んで、そこではあらためて論理的に結論を出さずに、さっと答えをだし、行動することといえる。

これらのことに着目して、後藤英一先生はassoccompそしてtabcompというアイデアの実現に向かった。1970年代中期のことである。最初に書かれたメモをちょうだいして、これは面白いと思った。それまでに学んだ力づく計算のまったく逆を行こうとする話だったから。私にとって、いわばコペルニクス的転回である。「ソフトウェアアルゴリズムの改良は1000倍、1万倍の速度向上をもたらす、ハードウェアの速度向上は、せいぜい2倍3倍というオーダーだ」がすっと理解できた。で、おそまきながら79年までに作っていた私のシステムにその機能を組み込んだ。

簡単な導入的な例の一つとして階乗の計算が語られた。n!である。100!は99!の値に100を掛けたものである。ならば、その時までに計算した階乗の値を覚えておけば、そこからのかけ算をすれば答えがでる。計算をしたら、その結果とパラメータの組み合わせを記憶しておく。新たな計算をする前に、その組み合わせをしたことがあるかをチェックし、あればその結果を利用し、そこからはじめれば、すばやく答に到達できる。

どうするかというと、階乗の例で言えば、n!=n・(n-1)! だからfactorial(x)=if x=0 then 1 else n × factorial(n-1)をそのままプログラムにして計算するようにしておき、計算しながらそこまでに計算した値を記憶するようにしていけば、この定義のままで作る方がループを使ってプログラムにするよりも、多数回の利用の総計算時間を考えると、速くなる。つまり、factorial(x)の計算の最初のステップに、「factorial(x)はすでに計算したことがあるか?そうであれば、その値を返す」ということと、最後の脱出のステップに「factorial(x)の値はyになることを記憶させる」を入れる。すでに計算したことがあるか、は、ソフト的ならハッシング等を利用し、ハード的なら連想メモリを利用することでいける。私はこれでハッシングの良いアルゴリズムの追求へ深入りした。これは一段落するところまで行った。80年代後半に入り、連想メモリをNTTの研究所からもらってこれるようになり、ロジックを作り、後輩の専門家に回路図にしてもらい、自分で半田をし、試作の学会発表まで行った。しかし、実用化まで至らなかった。

階乗の計算のようにパラメータが1つだけではなくて、複数あるいは多数あっても同じことになる。また、階乗のような帰納的定義でなくとも、今までに計算されたことがある、ということしかないから、活用の範囲は広い。経済現象や経営意志決定に使えると今でも思っている。

状況が変化する場合には、この純関数的な定義はダメになる。しかし、上記の仕組みに対して、覚えている答をフラッシュして無くすようにすれば、そうしたタブは無効になり、再計算をするだけになり、ちゃんと機能する。

どうかな、面白いと思ってもらえたかな。

コメントする

Written by masa-ida

8月 28th, 2018 at 10:12 am

Posted in IT

Leave a Reply