Aug 31, 2006

もうC++でプリミティヴはムリ(ってこればっか…)

ポスト @ 1:14:05 | プログラミング,C++,BREW

昨日更新しようと思ったのですが、まったくキーボード上の指が動きませんでした。。
というわけで多少復調した今夜書いています。

ただいまのお題はBREW上で動かす非決定性有限オートマトンエンジンを作る。ちなみにオライリー本は持っておらず買うつもりもありませんので、純粋に理論から組みます。

BREWなのでメモリ制限(正確には、フラグメンテーションに対する制限)がキツいのですが、とりあえずは普通にノードを構造体で抱えてグラフを作ることにします。

そして、それらノードを抱えておくメモリプールをどう管理すればよいのか、で時間が空しく失われてしまっていったのでした…涙


NFAグラフを作るには、繰り返しや分岐などで、挿入やグラフ部分集合のコピーが必要となります。

これを最も簡単に実装できるのはノードに配列を使用することです。挿入では後ろを伸ばして、次要素のポインタ値を挿入するノードの個数だけ加算させてずらしていけばよいし、コピーもその範囲の個数分だけポインタ値を加算しながらコピーしていけばよいだけです。

しかし、プールに配列を使うと、グラフが大きくなったときにどんどんフラグメンテーションが拡大していくに決まってます。苦笑

なので、STL の deque もどきのような仕組みを作り、一定の幅ずつリスト化したプールを割り当てていくことを考えました。

ただ、これで悩みましたよあたしゃ…どうやって挿入やコピーをするの?、って…。

もちろん原理的にはできますけど、次要素のポインタの「ずれ」を、すべての要素について計算しなおしてたらもう膨大なコストがかかるわけですから…


結局、次要素の位置をプラスマイナスの移動幅で表現すれば、恐ろしく簡単に話が済むのだ、という単純な話に今日の夜気づくまで、まる2日以上かかってしまいました

あぁもうホントにだめだ…

Trackback

No Trackbacks

Track from Your Website

http://blog.izumichan.com/trackback/tb.php?id=326

Comment

No Comments

Post Your Comment


*は入力必須です。E-Mailは公開されません。