python - 在Python中快速比较数据流图

Question

背景

我想证明两个数据处理函数在功能上是等价的。为此，我为每个函数构建了一个抽象语法树，然后运行控制流模拟以构建最终输出的数据流图。

数据流图由 (operation, operanda, operandb) 的三元组表示，这样 (a+b)*2 将表示为:

('*',('+','a','b'),'2')

我的一些操作是可交换的，因此来自等效图的数据流可能是:

('*','2',('+','b','a'))

问题

如何检查我的 2 个数据流图是否同构(即执行完全相同的操作)？

我尝试过的

我的想法是尝试通过检测交换运算符并将它们的操作数按排序顺序(例如字典顺序，尽管我认为顺序不重要，只要我保持一致)将每个数据流图转换为规范形式。然后我可以比较重新排序的元组是否严格相等。

对于我的图表，我认为这个算法应该足够了，即使它不会发现 (a+b)+c 和 a+(b+c) 之间的等价性。

但是，即使是小图，我也遇到了效率问题。

例如，这段 Python 代码构建了一个只有 28 个操作的普通数据流图，但 Python 需要 8 秒来比较元组(并且更大的图会以指数方式变得更糟):

from time import time

def make_dataflow_graph(n):
    A='y'
    for i in range(n):
        A=('+',A,A)
    return A

G1 = make_dataflow_graph(28)
G2 = make_dataflow_graph(28)

t0 = time()
print G1<G2
print time()-t0

我想问题在于 Python 以递归方式进行比较，因此它浪费了大量时间来一次又一次地比较相同的节点。

是否有一些 Pythonic 方法可以使元组比较更有效，或者是否有一些更好的算法来比较我的数据流图？

Answer 1

我不能说它是否是惯用的 Python，但你可以从 Lisp 那里借用一个名为 hash consing 的想法。 .一句话，想法是使用哈希表将子对象共享增加到最大，允许元组通过身份而不是深度比较。

像这样:

canonical_ids = set()
canonical_objs = {}
canonical_tuples = {}

def canonical_object(obj):
    if id(obj) in canonical_ids:
        return obj
    if isinstance(obj, tuple):
        operator, left_operand, right_operand = map(canonical_object, obj)
        if operator in {'+', '*'} and id(left_operand) > id(right_operand):
            left_operand, right_operand = right_operand, left_operand
        obj = operator, left_operand, right_operand
        canon_obj = canonical_tuples.setdefault(tuple(map(id, obj)), obj)
    else:
        canon_obj = canonical_objs.setdefault(obj, obj)
    canonical_ids.add(id(canon_obj))
    return canon_obj

然后你可以做类似的事情

canonical_object(obj1) is canonical_object(obj2)