python - 多対多のデー​​タ構造

Question

多対多対応を表現および処理するのに適したデータ構造。
メッセージの 2 つの向かい合ったストリームのマッチングを処理する必要があります。一方のストリーム内のエンティティが他方のストリーム内の複数のエンティティと一致したり、その逆の場合があります。
挿入と検索は頻繁には行われませんが、エンティティがデータのドメイン (「含む」) に存在するかどうかの評価は非常に頻繁に行われます。
私は特に python に興味がありますが、それはどのプログラミング言語にも等しく当てはまると思います。
正しい方向へのポインタは大歓迎です。

Answer 1

a と b の 2 つのセットがあるとします。a の要素は b の要素にマップされ、その逆も同様です。

グラフのようなデータ構造 (隣接リスト) を使用できます

# this maps elements in a to elements in b (elements of a are the keys)
# each element of a maps to several elements of b (as a list)
a2b = {
       'a' : [1,2,3]
      }

# this maps elements in b to elements in a (elements of b are the keys)
# each element of bmaps to several elements of a (as a list)
b2a = {
        1 : ['a'],
        2 : ['a'],
        3 : ['a'],
      }

基本的にリストの辞書があります。'a' は左から右方向に 1,2,3 にマップされ、1,2,3 はすべて反対方向に 'a' にマップされます (この例では)。要素を任意の数の他の要素にマップでき、その逆も可能です。

ドメインを見つけるには、辞書のキーを使用できます。上記の例では、次のことができます。

>>> print 1 in b2a
True
>>> print 'a' in b2a
False

elemがドメイン内にあるかどうかを確認するには (次の例でelemは、セット b にある場合)、次のようにします。

elem in b2a

要素がセット内にあるかどうかを確認するのは非常に高速です。これはあなたが望んでいることです。