いいものをつくろう

CTOの日記

アルゴリズム

union find

更新日:

こんにちは

PythonでのUnion-Find(素集合データ構造)の実装と使い方を参考にして

union findの使い方をみていきます。

アリ本にもでてくるデータ構造です。

上記リンクでの実装でのポイントはparentsで

親(parents)に各要素の親番号(親要素へのindex)を格納する要素自身が親つまりは根元の場合は、そのグループの要素数をマイナスで持つ

とうポイントを押さえれば、あとの理解は付いてくるはずです。

 

ここで少しバックグラウンドを話しましょう。

union findの祖先は

quick findです。coursera でプリンストン大学の動画はこちら

が、unionにO(N)で、実際グラフ形成にO(N^2)でquadratic(2乗)かかって 、データ大きいとだめだ

ってことで

union findです。っと行きたいところですが、まずはその前身、quick-unionを見ましょう。

union findっていうのも理解するには見ておいて損はないです。(coursera union find動画

quick-unionはunionが速いので、すごい良さげやん!って思うんですがworseケースを考えるとまだquadraticなんですねー。

worseケースっていうのは、findのときに高〜い、一直線の木です。

そこで!

工夫をしたのが、やっときました。そうunion findです。

union-quickで、木が高いとworseになるということだったので、木を構成していくとき

つまりはunion時に木が高くならないような工夫をしましょう!というのが肝です

それをするためにはグループのノード数の数を保存しておけばいいんです

あと、もう一個の工夫、これも高さを出さないための、木を低く保つための工夫で

findの速さにつながることですね。これは経路圧縮(path compression)というもので

やはりこの動画が非常にわかりやすいです。さらに経路圧縮でさらにかなり、速くなります。

log*N(ログNスター)というか速さ、でリニア(O(N))に近い速さだそうです。

 

親(parents)に各要素の親番号(親要素へのindex)を格納する要素自身が親つまりは根元の場合は、そのグループの要素数をマイナスで持つ

 

実装

class unionfind():
    def __init__(self, n):
        self.n = n
        self.pars = [-1] * n # 親のindexか、自信が親の場合は-(要素数)

    def find(self, x):
        if self.pars[x] < 0:
            return x
        else:
            # 親が根元ではないので、根元を探す旅
            oya = self.pars[x]
            # #これが経路圧縮。なくてもうごくよ。有ると速い。
            # self.pars[x] = self.find[oya]; return self.pars[x]
            return self.find(oya)

    def union(self, x, y):
        X = self.find(x) # Xはxの親である
        Y = self.find(y)
        if X == Y: return

        # 親のマージ。親のグループの小さい方に、大き方を足したいので。
        if self.pars[X] > self.pars[Y]:
            X, Y = Y, X

        self.pars[X] += self.pars[Y]
        self.pars[Y] = X

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.