2

重複の可能性:
Python: 交差に基づく単純なリストのマージ

オブジェクトを分類しようとしています。各オブジェクトは、 と呼ばれる一意の識別子プロパティによって識別されますid。したがって、私の分類ロジックは次のようになります。最初にオブジェクトのリストを準備すると、分類関数は一度に 2 つのオブジェクトを取得し、frozensetそれらを含む を返しますid。したがって、object1とobject5が同じカテゴリにある場合、 afrozenset(id1,id5)が返されます。今、私はこれらのフリーズセットをセットに追加し続けているので、最終的にはこのようなセットがあります

matched_set=(
             frozenset(id1,id2),
             frozenset(id9,id3),
             frozenset(id9,id2),
             frozenset(id24,id22),
             frozenset(id1,id23),
             frozenset(id25,id24),
             frozenset(id30,id24)
            )

と のオブジェクトは同じカテゴリにあり、 と のオブジェクトは同じカテゴリにあり、 と のオブジェクトは同じid1カテゴリにあるため、 のオブジェクトは同じカテゴリにある必要があります。だから私はこのようなセットを持っている必要があり ます誰かがそうするためのアルゴリズムを提供できますか? ありがとうid2id9id3id9id2id1,id2,id3,id9set(id1,id2,id3,id9)

4

1 に答える 1

6

disjoint-set datastructureを探しているようです。

ID のセットを指定すると、カテゴリはそれらを互いに素なサブセットに分けます。素集合のデータ構造は、代表 ID を選択することで各カテゴリを表します。代表 ID は、そのメンバーのいずれかのクエリによって返されます。(ID のフォームを 1 つのカテゴリごとに分離し、それ自体を返します)

ばらばらなセットのデータ構造を更新すると、任意の 2 つの ID のカテゴリが結合されるため、将来のクエリでは両方のサブセットのメンバーに対して同じ代表が返されます。(2 つの ID が既に同じカテゴリのメンバーである場合、更新は機能的にノーオペレーションです)

通常の方法は、各カテゴリを逆ツリーとして表すことです。各 ID にはparentリンクがありますが、子リンクはありません。「代表要素」はツリーのルートであり、親リンクをたどることで簡単に照会できます。更新には、両方の ID のツリーのルートを見つけ、(それらが異なる場合は) 一方のルートを他方の親にすることによってツリーをマージする必要があります。

いくつかの単純な最適化 (クエリはクエリ パスを「折りたたんで」ルートを直接指すようにし、更新は常に最も深いツリーのルートをマージの親として選択する) を追加することで、このアルゴリズムは非常に効率的になり、「ほとんど -O」で実行されます。 (1)"償却時間。

各カテゴリの ID の完全なリストへのオンライン アクセスが必要な場合は、各カテゴリ ルートにアタッチされた累積リストを維持し、各マージでそれらを連結する必要があります。一般に、この方法でカテゴリに関する任意の数の統計を維持すると便利です。

于 2012-08-21T22:01:49.590 に答える