<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                ## 問題 你使用訪問者模式遍歷一個很深的嵌套樹形數據結構,并且因為超過嵌套層級限制而失敗。你想消除遞歸,并同時保持訪問者編程模式。 ## 解決方案 通過巧妙的使用生成器可以在樹遍歷或搜索算法中消除遞歸。在8.21小節中,我們給出了一個訪問者類。下面我們利用一個棧和生成器重新實現這個類: import types class Node: pass class NodeVisitor: def visit(self, node): stack = [node] last_result = None while stack: try: last = stack[-1] if isinstance(last, types.GeneratorType): stack.append(last.send(last_result)) last_result = None elif isinstance(last, Node): stack.append(self._visit(stack.pop())) else: last_result = stack.pop() except StopIteration: stack.pop() return last_result def _visit(self, node): methname = 'visit_' + type(node).__name__ meth = getattr(self, methname, None) if meth is None: meth = self.generic_visit return meth(node) def generic_visit(self, node): raise RuntimeError('No {} method'.format('visit_' + type(node).__name__)) 如果你使用這個類,也能達到相同的效果。事實上你完全可以將它作為上一節中的訪問者模式的替代實現。考慮如下代碼,遍歷一個表達式的樹: class UnaryOperator(Node): def __init__(self, operand): self.operand = operand class BinaryOperator(Node): def __init__(self, left, right): self.left = left self.right = right class Add(BinaryOperator): pass class Sub(BinaryOperator): pass class Mul(BinaryOperator): pass class Div(BinaryOperator): pass class Negate(UnaryOperator): pass class Number(Node): def __init__(self, value): self.value = value # A sample visitor class that evaluates expressions class Evaluator(NodeVisitor): def visit_Number(self, node): return node.value def visit_Add(self, node): return self.visit(node.left) + self.visit(node.right) def visit_Sub(self, node): return self.visit(node.left) - self.visit(node.right) def visit_Mul(self, node): return self.visit(node.left) * self.visit(node.right) def visit_Div(self, node): return self.visit(node.left) / self.visit(node.right) def visit_Negate(self, node): return -self.visit(node.operand) if __name__ == '__main__': # 1 + 2*(3-4) / 5 t1 = Sub(Number(3), Number(4)) t2 = Mul(Number(2), t1) t3 = Div(t2, Number(5)) t4 = Add(Number(1), t3) # Evaluate it e = Evaluator() print(e.visit(t4)) # Outputs 0.6 如果嵌套層次太深那么上述的Evaluator就會失效: >>> a = Number(0) >>> for n in range(1, 100000): ... a = Add(a, Number(n)) ... >>> e = Evaluator() >>> e.visit(a) Traceback (most recent call last): ... File "visitor.py", line 29, in _visit return meth(node) File "visitor.py", line 67, in visit_Add return self.visit(node.left) + self.visit(node.right) RuntimeError: maximum recursion depth exceeded >>> 現在我們稍微修改下上面的Evaluator: class Evaluator(NodeVisitor): def visit_Number(self, node): return node.value def visit_Add(self, node): yield (yield node.left) + (yield node.right) def visit_Sub(self, node): yield (yield node.left) - (yield node.right) def visit_Mul(self, node): yield (yield node.left) * (yield node.right) def visit_Div(self, node): yield (yield node.left) / (yield node.right) def visit_Negate(self, node): yield - (yield node.operand) 再次運行,就不會報錯了: >>> a = Number(0) >>> for n in range(1,100000): ... a = Add(a, Number(n)) ... >>> e = Evaluator() >>> e.visit(a) 4999950000 >>> 如果你還想添加其他自定義邏輯也沒問題: class Evaluator(NodeVisitor): ... def visit_Add(self, node): print('Add:', node) lhs = yield node.left print('left=', lhs) rhs = yield node.right print('right=', rhs) yield lhs + rhs ... 下面是簡單的測試: >>> e = Evaluator() >>> e.visit(t4) Add: <__main__.Add object at 0x1006a8d90> left= 1 right= -0.4 0.6 >>> ## 討論 這一小節我們演示了生成器和協程在程序控制流方面的強大功能。避免遞歸的一個通常方法是使用一個棧或隊列的數據結構。例如,深度優先的遍歷算法,第一次碰到一個節點時將其壓入棧中,處理完后彈出棧。`visit()` 方法的核心思路就是這樣。 另外一個需要理解的就是生成器中yield語句。當碰到yield語句時,生成器會返回一個數據并暫時掛起。上面的例子使用這個技術來代替了遞歸。例如,之前我們是這樣寫遞歸: value = self.visit(node.left) 現在換成yield語句: value = yield node.left 它會將 `node.left` 返回給 `visti()` 方法,然后 `visti()` 方法調用那個節點相應的 `vist_Name()` 方法。yield暫時將程序控制器讓出給調用者,當執行完后,結果會賦值給value, 看完這一小節,你也許想去尋找其它沒有yield語句的方案。但是這么做沒有必要,你必須處理很多棘手的問題。例如,為了消除遞歸,你必須要維護一個棧結構,如果不使用生成器,代碼會變得很臃腫,到處都是棧操作語句、回調函數等。實際上,使用yield語句可以讓你寫出非常漂亮的代碼,它消除了遞歸但是看上去又很像遞歸實現,代碼很簡潔。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看