  |
2010/05/16 23:40
こんにちは。昨日会った者です（これで特定するには情報不足だけど、まあわかるよね）。
で「幅優先探索でやる」という方針自体はいいと思うし、データ構造の作り方も基本は押さえていると思います（斜め読みしかしてませんが）。
ただ、コーディングの発想が「C で作る」という大方針から見て、少しちぐはぐな印象も受けます。データ構造の設計や操作の部分、汎用のライブラリを作ろうというのならあれでもいいと思うのですが、わざわざ汎用のライブラリを使わずに自分で専用の道具を一から作ろうというのなら、問題の性質を考慮して能率良くやることが大事です。
ところが、ここに載っているコードを見ると、見かけが C らしくなく、C++ や Java の劣化版のような印象を受けます。記法（マクロを大文字化しない、ルーチン名を大文字で始めるなど）だけの問題ではなく、データ構造の設計思想が「C で書く」という方針と矛盾しているように見えます。
もう少し具体的に言うと、そもそも C というのは現在 Web 系の世界などで流行のスクリプト言語類とは逆で、汎用言語でありながら低レベル（ハードウェアに近い）処理が簡単にできることに特色があります。つまり、組み込みを想定してプラットフォーム非依存のコードを書いたり、ハードウェアの特性を考慮して低レベルな最適化をやりたいというときに適しています。
そこでこの問題ですが、これを C でやるということは、処理速度や使用メモリ量の最適化が要求される状況、つまり迷路の大きさが途方もなく大きいような状況を想定すべきです。もっと言ってしまえばこの問題、たとえば画像処理などで似たような発想が要求されることがあります。このため、どうすれば時間のかかる処理を切りつめることができるかを考えてやらねばなりません。
このプログラムの場合、時間のかかる処理の代表格である malloc() が大量に使われています。これはいかにもまずいです。このような大量データを処理する場合の定石は、あらかじめ必要なだけメモリを確保しておいて、自分で割り当てることです。具体的には、必要と想定される量だけメモリを配列の形でどかっと確保しておいて、配列のインデックスをポインタ代わりに使います。そして、足りなくなったら倍々のような感じでメモリを realloc() してやればよいのです。
なお、そのような観点で言って、木の各節点の子の数は高々 4 （スタート地点が内点でないとすれば 3）であることを使っていることはよいと思います。ここで「子のリスト」とかを作ってしまっていたらこれはもうアホもいいところですから（容量の節約にすらなりません）。
そんな感じでしょうか。
とにかく、この手の問題は、アルゴリズムさえわかっていれば可読性もヘッタクレもないので、「短く書く」というような表層的なことよりも、何が求められているのかをよく考えて、柔軟に設計思想を考えることが大事だと思います。
2010/05/17 13:54
Oさんですね。専門的なコメントありがとうございます！cで書くと言いつつObjective-Cっぽい発想で書いていました。マクロの命名もその影響で、関数はImage Magickなどに似た命名規則になっている気がします。mallocを使いすぎると時間がかかるということは全然意識していませんでした。今度作るときはメモリ管理を自前で用意する発想を取り入れてみたいです。参考になるコメントありがとうございました！
8
