मेरे पास एक सेगमेंट ट्री है जिसमें संख्याओं की एक श्रृंखला के लिए डेटा है (डेटा संरचना चुनी गई है >यहां)। यहाँ कोड है:

class SegmentTree:
    def __init__(self, N):
        def _init(b, e):
            if b is e:
                data = foo() # No dependency
                return Node(b, e, data, None, None)
            else:
                mid = (b + e ) / 2

                L = _init(b, mid)
                R = _init(mid + 1, e)

                data = foo() #Data depends on L and R

                return Node(b, e, data, L, R)

        self.root = _init(1, N)

यह अधिकतम रिकर्सन गहराई से अधिक त्रुटि के साथ एन लगभग 300 के लिए विफल रहता है। क्या पुनरावर्ती के बजाय पुनरावृत्त रूप से पेड़ बनाने का कोई तरीका है?

3
knite 9 अक्टूबर 2011, 21:22

2 जवाब

सबसे बढ़िया उत्तर

वास्तविक समस्या आपके एल्गोरिथ्म की पुनरावृत्ति गहराई नहीं है, जो कि 300 जैसे मान के लिए लगभग 10 होनी चाहिए, लेकिन यह कि आप संख्याओं की तुलना is से कर रहे हैं। is कीवर्ड ऑब्जेक्ट की पहचान की जांच करता है, जबकि == समानता की जांच करता है:

>>> 300 == 299+1
True
>>> 300 is 299+1
False

उसके कारण आपकी if शर्त जो कि रिकर्सन को समाप्त कर देगी, कभी भी सत्य नहीं होगी और फ़ंक्शन पुनरावर्ती रहेगा, भले ही b और e बराबर हों।

यदि आप if बदलते हैं तो यह समस्या दूर हो जानी चाहिए:

if b == e:
   ...

छोटी संख्या के लिए समस्या नहीं हो सकती है क्योंकि पायथन "caches" और एक निश्चित आकार तक के ints के लिए वस्तुओं का पुन: उपयोग करता है।

6
Community 23 मई 2017, 15:00

आम तौर पर, जिस तरह से आप रिकर्सन से पुनरावर्तक में कनवर्ट करते हैं, वह मैन्युअल रूप से स्टैक (या कतार) को बनाए रखना है।

कुछ इस तरह:

 while stack is not empty:
     item = pop from stack

     do processing (such as adding onto the node)

     push L and R onto the stack

स्मृति में ढेर बढ़ता है, क्योंकि प्रत्येक आइटम के लिए आप पॉप कर रहे हैं, आप दो को दबा रहे हैं।

1
Donald Miner 9 अक्टूबर 2011, 21:26
हां, मैं यह करना चाहता था, लेकिन मुझे एल और आर नोड्स बनाने के बाद (पुनरावर्ती) वर्तमान नोड पर अपना प्रसंस्करण करने की आवश्यकता है। मुझे यकीन नहीं है कि भविष्य के प्रसंस्करण के लिए वर्तमान नोड को कहां/कैसे छिपाना है - एक अलग ढेर पर?
 – 
knite
9 अक्टूबर 2011, 21:32
वैसे आमतौर पर "स्टैक" का उपयोग करने के बजाय ट्री ट्रैवर्सल (हालांकि वे पॉइंटर ट्विडलिंग और सामान के साथ जटिल हो सकते हैं) को लागू करने के बेहतर तरीके हैं। आखिरकार यदि आप ढेर पर ढेर का उपयोग करते हैं तो आप वास्तव में ज्यादा जगह नहीं बचा रहे हैं (एक स्थिर कारक के अलावा क्योंकि आपको कम राज्य बचाने की जरूरत है)
 – 
Voo
11 अक्टूबर 2011, 04:22