スタックの速度改善
 永字八法 - スタックまとめを読んでしまったので、取り急ぎ文章だけでも。以下の文章を読む時は永字八法 - スタックまとめを見ながら読むことをお勧めします。自分も見ながら書いたんで。

 まず1点目。
「この考え方はさらに推し進めると、push, popの際に、スタックに使う変数を指定する遣り方が考えられる。つまり、特別にスタック用領域をスタックで用意するのではなく、スタックを使う側に用意させる方法である。これならば、スタック領域も過不足なく用意できるだろう。」
 と「スタックのローカライズ」の項でむいむいさんがおっしゃっていますが、まっことそのとおりです。現在Tempライブラリを作成中ですが、ライブラリに組み込んだ内部命令のpush/popには変数番号を渡していますからね。
 正直、変数番号管理の方がやりやすいんでしょうが、スタック領域の破壊をなるべく防ぐことと、スクリプトに余り慣れていない人にもこっちの方が安心して使えるのではないだろうかということで、スタック番号で管理するようにしました。次回はスタック番号でも変数番号でも扱えるようにバージョンアップしましょう。

 で、2点目。こっちが本題。
 「しかしその実装方式(splitの性質をうまく利用して切り出すなどの見るべき点も多い)は、同時にスタックの大きさ(限界)に不確定性を持ち込んでしまった。それに、速度の点で疑問が残る。スタックの積み方からして、積めば積むほど実行速度が遅くなることがわかるからだ。スクリプトの簡便さとのトレードオフの問題なのだろうが。」
 またもやむいむいさんの記事からの抜粋ですが、確かに文字列変数を用いた簡易スタックの問題は、スタックサイズと実行速度の2点なんですよね。
 むいむいさんはこの問題を解決するために固定長スタック、つまり入れる要素の方に工夫を施すことで対処を行うことを提案なさっています。ところが、自分が考えていたのはちょうどこれと反対方向への対策でした。むいむいさんの方法を「箱に入れる物のサイズを統一することで問題を解決する考え方」だとしたら、自分の方法は「箱を増やすことで問題を解決する考え方」です。要は、1.にあるNScLisperの中の人ことzickさんのやり方と2.の自分のやり方を合わせたものです。

 では、どうやるのか。まず、ある一定数の文字変数をスタック用領域として確保しておき(定数で確保してもいいし、引数などで指定させてもいい)、また数字変数を「スタック用文字変数の変数番号へのカーソル」として確保しておきます。次に、スタック1つの最大サイズを指定しておきます。そしてpush命令内部で、スタックの最大サイズを超えたら、カーソルを次のスタックに移します。
 説明だけでは理解しにくいと思いますので、具体的にどんな処理をするのか、文字列スタックを例に書いていきましょう。
 まず、文字変数$0~$9までをスタック用領域として確保します。また、数字変数%0をスタックへのカーソルとして確保し、%0に文字変数$0の変数番号である0を代入しておきます。スタック1つの最大サイズはとりあえず10としておきましょう。
 そして、とりあえず適当にpushします。例えばabcdefghijkをpushしたとしましょう。スタックのカーソルは0、つまり$0になっているので、$0にpushした値が格納されます。pushされた値は11バイトなので、これでもうスタック1つの最大サイズを超えてしまいました。
 今までの自分のやり方なら、ここで「スタックオーバーフローが発生しました」とエラーメッセージを出して強制終了させていたところですが、新しいやり方では違います。スタックが最大サイズを超えた場合、スタックのカーソルを次のスタック(この場合$0の次なので$1)に自動的に移すんです。そして次回以降、操作対象のスタックは$1に移り、また$1が一杯になったら$2に……といった感じに処理をしていきます。$9まで一杯になったら、その時になって初めてエラーメッセージを出力します。
 こうすれば1つなぎのスタックとしてかなりの容量を確保できますし、またスタック1つの最大サイズを小さく設定すれば、処理速度の問題も(おそらく)軽減できるでしょう。

 まだ設計段階で、実装に入ったら色々と問題が出てきそうではありますが、Tempライブラリ実装後にスタックver4として、上記のやり方で製作してみたいと思います。
[PR]
by lyricist_m | 2007-07-02 23:47 | NScripter
<< monocro命令が効かない! 簡易スタックver3 >>