ただ、コーディングの発想が「C で作る」という大方針から見て、少しちぐはぐな印象も受けます。データ構造の設計や操作の部分、汎用のライブラリを作ろうというのならあれでもいいと思うのですが、わざわざ汎用のライブラリを使わずに自分で専用の道具を一から作ろうというのなら、問題の性質を考慮して能率良くやることが大事です。

ところが、ここに載っているコードを見ると、見かけが C らしくなく、C++ や Java の劣化版のような印象を受けます。記法（マクロを大文字化しない、ルーチン名を大文字で始めるなど）だけの問題ではなく、データ構造の設計思想が「C で書く」という方針と矛盾しているように見えます。

もう少し具体的に言うと、そもそも C というのは現在 Web 系の世界などで流行のスクリプト言語類とは逆で、汎用言語でありながら低レベル（ハードウェアに近い）処理が簡単にできることに特色があります。つまり、組み込みを想定してプラットフォーム非依存のコードを書いたり、ハードウェアの特性を考慮して低レベルな最適化をやりたいというときに適しています。

そこでこの問題ですが、これを C でやるということは、処理速度や使用メモリ量の最適化が要求される状況、つまり迷路の大きさが途方もなく大きいような状況を想定すべきです。もっと言ってしまえばこの問題、たとえば画像処理などで似たような発想が要求されることがあります。このため、どうすれば時間のかかる処理を切りつめることができるかを考えてやらねばなりません。

このプログラムの場合、時間のかかる処理の代表格である malloc() が大量に使われています。これはいかにもまずいです。このような大量データを処理する場合の定石は、あらかじめ必要なだけメモリを確保しておいて、自分で割り当てることです。具体的には、必要と想定される量だけメモリを配列の形でどかっと確保しておいて、配列のインデックスをポインタ代わりに使います。そして、足りなくなったら倍々のような感じでメモリを realloc() してやればよいのです。

なお、そのような観点で言って、木の各節点の子の数は高々 4 （スタート地点が内点でないとすれば 3）であることを使っていることはよいと思います。ここで「子のリスト」とかを作ってしまっていたらこれはもうアホもいいところですから（容量の節約にすらなりません）。

そんな感じでしょうか。

とにかく、この手の問題は、アルゴリズムさえわかっていれば可読性もヘッタクレもないので、「短く書く」というような表層的なことよりも、何が求められているのかをよく考えて、柔軟に設計思想を考えることが大事だと思います。

2010/05/17 13:54

Oさんですね。専門的なコメントありがとうございます！cで書くと言いつつObjective-Cっぽい発想で書いていました。マクロの命名もその影響で、関数はImage Magickなどに似た命名規則になっている気がします。mallocを使いすぎると時間がかかるということは全然意識していませんでした。今度作るときはメモリ管理を自前で用意する発想を取り入れてみたいです。参考になるコメントありがとうございました！

2010/11/18 23:56

実はいわゆる「正規表現」は形式言語理論でいう正規表現ではないんだけどね……（ぼそっ）

Permalink | 記事への反応(0) | 15:52

2011-01-11

■人材獲得作戦・４　試験問題ほか

http://okajima.air-nifty.com/b/2010/01/post-abc6.html

迷路の最短経路を求める問題が出たので解いてみた

幅優先探索を使えばいいのがわかっていたのですんなりかけたのだが、無限ループになる個所があったので動くようになるまで時間がかかった

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace MazeFind
{
    class Point
    {
        public int x;
        public int y;
        public Point before;
        public Point(int x, int y,Point before)
        {
            this.x = x;
            this.y = y;
            this.before = before;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            const char BreakChar = 'B';
            const char GoalChar = 'G';
            const char WallChar = '*';
            const char BeforeChar = '.';

            StringBuilder[] maze = new StringBuilder[]{
                new StringBuilder("**************************"),
                new StringBuilder("*S* *                    *"),
                new StringBuilder("* * *  *  *************  *"),
                new StringBuilder("* *   *    ************  *"),
                new StringBuilder("*    *                   *"),
                new StringBuilder("************** ***********"),
                new StringBuilder("*                        *"),
                new StringBuilder("** ***********************"),
                new StringBuilder("*      *              G  *"),
                new StringBuilder("*  *      *********** *  *"),
                new StringBuilder("*    *        ******* *  *"),
                new StringBuilder("*       *                *"),
                new StringBuilder("**************************"),
            };
            Point start = new Point(1, 1,null);

            //最短経路を探索する
            Queue&lt;Point&gt; queque = new Queue&lt;Point&gt;();
            queque.Enqueue(start);

            while (queque.Count &gt; 0)
            {
                Point now = queque.Dequeue();
                if (maze[now.y][now.x] == BreakChar)
                    Console.WriteLine("break");
                if (maze[now.y][now.x] == WallChar || maze[now.y][now.x] == BeforeChar)
                    continue;
                else if (maze[now.y][now.x] == GoalChar)
                {
                    Point p = now.before;
                    while (p != null)
                    {
                        maze[p.y][p.x] = '@';
                        p = p.before;
                    }
                    break;
                }

                if (maze[now.y - 1][now.x] != '#')
                {
                    queque.Enqueue(new Point(now.x, now.y - 1, now));
                    maze[now.y][now.x] = '.';
                }
                if (maze[now.y][now.x + 1] != '#')
                {
                    queque.Enqueue(new Point(now.x + 1, now.y, now));
                    maze[now.y][now.x] = '.';
                }
                if (maze[now.y + 1][now.x] != '#')
                {
                    queque.Enqueue(new Point(now.x, now.y + 1, now));
                    maze[now.y][now.x] = '.';
                }
                if (maze[now.y][now.x - 1] != '#')
                {
                    queque.Enqueue(new Point(now.x - 1, now.y, now));
                    maze[now.y][now.x] = '.';
                }
            }

            //結果を出力する
            foreach (StringBuilder s in maze)
                Console.WriteLine(s.ToString().Replace(BeforeChar,' '));

            Console.ReadLine();
        }
    }
}
&lt;||

Permalink | 記事への反応(0) | 04:40

「幅優先探索」を含む日記

■バカエンジニアをはじく面接問題集

■理系卒で聞いたことがないとやばい言葉

■人材獲得作戦・４ 試験問題ほか

■人材獲得作戦・４　試験問題ほか