1

比較するには非常に高価な構造がいくつかあります。(実際には、別個の枝を持つツリーです。) それらのハッシュ値の計算にもコストがかかります。

処理を高速化するために一部の結果をキャッシュするeq演算子のデコレータを作成したいと考えています。これは、メモ化にいくぶん似ています。

特に、このようなことが起こってほしいです。A、B、C の 3 つのオブジェクトがあるとします。A と B を比較します。eq演算子が呼び出され、True が返され、結果が格納されます。B と C を比較します。前と同じようにeq演算子が呼び出されます。次に、A と C を比較します。アルゴリズムは、A が B に等しく、B が C に等しいことを検出する必要があるため、コストのかかるeq演算子を呼び出すことなく、A が C に等しいことを返す必要があります。

union-find アルゴリズムを使用したかったのですが、等式のキャッシュのみが許可され、不等式のキャッシュは許可されません。

互いに等しい 2 つのオブジェクト、A と B があるとします。また、等しいオブジェクトの別のペア、C と D があるとします。和集合検索アルゴリズムは、それらを 2 つのカテゴリ (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 の両方が高速化されます。

4

3 に答える 3

0

これは、O(k*n*eq_operation)k がセットの数であるアルゴリズムです。n セットで開始し、要素 v を取り、eq 演算子を使用して他の要素と比較します。要素 u が等しくない場合、アイテムを新しいセットに追加します。そうでない場合は、v と u の結合を見つけ、リストの最後まで続行します。要素が 1 つだけになるまで、新しいリストで同じことを行います。

擬似コード:-

set = all n
for i in set
parent[i] = i;

while set is not empty {

    i = set[0];
    newset = [];
    for j = 1 to set.size() {

        if(eq(i,set[j])) {

             parent[set[j]] = i;
        }         

        else {
               newset.add(set[j])
        }
    }

   set = newset

}

注:-O(n^2*eq_operation)セット数が少ない場合はブルート フォースと同じくらい良いセット数が多い場合O(n*eq_operation)

parent[i] ! = parent[j]この後、不等号を取得するかどうか、およびparent[i ] == parent[j]で等号を取得するかどうかを簡単に確認できますO(1)。

于 2013-12-11T17:11:04.997 に答える
0

これはあまりきれいな解決策ではありませんが、同等クラスのすべてのリーダー (つまり、Union Find 構造のルート) について、少なくとも (以下を参照) すべてのリーダーを含む二分探索木を保存するのはどうでしょうか。絶対に不平等。

クエリするにx ?= yは: いつものように、両方のリーダーを見つけて、それらが等しいかどうかを確認します。それらが等しくない場合は、他のリーダーの BST でリーダーの 1 つを見つけます。存在する場合、xとyは間違いなく等しくありません。

2 つの同等クラスxandを結合するには: それらのリーダーの BST をマージし、それをandyの結合の新しいリーダーの BST として設定します。BST の 1 つに入り、後で非リーダーになるノードは、BST から削除されることはありませんが、それは大きな問題ではありません。クエリが間違った結果を返すことはありません。スペースが無駄になるだけです (ただし、多くのことはありません)。 ）。xy

于 2013-12-11T18:00:55.133 に答える