मैं अपने एकरमैन फ़ंक्शन को ढेर से बहने से कैसे रोक सकता हूं?

Question

क्या मेरे एकरमैन फ़ंक्शन को प्रवाह पर ढेर बनाने से रोकने का कोई तरीका है, यह अपेक्षाकृत छोटी संख्याओं के लिए है, यानी (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; 
      } 
     } 

Answer 1

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 के साथ निपटा जाना अभी बाकी रों से बाहर चलाने के लिए, हम 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; 
    } 

इस बिंदु पर, हम ओ पी के सवाल का जवाब दे दिया है। इसे चलाने में लंबा समय लगेगा, लेकिन यह कोशिश किए गए मानों के साथ वापस आ जाएगा (m = 4, n = 2)। यह कभी भी StackOverflowException फेंक नहीं देगा, हालांकि यह m और 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(); 
     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 को खत्म करते हुए कहा कि अनुकूलन रखने पाठक :)

संयोग के लिए एक व्यायाम के रूप में छोड़ दिया जाता है, मैं इस परीक्षण में भी अधीर हो गया है, इसलिए मैं एकरमैन समारोह के नाम से जाना जाता गुण जब मीटर का उपयोग करता है एक धोखाधड़ी रूप से किया था

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; 
    } 

इस संस्करण के साथ, मैं true का एक परिणाम के Ackermann(4, 2) == BigInteger.Pow(2, 65536) - 3 के लिए एक छोटे से बाद एक दूसरा से अधिक प्राप्त कर सकते हैं (मोनो, रिलीज निर्माण, एक कोर i7 पर चल रहा है): 3 से कम है। यह देखते हुए कि गैर-धोखाधड़ी संस्करण m के ऐसे मानों के सही परिणाम को वापस करने में लगातार है, मैं इसे पिछले संस्करण की शुद्धता के उचित सबूत के रूप में लेता हूं, लेकिन मैं इसे चलाना और देखूंगा।

संपादित करें: बेशक, मैं वास्तव में पिछले संस्करण को किसी भी समझदार समय सीमा में वापस आने की उम्मीद नहीं कर रहा हूं, लेकिन मैंने सोचा कि मैं इसे किसी भी तरह से चलाना छोड़ दूंगा और देख सकता हूं कि इसकी स्मृति का उपयोग कैसे हुआ। 6 घंटों के बाद यह 40 एमआईबी के तहत अच्छी तरह से बैठा है। मैं बहुत खुश हूं कि स्पष्ट रूप से अव्यवहारिक होने पर, वास्तविक मशीन पर पर्याप्त समय देने पर यह वास्तव में वापस आ जाएगा।

संपादित करें: जाहिर है कि यह तर्क दिया जा रहा है कि 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) रिटर्न बुला:: हम अगर हम भी होना चाहिए कि के साथ सौदा कर सकते हैं

कौन सा सही परिणाम है। इस्तेमाल की गई ढेर संरचना कभी फेंक नहीं जाएगी, इसलिए शेष सीमा केवल ढेर है (और निश्चित रूप से समय, बड़े पर्याप्त इनपुट के साथ आपको माप की इकाई के रूप में "ब्रह्मांड जीवनकाल" का उपयोग करना होगा ...)।

जिस तरह से इसका उपयोग किया जाता है, ट्यूरिंग मशीन के टेप के समान होता है, हमें थिसिस की याद दिलाई जाती है कि किसी भी गणना योग्य फ़ंक्शन की गणना पर्याप्त आकार की ट्यूरिंग मशीन पर की जा सकती है।

Answer 2

उपयोग Memoization है। कुछ की तरह:

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; 
} 

हालांकि, यह उदाहरण केवल अवधारणा पता चलता है, यह अभी भी एकरमैन (4, 2), परिणाम धारण करने के लिए एक int रास्ता बहुत छोटा है के रूप में के लिए सही परिणाम नहीं देंगे। इसके लिए 32 के बजाय आपको 65536 बिट्स के साथ एक पूर्णांक की आवश्यकता होगी।