algorithm - 优化相等和不等运算符

Question

我有一些比较昂贵的结构。 (它们实际上是具有不同分支的树。)为它们计算哈希值也很昂贵。

我想为 eq 运算符创建一个装饰器，它将缓存一些结果以加快处理速度。这有点类似于内存。

特别是，我希望这样的事情发生。假设我们有 3 个对象:A、B 和 C。我们将 A 与 B 进行比较。eq 运算符被调用，返回 True，结果被存储。我们将 B 与 C 进行比较。eq 运算符像以前一样被调用。现在我们比较 A 和 C。现在算法应该检测到 A 等于 B 和 B 等于 C，因此它应该返回 A 等于 C 而无需调用代价高昂的 eq 运算符。

我想使用联合查找算法，但它只允许缓存等式，不允许缓存不等式。

假设我们有 2 个彼此相等的对象:A 和 B。还假设我们有另一对相等的对象:C 和 D。联合查找算法会将它们正确地分为两类 (A, B)和(C，D)。现在假设 A 不等于 C。我的算法应该以某种方式缓存它并防止 eq 运算符进一步在 (A, C), (B, C) 对上运行, (A, D), (B, D), 因为我们可以推断出所有这些对都是不相等的。 Union-find 不允许这样做。它只保存正等式，当我们必须比较许多不等的对象时会惨败。

我目前的解决方案是这样的:

def optimize(original_eq):
    def optimized_eq(first, second):
        if first is second: return True
        if hash(first) != hash(second): return False
        if cache.find(first) == cache.find(second): return True
        result = original_eq(first, second)
        if result:
            cache.union(first, second)
        else:
            pass # no idea how to save the negative result
        return result
    return optimized_eq

如果散列函数易于计算，则此解决方案还可以，但事实并非如此。我们会在很可能相等的对象上调用 cache.find，因此我们很少需要调用原始的相等运算符。但是，正如我所说，散列函数在我的树上非常慢(它基本上需要遍历所有树，比较每个节点上的分支以删除重复项)，所以我想删除它。我想缓存负面结果。

有人知道解决这个问题的好方法吗？我不仅需要缓存正比较结果，还需要缓存负比较结果。

更新:

我目前适用的解决方案如下:

def memoize_hash_and_eq(cls):
    "This decorator should be applied to the class."

    def union(key1, key2):
        nonlocal union_find
        if key1 is not key2:
            key1_leader = union_find(key1)
            key2_leader = union_find(key2)
            key1_leader._memoize_hash_and_eq__leader = key2_leader
            try:
                key2_leader._memoize_hash_and_eq__splits = key1_leader._memoize_hash_and_eq__splits
                del key1_leader._memoize_hash_and_eq__splits
            except AttributeError:
                pass

    def union_find(key):
        leader = key
        while True:
            try:
                leader = leader._memoize_hash_and_eq__leader
            except AttributeError:
                break
        if leader is not key:
            key._memoize_hash_and_eq__leader = leader
            try:
                leader.__splits = key._memoize_hash_and_eq__splits
                del key._memoize_hash_and_eq__splits
            except AttributeError:
                pass
        return leader

    def split(key1, key2):
        nonlocal union_find
        key1_leader = union_find(key1)
        key2_leader = union_find(key2)
        try:
            key1_leader._memoize_hash_and_eq__splits.add(key2_leader)
        except AttributeError:
            try:
                key2_leader._memoize_hash_and_eq__splits.add(key1_leader)
            except AttributeError:
                try:
                    key1_leader._memoize_hash_and_eq__splits = set()
                    key1_leader._memoize_hash_and_eq__splits.add(key2_leader)
                except (AttributeError, TypeError):
                    pass

    def split_find(key1, key2):
        nonlocal union_find

        key1_leader = union_find(key1)
        key2_leader = union_find(key2)

        try:
            split_leaders = key2_leader._memoize_hash_and_eq__splits
            for k in [_k for _k in split_leaders]:
                split_leaders.add(union_find(k))
            if key1_leader in split_leaders:
                return True
        except (AttributeError, TypeError):
            pass

        try:
            split_leaders = key1_leader._memoize_hash_and_eq__splits
            for k in [_k for _k in split_leaders]:
                split_leaders.add(union_find(k))
            if key2_leader in split_leaders:
                return True
        except (AttributeError, TypeError):
            pass

        return False

    def memoized_hash(self):
        return original_hash(union_find(self))
    original_hash = cls.__hash__
    cls.__hash__ = memoized_hash

    def memoized_equivalence(self, other):
        if self is other:
            return True

        if union_find(self) is union_find(other):
            return True

        if split_find(self, other):
            return False

        result = original_equivalence(self, other)
        if result is NotImplemented:
            return result
        elif result:
            union(self, other)
        else:
            split(self, other)

        return result
    original_equivalence = cls.__eq__
    cls.__eq__ = memoized_equivalence

    return cls

这会加速 eq 和 hash。

Answer 1

这不是一个非常漂亮的解决方案，但是你如何为等价类的每个领导者(即 Union Find 结构中的根)存储至少包含(见下文)所有领导者的二叉搜索树它绝对不等于。

要查询 x ?= y:像往常一样，您会找到它们的首领并查看它们是否相等。如果他们不相等，则在另一个 BST 中找到一个领导者。如果存在，x 和 y 肯定不相等。

合并两个等价类x 和y:合并它们领导者的BST，并将其设置为x 并集的新领导者的BST 和 y。进入 BST 之一并后来成为非领导者的节点永远不会从 BST 中删除，但这不是一个大问题 - 它不会导致任何查询返回错误的结果，它只是浪费了一些空间(但从来没有很多).