眉山网站制作,地方生活门户网站,口碑好的品牌网站建设,电子商务网站开发项目假设要实现一个存放多种类型数据结构的对象#xff0c;比如一个存放算术操作数和操作符的树结点#xff0c;需要存放包含一元操作符、二元操作符和数字类型的结点
class Node:passclass UnaryOperator(Node):def __init__(self, operand):self.operand operandclass Binary…假设要实现一个存放多种类型数据结构的对象比如一个存放算术操作数和操作符的树结点需要存放包含一元操作符、二元操作符和数字类型的结点
class Node:passclass UnaryOperator(Node):def __init__(self, operand):self.operand operandclass BinaryOperator(Node):def __init__(self, left, right):self.left leftself.right rightclass Add(BinaryOperator):passclass Sub(BinaryOperator):passclass Mul(BinaryOperator):passclass Div(BinaryOperator):passclass Negative(UnaryOperator):passclass Number(Node):def __init__(self, value):self.value value
执行运算需要这样调用
# 假设运算式子2 - (22) * 2 / 1 2-(8) -6.0
t1 Add(Number(2), Number(2))
t2 Mul(t1, Number(2))
t3 Div(t2, Number(1))
t4 Sub(Number(2), t3)或者这样调用
t5 Sub(Number(2), Div(Mul(Add(Number(2), Number(2)), Number(2)), Number(1)))这样子需要执行多次类的调用极不易读写且冗长有没有一种方法让调用更加通用访问变得简单呢。这里使用访问者模式可以达到这样的目的。
访问者模式能够在不改变元素所属对象结构的情况下操作元素让调用或调用者caller的方式变得简单这种操作常见于的士公司操作当一个乘客叫了一辆的士时的士公司接收到了一个访问者并分配一辆的士去接这个乘客。
首先定义一个访问者结点类VisitorNode实现最基本的访问入口任何访问的方式都需要继承这个访问者结点类并通过这个访问者结点类的visit()方法来访问它的各种操作
# 访问者节点的基类
class NodeVisitor:def visit(self, node):if not isinstance(node, Node): # 不是Node对象时当做一个值返回如果有其他情况可以根据实际来处理return nodeself.meth visit_ type(node).__name__.lower() # type(node)也可以换成node.__class__只要node.__class__不被篡改meth getattr(self, self.meth, None) if meth is None:meth self.generic_visitreturn meth(node)def generic_visit(self, node):raise RuntimeError(fNo {self.meth} method)# 一种访问者对应的类
class Visitor(NodeVisitor):方法的名称定义都要与前面定义过的结点类Node的名称保证一致性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_negative(self, node): # 如果class Negative 命名- class Neg那么 def visit_negative 命名- def visit_negreturn -self.visit(node.operand)def visit_number(self, node):return node.value这里的meth getattr(self, self.meth, None)使用了字符串调用对象方法self.meth动态地根据各类Node类Add, Sub, Mul…的名称定义了对应于类Visitor中的方法visit_add, visit_sub, visit_mul…简化了访问入口的代码当没有获取到对应的方法时会执行generic_visit()并抛出RuntimeError的异常提示访问过程中的异常
如果需要添加一种操作比如取绝对值只需要定义一个类class Abs(Unaryoperator): pass并在类Visitor中定义一个visit_abs(self, node)方法即可不需要做出任何多余的修改更不需要改变存储的结构
这里visit()方法调用了visit_xxx()方法而visit_xxx()可能也调用了visit()本质上是visit()的循环递归调用当数据量变大时效率会变得很慢且递归层次过深时会导致超过限制而失败而下面介绍的就是利用栈和生成器来消除递归提升效率的实现访问者模式的方法
import typesclass Node:passclass BinaryOperator(Node):def __init__(self, left, right):self.left leftself.right rightclass UnaryOperator(Node):def __init__(self, operand):self.operand operandclass Add(BinaryOperator):passclass Sub(BinaryOperator):passclass Mul(BinaryOperator):passclass Div(BinaryOperator):passclass Negative(UnaryOperator):passclass Number(Node):def __init__(self, value): # 与UnaryOperator区别仅命名不同self.value valueclass NodeVisitor:def visit(self, node):# 使用栈生成器来替换原来visit()的递归写法stack [node]last_result None # 执行一个操作最终都会返回一个值while stack:last stack[-1]try:if isinstance(last, Node):stack.append(self._visit(stack.pop()))elif isinstance(last, types.GeneratorType): # GeneratorType会是上一个if返回的对象这个对象会返回两个node执行算术之后的结果# 如果是生成器不pop掉而是不断send直到StopIteration# 如果last_result不是None这个值会给回到生成器例如2被visit_add()的左值接收到stack.append(last.send(last_result))last_result Noneelse: # 计算结果是一个值last_result stack.pop()except StopIteration: # 生成器yield结束stack.pop()return last_resultdef _visit(self, node):self.method_name visit_ type(node).__name__.lower()method getattr(self, self.method_name, None)if method is None:self.generic_visit(node)return method(node)def generic_visit(self, node):raise RuntimeError(fNo {self.method_name} method)class Visitor(NodeVisitor):def visit_add(self, node):yield (yield node.left) (yield node.right) # node.left和node.right都可能是Nodedef 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_negative(self, node):yield -(yield node.operand)def visit_number(self, node):return node.value测试是否还会引起超过递归层数的异常
def test_time_cost():import times time.perf_counter()a Number(0)for n in range(1, 100000):a Add(a, Number(n))v Visitor()print(v.visit(a))print(ftime cost:{time.perf_counter() - s})输出正常没有问题
4999950000
time cost:0.9547078最后琢磨出了一个似乎可以作为替代的方法
class Node:passclass UnaryOperator(Node):def __init__(self, operand):self.operand operandclass BinaryOperator(Node):def __init__(self, left, right):self.left leftself.right rightclass Add(BinaryOperator):def __init__(self, left, right):super().__init__(left, right)self.value self.left.value self.right.valueclass Sub(BinaryOperator):def __init__(self, left, right):super().__init__(left, right)self.value self.left.value - self.right.valueclass Mul(BinaryOperator):def __init__(self, left, right):super().__init__(left, right)self.value self.left.value * self.right.valueclass Div(BinaryOperator):def __init__(self, left, right):super().__init__(left, right)self.value self.left.value / self.right.valueclass Negative(UnaryOperator):def __init__(self, operand):super().__init__(operand)self.value -self.operand.valueclass Number(Node):def __init__(self, value):self.value value运行测试
def test_time_cost():import times time.perf_counter()a Number(0)for n in range(1, 100000):a Add(a, Number(n))print(a.value)print(time.perf_counter() - s)输出
4999950000
0.2506986比前面的访问者模式还快而且不用递归- -!
