深さ優先探索を再帰関数なしで書くと速度はどうなるか？

気になったから適当に書いてみた。

N*Nマスを塗りつぶす深さ優先探索。

dfs1が、愚直に再帰関数で書いたもの

dfs2が、配列をスタックっぽく使って書いたもの

dfs3が、素直にスタックで書いた深さ優先探索

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    int N = 100;
    void calc()
    {
        Stopwatch sw1 = new Stopwatch();
        Stopwatch sw2 = new Stopwatch();
        Stopwatch sw3 = new Stopwatch();
        board = new int[N, N];
        for (int i = 0; i < N; i++)
        {
            board[i, 0] = board[i, N - 1] = board[0, i] = board[N - 1, i] = 99999999;
        }

        int c = 1;
        sw1.Start();
        for (int i = 0; i < 100; i++)
        {
            dfs1(1, 1, c++);
        }
        sw1.Stop();
        sw2.Start();
        for (int i = 0; i < 100; i++)
        {
            dfs2(c++);
        }
        sw2.Stop();
        sw3.Start();
        for (int i = 0; i < 100; i++)
        {
            dfs3(c++);
        }
        sw3.Stop();
        Console.WriteLine(sw1.ElapsedMilliseconds);
        Console.WriteLine(sw2.ElapsedMilliseconds);
        Console.WriteLine(sw3.ElapsedMilliseconds);
    }

    int[,] board;
    int vy = new int { 1, 0, -1, 0 };
    int vx = new int { 0, 1, 0, -1 };

    void dfs1(int y, int x, int count)
    {
        board[y, x] = count;
        for (int i = 0; i < 4; i++)
        {
            int ny = y + vy[i];
            int nx = x + vx[i];
            if (board[ny, nx] < count)
            {
                dfs1(ny, nx, count);
            }
        }
    }

    void dfs2(int count)
    {
        int MAX = 10005;
        int px = new int[MAX];
        int py = new int[MAX];
        int[] pv = new int[MAX];
        px[0] = py[0] = 1;
        pv[0] = 0;
        int p = 0;

        board[1, 1] = count;
        while (p >= 0)
        {
            if (pv[p] == 4) { p--; continue; }
            int ny = py[p] + vy[pv[p]];
            int nx = px[p] + vx[pv[p]];
            if (board[ny, nx] < count)
            {
                board[ny, nx] = count;
                pv[p]++;
                p++;
                px[p] = nx; py[p] = ny; pv[p] = 0;
            }
            else pv[p]++;
        }
    }

    void dfs3(int count)
    {
        int MAX = 10005;
        Stack spx = new Stack();
        Stack spy = new Stack();
        Stack spv = new Stack();
        spx.Push(1);
        spy.Push(1);
        spv.Push(0);

        board[1, 1] = count;
        while (spx.Count != 0)
        {
            int x = spx.Pop();
            int y = spy.Pop();
            int v = spv.Pop();

            int ny = y + vy[v];
            int nx = x + vx[v];

            v++;
            if (v != 4)
            {
                spx.Push(x);
                spy.Push(y);
                spv.Push(v);
            }

            if (board[ny, nx] < count)
            {
                board[ny, nx] = count;
                spx.Push(nx);
                spy.Push(ny);
                spv.Push(0);
            }
        }
    }
}

実行結果

ローカルで、16ms, 24ms, 96ms

ideoneだと、72ms, 119ms, 374ms

余程高速化しない限り、再帰で書いても速度的な問題はなさそう。というか適当に書いたら再帰のが早かった。

標準で入ってるスタックは遅いのかな？それとも出し入れする回数が増えてるのが悪い？にしてもちょっと遅すぎる感があるなぁ。

まぁ、N=200になるとdfs1は死ぬので、基本的には再帰でおっけー。スタックオーバーフローが避けられない時だけ頑張りましょう。まぁ幅優先探索で大体大丈夫だけどね。