Python の高度なアルゴリズムとデータ構造: コレクションの高速クエリとマージ

コード設計では、このようなシナリオによく直面します。2 つの要素が与えられた場合、それらが同じセットに属しているかどうかをすばやく判断する必要があります。同時に、必要に応じて、異なるセットを 1 つのセットにすばやくマージできます。たとえば、ソーシャル アプリケーションを開発する場合、ここで説明した関数を使用して、2 人のユーザーが友人であるかどうか、または同じグループに属しているかどうかを判断する必要があります。

これらの関数は単純に思えるかもしれませんが、難しいのは「十分に速く」処理することです。2 つの要素 a と b がそれぞれセット A と B に属しているとします。これらが同じセットに属しているかどうかを判断する直接的な方法は、セット A のすべての要素を走査して b が見つかるかどうかを確認することです。セット A に n 個の要素が含まれている場合、この方法の時間計算量は O(n) です。セットに多くの要素があり、判断の数も大きい場合、この方法は非常に非効率的になります。このセクションでは、サブ線形アルゴリズムが見つかるかどうかを確認します。

まず、複雑度が O(n) のアルゴリズム ロジックを見てみましょう。0 から 6 までの番号が付けられた 6 つの要素があるとします。キューを使用してセットをシミュレートできます。同じセットに属する要素は同じキューに格納され、次の図に示すように、各要素はハッシュ テーブルを通じてキューの先頭にマッピングされます。

このデータ構造では、2 つの要素が同じセットに属しているかどうかを確認するには、ハッシュ テーブルを通じてそれぞれの要素が配置されているキューの先頭を見つけ、先頭が一貫しているかどうかを判断するだけです。2 つの要素が同じセットに属しているかどうかを示すには、areDisjoint(x,y) を使用します。現在のデータ構造では、areDisjoint の時間計算量は O(1) です。

2 つの要素のセットを結合する場合は、merge(x,y) を使用して表現します。次に、現在の構造では、次の図に示すように、x と y に対応するキューの先頭を見つけ、x が配置されているキューの先頭から最後の要素までトラバースし、最後の要素の次のポインターを y が配置されているキューの先頭に移動するだけです。

同時に、2 番目のセットの各要素によってマップされるキュー ヘッドを変更する操作も実行する必要があります。したがって、現在の構造では、merge(x,y) の時間計算量は O(n) です。キュー ヘッドから末尾までのトラバースは O(n) であり、y が配置されているセットの各要素をトラバースして、それらがマップするキュー ヘッドを変更するのにも O(n) の時間計算量があるためです。

ここで問題となるのは、マージに必要な時間を最適化できるかどうかです。マージ時に時間のかかるステップが 2 つあることに気付きました。1 つはキューからキューの末尾まで移動すること、もう 1 つは 2 番目のセットの各要素が指すキューの先頭を変更することです。つまり、時間の消費は、コレクションを表すためにキューを使用するという事実によって実際に発生します。時間を最適化するために、次の図に示すように、キューをマルチブランチ ツリーに置き換えます。

この時点で、要素をキューの先頭にマッピングするためにハッシュ テーブルは使用しなくなりました。代わりに、同じセットの要素を同じマルチブランチ ツリーに挿入します。2 つの要素が同じセットに属しているかどうかを判断するには、ツリーのルート ノードが見つかるまで、要素の親ノード ポインターをたどるだけです。同じルート ノードが見つかった場合、2 つの要素は同じセットに属します。ソートされたバイナリ ツリーの場合、ツリーの高さは O(lg(n)) です (n はツリー内のノードの数)。したがって、2 つの要素が同じセットに属しているかどうかを判断するために必要な時間の計算量は O(lg(n)) です。

2 セットの要素をマージする必要がある場合、2 つの要素ペアのルート ノードをそれぞれ見つけ、高さが低いツリーのルート ノードを、高さが高いツリーの子ノードとして使用します。このプロセスは効率性にとって非常に重要です。これについては後でさらに詳しく説明します。ツリーのマージの状況を次の図に示します。

コードの実装を見てみましょう:

 # これはサンプルの Python スクリプトです。 
 
 # ⌃Rを押すと 実行するか 自分のコードに置き換えてください。
 # ⇧を2 回押すと、クラス、ファイル、ツール ウィンドウ、アクション、設定など、あらゆる場所を検索できます。 
 
クラス要素:
    def __init__(self, val: int ):
        自己.val = val
        self.parent = self #要素は作成されると別のコレクションを形成するため、親ノードはそれ自身を指します
    定義値(自己):
 self.valを返す
    親(自分)を定義します。
自己.親を返す
    def set_parent(自分自身、親):
        親が主張する なしではない
        自己.親 = 親
 
クラスDisjointSet:
    __init__(self)を定義します。
        自己.hash_map = {}
    def add (self, elem : 要素):
        要素が なしではない
        self.hash_map内のelem.value() の場合:
戻る 間違い 
        self.hash_map[elem.value()] = elem
戻る 真実 
    def find_partition(self, elem: 要素):
        #要素が配置されているコレクションのルートノードを返します
        要素が  self.hash_map内のNoneまたはelem.value()ではない
        親 = 要素.parent()
        if parent != elem: #ルートノードを再帰的に検索します。ツリーの高さは lg(n) なので、ここでの検索の時間計算量は lg(n) です。
            親 = self.find_partition(親)
親を返す
 
    def are_disjoint(self, elem1: 要素, elem2: 要素):
        # 2 つの要素が同じセットに属しているかどうかを判断するには、ハッシュ テーブルでそれらがマップされるルート ノードが同じかどうかを判断するだけです。
        ルート1 = 自己.パーティション検索(要素1)
        root2 = self.find_partition(要素2)
ルート1を返す ルートではない2 
 
    def merge(self, elem1: 要素, elem2: 要素):
        ルート1 = 自己.パーティション検索(要素1)
        root2 = self.find_partition(要素2)
        root1がroot2の場合:
            #2つの要素が同じセットに属している
戻る 間違い 
        ルート2.setParent(ルート1)
        self.hash_map[root2.value()] = root1 #root2に対応する親ノードを設定します
 
 #スクリプトを実行するには、ガターの緑色のボタンを押します。
 __name__ == '__main__'の場合: 
 
 # PyCharm のヘルプについては、 https://www.jetbrains.com/help/pycharm/を参照してください。

コレクションの表現をキューからマルチツリーに変更したため、コレクションの検索とマージの対応する複雑さは O(lg(n)) です。ここで問題となるのは、効率をさらに向上できるかどうかです。現在のマージ関数は、親ポインタを経由してルートノードまで登らなければならないため、時間がかかります。親ポインタがルートノードを直接指すようにできれば、登る時間のオーバーヘッドを節約できるのではないでしょうか。次の図に示すように、下位ノードの親ポインタがルートノードを直接指すこの方法は、パス圧縮と呼ばれます。

上の図から、ノード 6 と 8 の親ノードは元々 9 であり、それが属するセットのルート ノードは 1 であることがわかります。したがって、元々 9 を指していたポインターをルート ノード 1 に直接ポイントすることで、将来セットをマージまたはクエリするときに上へ登る時間コストを節約できます。もう 1 つの問題は、上記のコードで 2 つのツリーをマージすることです。root2 の親ポインターを root1 にポイントするだけです。これにより、マージされたツリーのバランスが崩れます。つまり、マージ後の左と右のサブツリーの高さが大きく異なる可能性があり、次の図に示すように、これも効率に悪影響を及ぼします。

右下隅をマージした後、左右のサブツリーの高さの差が大きいため、ノード 6、8 がルート ノード 0 を見つけるのにかかる時間は、2、3、4 よりも長くなっていることがわかります。ただし、右上隅が形成されると、リーフ ノード 6、8 と 2、3、4 がルート ノードを見つけるのにかかる時間はほぼ同じになり、効率が向上します。したがって、ツリーの高さも記録する必要があります。マージするときは、高さの低いツリーを高さの高いツリーにマージする必要があります。したがって、コードは次のように変更されます。

クラス要素:
    def __init__(self, val: int ):
        自己.val = val
        self.parent = self #要素は作成されると別のコレクションを形成するため、親ノードはそれ自身を指します
        self.rank = 1 # 木の高さを示します
    定義値(自己):
 self.valを返す
    親(自分)を定義します。
自己.親を返す
    def set_parent(自分自身、親):
        親が主張する なしではない
        自己.親 = 親
    get_rank(self)を定義します。
自己ランクを返す
    def set_rank(自己、ランク):
        ランク > 1 を主張する
        自己ランク = ランク

次にfind_partitionアプローチを修正する必要があります

def find_partition(self, elem: 要素):
    #要素が配置されているコレクションのルートノードを返します
    要素が  self.hash_map内のNoneまたはelem.value()ではない
    親 = 要素.parent()
    親がelemの場合: #すでにルートノード
要素を返す
    parent = self.find_partition(elem) #コレクションのルートノードを取得します
    elem.set_parent(parent) #パス圧縮はルートノードを直接指します
return parent #ルートノードを返す

find_partion の実装には再帰的なプロセスがあることに注意してください。現在のノードがルート ノードでない場合は、ルート ノードが再帰的に照会され、現在のノードの親ポインタが直接ルート ノードを指します。この変更に必要な時間計算量は元の lg(n) と同じであることがわかります。

次に、マージの実装を変更する必要があります。

 def merge(self, elem1: 要素, elem2: 要素):
        ルート1 = 自己.パーティション検索(要素1)
        root2 = self.find_partition(要素2)
        root1がroot2 の場合: # 2 つの要素は同じセットに属します
戻る 間違い 
        新しいランク = root1.get_rank() + root2.get_rank()
        if root1.get_rank() >= root2.get_rank(): # ツリーの高さに基づいてマージ方向を決定します
            ルート2.set_parent(ルート1)
            root1.set_rank(新しいランク)
それ以外：
            ルート1.set_parent(ルート2)
            root2.set_rank(新しいランク)
戻る 真実 

この改善後、find_partion と merge の m 回の呼び出しに必要な時間は O(m) です。つまり、改善後、find_partion と merge が多数回呼び出された場合、これらの呼び出しの平均時間は O(1) に短縮されます。つまり、パス圧縮後、大量の検索セット操作とマージセット操作を呼び出す際の効率が大幅に向上します。対応する数学的証明は非常に詳細なので、今は無視します。ここでの効率向上は実感できないかもしれませんが、考えてみてください。WeChatでは、2人が同じグループに属しているかどうかを判断するための通話が1日に少なくとも数千万回、場合によっては数億回行われるため、ここでの改善によりサーバーの処理効率が大幅に向上します。

完全なコードはここにあります

https://github.com/wycl16514/python_disjoint_set.git