18

これが私の単純化された二重再帰メソッドです。これは何の役にも立ちませんが、必要な再帰呼び出しを示しています。

void Main()
{
    Test(2, 3, 4);
}

int n1 = 0;
int n2 = 0;

void Test(int i1, int i2, int v)
{
    if (v == 0)
    {
        (n1 + n2).Dump();
    }
    else
    {
        n1 = i1 + 10;
        n2 = i2 + 20;
        Test(n1, n2, v - 1);
        Test(n2, n1, v - 1);
    }   
}

これをループとして記述して、パフォーマンスが向上するかどうかを確認する方法がよくわかりません。

明らかなエラーの例を修正しました。

4

3 に答える 3

4

再帰的に実行できることは、スタックを使用して実行することもできます。例で記述した機能のみが必要であると仮定します。

i1 と i2 は最終的にグローバル変数 n1、n2 の合計に追加されます。それらを合計して、コードの先頭で結果を n1 または n2 に割り当てて、機能を簡素化できます。また、スタックを使用すると、次のようなことができます。

int n1 = 0;
int n2 = 0;

void Test2(int i1, int i2, int v)
{
    Stack<int> s = new Stack<int>(new[] {v});
    n1 = i1 + i2;

    while (s.Any())
    {
        v = s.Pop();
        if (v == 0)
        {
            Console.Out.WriteLine(n1 + n2);
        }
        else
        {
            int tmp = n1;
            n1 = n2 + 10;
            n2 = tmp + 20;
            s.Push(v - 1);
            s.Push(v - 1);
        }
    }
}

これは再帰コードと同じものを出力します:

125
155
155
215
215
245
245
335
335
365
365
425
425
455
455
于 2013-01-16T10:02:21.930 に答える
3

この反復的な (スタックなしの) アプローチを試してください。

int n1 = 0;
int n2 = 0;

void MyWay(int start1, int start2, int plus1, int plus2, int v)
{
    n1 = start2 + plus2 * v;
    n2 = start1 + plus1 * v;
    for (int i = 0, pow = 1 << v; i < pow; i++)
    {
        if ((i & 1) == 0)
        {
            int temp = n2;
            n2 = n1;
            n1 = temp;
        }
        for (int mask = i; mask > 0 && (mask & 1) == 0; mask >>= 1)
        {
            n1 += plus1;
            n2 += plus2;
        }
        Console.WriteLine(n1 + n2);
    }
}

次のように呼び出す必要があります。

MyWay(2, 3, 10, 20, 4);

例のすべての定数は関数に渡されるため、完全に普遍的です。また、重要な事実は、関数の完了後の n1 と n2 の値は、再帰的アプローチの完了後とまったく同じになるということです。

性能について：

確かに、それはいくらかの改善をもたらしますが、それほど多くはありません。しかし、それは大きな入力パラメータで与えます。また、私のアプローチは追加のメモリを消費しません (再帰的およびスタック アプローチは消費します)。

パフォーマンスに関する更新:

私はあなたと私のアプローチをローカルでテストしました-それぞれ1000 000回呼び出します。結果は次のとおりです。

再帰: 225.1774 ミリ秒

反復: 152.1194 ミリ秒

[更新] 関数が完了した後に n1 と n2 が必要ない場合は、コードを短くすることができます。

void MyWayTwo(int start1, int start2, int plus1, int plus2, int v)
{
    plus1 += plus2;
    int n = start1 + start2 + plus1 * v;
    for (int i = 0, pow = 1 << v; i < pow; i++)
    {
        for (int mask = i; mask > 0 && (mask & 1) == 0; mask >>= 1)
            n += plus1;
        Console.WriteLine(n);
    }
}

呼び出し時の出力MyWayTwo(2, 3, 10, 20, 4);:

125
125
155
155
215
215
245
245
335
335
365
365
425
425
455
455

さらに単純化されたソリューション:

void MyWayTwo(int s1, int s2, int p1, int p2, int v)
{
    p1 += p2;
    s1 += s2;
    for (int i = 1 << v, p = i << 1; i < p; i++)
    {
        for (int m = i; (m & 1) == 0; m >>= 1)
            s1 += p1;
        Console.WriteLine(s1);
    }
}
于 2013-01-16T11:46:33.453 に答える
0

最終結果のみを使用する場合は、このコードを提供できます

protected void TestIt(int i1, int i2, int v)
{
    int tot = 0;
    for (; v > 0; v--)
        tot = tot * 2 + 30;
    Console.Out.WriteLine(tot + i1 + i2);
}

中間結果が必要な場合、残念ながらこのコードではそれを提供できません。

于 2013-01-16T10:43:32.397 に答える