我有一些结构非常昂贵的比较。(它们实际上是具有不同分支的树)为它们计算散列值也很昂贵。
我想为eq操作符创建一个decorator,它将缓存一些结果以加快速度。这有点像回忆录。
尤其是,我希望这样的事情发生。假设我们有三个对象:A、B和C。
我们比较a和b。eq运算符被调用,返回true,结果被存储。我们比较B和C,eq算符像以前一样被调用现在我们比较A和C。现在算法应该检测A等于B,B等于C,所以它应该返回A等于C,而不调用代价高昂的eq运算符。
我想使用union-find算法,但它只允许缓存等式,不允许缓存不等式。
假设我们有两个相等的对象:A和B。假设我们还有另一对相等的对象:C和D。联合查找算法将它们正确地分为两类(A,B)和(C,D)现在假设A不等于C,我的算法应该以某种方式缓存它,并防止eq运算符进一步在对(A,C),(B,C),(A,D),(B,D)上运行,因为我们可以推断所有这些对都是不相等的联合查找不允许这样做它只保留了正的等式,当我们不得不比较许多不相等的对象时,它失败得很惨。
我目前的解决方案是这样的:

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来查找很可能相等的对象,因此我们很少需要调用原始的相等运算符但是,正如我所说,hash函数在我的树上非常慢(它基本上需要遍历所有树,比较每个节点上的分支以删除重复项),所以我想删除它。我想缓存负结果。
有人知道解决这个问题的好办法吗我不仅需要缓存正比较结果,还需要缓存负比较结果。
更新:
我目前的解决方案是:
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的速度。

最佳答案

这不是一个很好的解决方案,但是对于一个等价类的每个leader(即Union Find结构中的一个根),如何存储一个二进制搜索树,其中至少包含(见下文)它绝对不等于的所有leader。
要查询x ?= y:像往常一样,您会找到它们的领导者,并查看它们是否相等如果他们不平等,在另一个的BST中找到一个领导。如果存在,xy绝对不相等。
合并两个等价类xy:合并其领导的bst,并将其设置为xy联合的新领导的bst。进入其中一个bst并随后成为非leader的节点永远不会从bst中移除,但这不是一个大问题-它不会导致任何查询返回错误的结果,它只是浪费了一些空间(但不会浪费很多空间)。

关于algorithm - 优化平等和不平等运算符(operator),我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/20524939/

10-10 03:46