ソフトウェアエンジニアを目指す人のブログ

ソフトウェアエンジニアになるために勉強したことを書いていきます

Disjoint Sets (Cousera Data Structure week3)

CouseraのData Strucureコースのweek3の内容です。
www.coursera.org

前回のweek3の内容の記事はこちら
rikeiin.hatenablog.com

Disjoint-set

Disjoint-setは以下の操作を持つデータ構造である

  • MakeSet(x):集合{x}を作る
  • Find(x):xを含む集合のIDを返す
    • もしxとyが同じ集合に属していればFind(x)==Find(y)
  • Union(x, y):xとyを含む2つの集合を結合する

単純な実装

  • 集合の最も小さい値の要素をその集合のIDとして使う
  • smallest[1...n]のような配列を使う
    • smallest[i]にiが所属する最小の要素の値を入れる

f:id:rikeiin:20180428215229p:plain
f:id:rikeiin:20180428215301p:plain
f:id:rikeiin:20180428215438p:plain

効率的な実装

  • 単純な実装のボトルネックはUnion操作である。
  • Linked listを使うことでより効率的な実装が可能。
    • 集合をLinked listで表し、listの末尾を集合のIDとして使う

f:id:rikeiin:20180428220453p:plain

f:id:rikeiin:20180428220528p:plain

  • メリット
    • Unionの実行時間がO(1)
  • デメリット
    • 末尾を探すためにリストを走査する必要があるため、Findの実行時間がO(1)
    • xのリストの末尾とyのリストの先頭を定数時間で取得できる場合のみUnionの実行時間はO(1)

木構造を用いたさらに効率的な実装

  • 集合を一つの木で表す
  • IDはその木構造のルート
  • parent[1...n]という配列を使う
    • parent[i]はiの親もしくはiがルートであるならばi自身

f:id:rikeiin:20180428223100p:plain
f:id:rikeiin:20180428223204p:plain

  • どのように2つの木をマージさせるか?
  • 片方の木をもう片方のルートノードの下にぶら下げる
    • 木を浅くしておくため、短い木をぶら下げる

f:id:rikeiin:20180428225415p:plain

  • 木の高さを素早く見つけるために各サブツリーの高さを配列rank[1...n]に保持しておく
    • rank[i]はルートがiであるサブツリーの高さを表す
  • 高い木の下に短い木をぶら下げることをunion by rank heuristicと呼ぶ

まとめ

union by rank heuristicを使うことでUnionとFindの実行時間がO(log n)になる

Path Compression

木の高さを短くする方法。例えば以下の図の例でFind(6)を実行する場合、ノード6からルートノードまで親を辿っていく必要があるが、その際12と3もルートノードも同時にわかるので以下の様に木を変形できる。

f:id:rikeiin:20180428232818p:plain

O(log n)の操作をn回繰り返すときの計算量をlog*nと定義する。
f:id:rikeiin:20180430161203p:plain

f:id:rikeiin:20180430161247p:plain

つまり一回の操作の時間計算量は漸近的にO(log*n)となり、実質的にlog*n < 5のときは定数時間とみなせる。

まとめ

  • 各集合を木構造で表現する
  • ルートノードをその集合のIDとする
  • Union by rank heuristic
    • 高い木のルートの下に短い木を吊り下げる
  • Path Compresion heuristic
    • ある特定のノードのルートを見つけるときに、走査したノードをルートの下に吊り下げる
  • 償却的時間計算量はO(log*n)
    • 現実的なnの値でほぼ定数時間