पायथन

Question

में गहराई से पहले पेड़ इटरेटर को कार्यान्वित करना मैं पाइथन में अनिवार्य रूप से बाइनरी पेड़ों के लिए एक इटरेटर वर्ग को लागू करने की कोशिश कर रहा हूं। इटरेटर को पेड़ के रूट नोड के साथ बनाया गया है, इसके next() फ़ंक्शन को गहराई से पहले क्रम में पेड़ को पार करने के लिए बार-बार कहा जा सकता है (उदाहरण के लिए, this order), अंततः None लौटाते समय कोई नोड नहीं छोड़ा जाता है।

class Node(object): 

    def __init__(self, title, children=None): 
     self.title = title 
     self.children = children or [] 
     self.visited = False 

    def __str__(self): 
     return self.title 

आप ऊपर देख सकते हैं, मैं अपनी पहली दृष्टिकोण के लिए नोड्स के लिए एक visited संपत्ति शुरू की, के बाद से मैं इसके चारों ओर एक तरह से नहीं देखा:

यहाँ एक पेड़ के लिए बुनियादी Node वर्ग है । राज्य की कि अतिरिक्त उपाय के साथ, Iterator वर्ग इस तरह दिखता है:

class Iterator(object): 

    def __init__(self, root): 
     self.stack = [] 
     self.current = root 

    def next(self): 
     if self.current is None: 
      return None 

     self.stack.append(self.current) 
     self.current.visited = True 

     # Root case 
     if len(self.stack) == 1: 
      return self.current 

     while self.stack: 
      self.current = self.stack[-1] 
      for child in self.current.children: 
       if not child.visited: 
        self.current = child 
        return child 

      self.stack.pop() 

यह अच्छी तरह से और अच्छा सब है, लेकिन मैं, visited संपत्ति के लिए की जरूरत से छुटकारा पाने के प्रत्यावर्तन या किसी अन्य परिवर्तन का सहारा के बिना चाहते हैं Node कक्षा में।

मुझे जिस राज्य की आवश्यकता है उसे इटरेटर में ख्याल रखा जाना चाहिए, लेकिन मुझे यह पता चल जाएगा कि यह कैसे किया जा सकता है। पूरे पेड़ के लिए एक विज़िट सूची रखना गैर-स्केलेबल और प्रश्न से बाहर है, इसलिए स्टैक का उपयोग करने के लिए एक चालाक तरीका होना चाहिए।

जो मुझे विशेष रूप से भ्रमित करता है वह यह है - next() फ़ंक्शन, निश्चित रूप से, रिटर्न, मुझे याद कैसे हो सकता है कि मैं कुछ भी चिह्नित किए बिना या अतिरिक्त संग्रहण का उपयोग किए बिना कहां गया हूं? सहजता से, मैं बच्चों पर लूपिंग के बारे में सोचता हूं, लेकिन next() फ़ंक्शन रिटर्न मिलने पर वह तर्क टूटा/भूल गया है!

tree = Node(
    'A', [ 
     Node('B', [ 
      Node('C', [ 
       Node('D') 
       ]), 
      Node('E'), 
      ]), 
     Node('F'), 
     Node('G'), 
     ]) 

iter = Iterator(tree) 

out = object() 
while out: 
    out = iter.next() 
    print out 

Answer 1

तुम सच में प्रत्यावर्तन से बचना चाहिए, तो यह इटरेटर काम करता है:: -

अद्यतन यहाँ एक छोटे से परीक्षण है

from collections import deque 

def node_depth_first_iter(node): 
    stack = deque([node]) 
    while stack: 
     # Pop out the first element in the stack 
     node = stack.popleft() 
     yield node 
     # push children onto the front of the stack. 
     # Note that with a deque.extendleft, the first on in is the last 
     # one out, so we need to push them in reverse order. 
     stack.extendleft(reversed(node.children)) 

---

कि कहा के साथ

, मुझे लगता है कि आप कर रहे हैं इस बारे में बहुत मुश्किल सोच रहा है।

class Node(object): 

    def __init__(self, title, children=None): 
     self.title = title 
     self.children = children or [] 

    def __str__(self): 
     return self.title 

    def __iter__(self): 
     yield self 
     for child in self.children: 
      for node in child: 
       yield node 

इन दोनों को अपने परीक्षण पास:

expected = ['A', 'B', 'C', 'D', 'E', 'F', 'G'] 
# Test recursive generator using Node.__iter__ 
assert [str(n) for n in tree] == expected 

# test non-recursive Iterator 
assert [str(n) for n in node_depth_first_iter(tree)] == expected 

और आप आसानी से Node.__iter__ यदि आप पसंद गैर पुनरावर्ती फार्म का उपयोग कर सकते हैं एक अच्छा-OLE '(पुनरावर्ती) जनरेटर भी काम कर देता है :

def __iter__(self): 
    return node_depth_first_iter(self) 

Answer 2

कि अभी भी संभावित, हर लेबल पकड़ सकता है, हालांकि। मैं इटरेटर को एक समय में पेड़ का केवल एक सबसेट रखना चाहता हूं।

लेकिन आप पहले से ही सबकुछ धारण कर रहे हैं। याद रखें कि एक वस्तु अनिवार्य रूप से प्रत्येक विशेषता के लिए एक प्रविष्टि के साथ एक शब्दकोश है। Node का अर्थ है कि आप प्रत्येक Node ऑब्जेक्ट के लिए एक अनावश्यक "visited" कुंजी और False मान संग्रहीत कर रहे हैं, इससे कोई फर्क नहीं पड़ता। एक सेट, कम से कम, की क्षमता प्रत्येक भी नोड आईडी को रखने की क्षमता है।इसे आज़माएं:

class Iterator(object): 
    def __init__(self, root): 
     self.visited_ids = set() 
     ... 

    def next(self): 
     ... 
     #self.current.visited = True 
     self.visited_ids.add(id(self.current)) 
     ... 
       #if not child.visited: 
       if id(child) not in self.visited_ids: 

सेट में आईडी को देखना नोड की विशेषता तक पहुंचने के जितना तेज़ होना चाहिए। आपके समाधान की तुलना में यह अधिक अपर्याप्त तरीका हो सकता है सेट सेट ऑब्जेक्ट का ओवरहेड (इसके तत्व नहीं), जो केवल एक चिंता है यदि आपके पास एकाधिक समवर्ती इटरेटर हैं (जो आप स्पष्ट रूप से नहीं करते हैं, अन्यथा नोड visited विशेषता नहीं हो सकती आपके लिए उपयोगी नहीं होगा)।