मेरे पास एक सेगमेंट ट्री है जिसमें संख्याओं की एक श्रृंखला के लिए डेटा है (डेटा संरचना चुनी गई है >यहां)। यहाँ कोड है:
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 के लिए विफल रहता है। क्या पुनरावर्ती के बजाय पुनरावृत्त रूप से पेड़ बनाने का कोई तरीका है?
2 जवाब
वास्तविक समस्या आपके एल्गोरिथ्म की पुनरावृत्ति गहराई नहीं है, जो कि 300 जैसे मान के लिए लगभग 10 होनी चाहिए, लेकिन यह कि आप संख्याओं की तुलना is से कर रहे हैं। is कीवर्ड ऑब्जेक्ट की पहचान की जांच करता है, जबकि == समानता की जांच करता है:
>>> 300 == 299+1
True
>>> 300 is 299+1
False
उसके कारण आपकी if शर्त जो कि रिकर्सन को समाप्त कर देगी, कभी भी सत्य नहीं होगी और फ़ंक्शन पुनरावर्ती रहेगा, भले ही b और e बराबर हों।
यदि आप if बदलते हैं तो यह समस्या दूर हो जानी चाहिए:
if b == e:
...
छोटी संख्या के लिए समस्या नहीं हो सकती है क्योंकि पायथन "caches" और एक निश्चित आकार तक के ints के लिए वस्तुओं का पुन: उपयोग करता है।
आम तौर पर, जिस तरह से आप रिकर्सन से पुनरावर्तक में कनवर्ट करते हैं, वह मैन्युअल रूप से स्टैक (या कतार) को बनाए रखना है।
कुछ इस तरह:
while stack is not empty:
item = pop from stack
do processing (such as adding onto the node)
push L and R onto the stack
स्मृति में ढेर बढ़ता है, क्योंकि प्रत्येक आइटम के लिए आप पॉप कर रहे हैं, आप दो को दबा रहे हैं।
संबंधित सवाल
जुड़े हुए प्रश्न
नए सवाल
python
पायथन एक बहु-प्रतिमान है, गतिशील रूप से टाइप किया हुआ, बहुउद्देशीय प्रोग्रामिंग भाषा है। यह एक साफ और एक समान वाक्यविन्यास सीखने, समझने और उपयोग करने के लिए त्वरित होने के लिए डिज़ाइन किया गया है। कृपया ध्यान दें कि अजगर 2 आधिकारिक तौर पर 01-01-2020 के समर्थन से बाहर है। फिर भी, संस्करण-विशिष्ट पायथन सवालों के लिए, [अजगर -२.०] या [अजगर -३.x] टैग जोड़ें। पायथन वेरिएंट (जैसे, ज्योथन, PyPy) या लाइब्रेरी (उदा।, पांडस और न्यूमपी) का उपयोग करते समय, कृपया इसे टैग में शामिल करें।