5

私のアッカーマン関数がスタックオーバーフローを作成しないようにする方法はありますか?それは比較的小さな数、つまり (4,2) に対して行います。これがエラーです

{現在のスレッドがスタック オーバーフロー状態にあるため、式を評価できません。}

private void  Button1Click(object sender, EventArgs e)
        {
            var t = Ackermann(4,2);
            label1.Text += string.Format(": {0}", t);
            label1.Visible = true;
        }

        int Ackermann(uint m, uint n)
        {
            if (m == 0)
                return  (int) (n+1);
            if (m > 0 && n == 0)
                return Ackermann(m - 1, 1);
            if (m > 0 && n > 0)
                return Ackermann(m - 1, (uint)Ackermann(m, n - 1));
            else
            {
                return -1;
            }
        }
4

2 に答える 2

26

回避する最善の方法StackOverflowExceptionは、スタックを使用しないことです。

で呼び出すと意味がないので、負のケースを取り除きましょうuint。あるいは、他の可能性が考慮される前に、否定的なテストをメソッドの最初のものにすると、ここに続くことも機能します。

まず、より大きなボートが必要になります。

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        if (m == 0)
            return  n+1;
        if (n == 0)
            return Ackermann(m - 1, 1);
        else
            return Ackermann(m - 1, Ackermann(m, n - 1));
    }

現在、成功は少なくとも数学的に可能です。さて、n == 0ケースは非常に単純なテールコールです。手で消しましょう。gotoこれは一時的なものであり、ヴェロキラプトルやダイクストラについて心配する必要がないため、使用します。

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
    restart:
        if (m == 0)
            return  n+1;
        if (n == 0)
        {
            m--;
            n = 1;
            goto restart;
        }
        else
            return Ackermann(m - 1, Ackermann(m, n - 1));
    }

これは、スタックを吹き飛ばすのにもう少し時間がかかりますが、吹き飛ばしてください。ただし、このフォームを見るとm、再帰呼び出しの戻りによって が設定されることはありませんが、設定されるnこともあります。

これを拡張すると、これを反復形式に変えることができますが、 の以前の値を追跡することだけを処理する必要がありm、再帰形式で戻る場所をn反復形式で割り当てます。m処理を待っている sがなくなると、 の現在の値を返しnます。

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        Stack<BigInteger> stack = new Stack<BigInteger>();
        stack.Push(m);
        while(stack.Count != 0)
        {
            m = stack.Pop();
            if(m == 0)
                n = n + 1;
            else if(n == 0)
            {
                stack.Push(m - 1);
                n = 1;
            }
            else
            {
                stack.Push(m - 1);
                stack.Push(m);
                --n;
            }
        }
        return n;
    }

この時点で、OP の質問に回答しました。実行には時間がかかりますが、試行された値 (m = 4、n = 2) が返されます。がスローされることはありませんが、およびStackOverflowExceptionの特定の値を超えるとメモリが不足します。mn

さらなる最適化として、スタックへの値の追加をスキップして、直後にポップすることができます。

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        Stack<BigInteger> stack = new Stack<BigInteger>();
        stack.Push(m);
        while(stack.Count != 0)
        {
            m = stack.Pop();
        skipStack:
            if(m == 0)
                n = n + 1;
            else if(n == 0)
            {
                --m;
                n = 1;
                goto skipStack;
            }
            else
            {
                stack.Push(m - 1);
                --n;
                goto skipStack;
            }
        }
        return n;
    }

これは、スタックやヒープでは意味がありませんが、大きな値を処理するループの数を考えると、削ることができるすべてのビットはそれだけの価値があります。

その最適化を維持しながら削除gotoすることは、読者の演習として残されています:)

ちなみに、私はこれをテストするのに焦りすぎたので、m が 3 未満の場合にアッカーマン関数の既知のプロパティを使用する不正な形式を作成しました。

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        Stack<BigInteger> stack = new Stack<BigInteger>();
        stack.Push(m);
        while(stack.Count != 0)
        {
            m = stack.Pop();
        skipStack:
            if(m == 0)
                n = n + 1;
            else if(m == 1)
                n = n + 2;
            else if(m == 2)
                n = n * 2 + 3;
            else if(n == 0)
            {
                --m;
                n = 1;
                goto skipStack;
            }
            else
            {
                stack.Push(m - 1);
                --n;
                goto skipStack;
            }
        }
        return n;
    }

このバージョンでは、1 秒強でtrueforの結果を取得できますAckermann(4, 2) == BigInteger.Pow(2, 65536) - 3(Mono、リリース ビルド、Core i7 で実行)。非チート バージョンは のような値に対して正しい結果を返すことに一貫性があるためm、これを以前のバージョンの正確さの合理的な証拠と見なしますが、実行したままにして様子を見ていきます。

編集: もちろん、以前のバージョンが賢明な時間枠で戻るとは思っていませんが、とにかく実行したままにして、メモリの使用状況を確認することにしました。6 時間後には 40MiB を下回っています。明らかに実用的ではありませんが、実際のマシンで十分な時間が与えられれば、実際に戻ってくることを非常に嬉しく思います.

編集: どうやらStack<T>、2³¹ アイテムの内部制限に達すると、一種の「スタック オーバーフロー」としてもカウントされると主張されているようです。必要な場合にも対処できます。

public class OverflowlessStack <T>
{
    internal sealed class SinglyLinkedNode
    {
        //Larger the better, but we want to be low enough
        //to demonstrate the case where we overflow a node
        //and hence create another.
        private const int ArraySize = 2048;
        T [] _array;
        int _size;
        public SinglyLinkedNode Next;
        public SinglyLinkedNode()
        {
            _array = new T[ArraySize];
        }
        public bool IsEmpty{ get{return _size == 0;} }
        public SinglyLinkedNode Push(T item)
        {
            if(_size == ArraySize - 1)
            {
                SinglyLinkedNode n = new SinglyLinkedNode();
                n.Next = this;
                n.Push(item);
                return n;
            }
            _array [_size++] = item;
            return this;
        }
        public T Pop()
        {
            return _array[--_size];
        }
    }
    private SinglyLinkedNode _head = new SinglyLinkedNode();

    public T Pop ()
    {
        T ret = _head.Pop();
        if(_head.IsEmpty && _head.Next != null)
            _head = _head.Next;
        return ret;
    }
    public void Push (T item)
    {
        _head = _head.Push(item);
    }
    public bool IsEmpty
    {
        get { return _head.Next == null && _head.IsEmpty; }
    }
}
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
    var stack = new OverflowlessStack<BigInteger>();
    stack.Push(m);
    while(!stack.IsEmpty)
    {
        m = stack.Pop();
    skipStack:
        if(m == 0)
            n = n + 1;
        else if(m == 1)
            n = n + 2;
        else if(m == 2)
            n = n * 2 + 3;
        else if(n == 0)
        {
            --m;
            n = 1;
            goto skipStack;
        }
        else
        {
            stack.Push(m - 1);
            --n;
            goto skipStack;
        }
    }
    return n;
}

再度呼び出すと、以下がAckermann(4, 2)返されます。

ここに画像の説明を入力

これは正しい結果です。使用されるスタック構造は決してスローされないため、残っている唯一の制限はヒープです (もちろん、十分な大きさの入力がある場合は、測定単位として「宇宙寿命」を使用する必要があります...)。

その使用方法はチューリング マシンのテープに似ているため、計算可能な関数は十分なサイズのチューリング マシンで計算できるというテーゼを思い出します。

于 2012-08-30T00:27:50.553 に答える
1

メモ化を使用します。何かのようなもの：

private static Dictionary<int, int> a = new Dictionary<int, int>();

private static int Pack(int m, int n) {
 return m * 1000 + n;
}

private static int Ackermann(int m, int n) {
  int x;
  if (!a.TryGetValue(Pack(m, n), out x)) {
    if (m == 0) {
      x = n + 1;
    } else if (m > 0 && n == 0) {
      x = Ackermann(m - 1, 1);
    } else if (m > 0 && n > 0) {
      x = Ackermann(m - 1, Ackermann(m, n - 1));
    } else {
      x = -1;
    }
    a[Pack(m, n)] = x;
  }
  return x;
}

intただし、この例は概念のみを示しており、結果を保持するには小さすぎるため、Ackermann(4, 2) の正しい結果は得られません。そのためには、32 ではなく 65536 ビットの整数が必要です。

于 2012-08-29T21:41:41.590 に答える