interprism's blog

インタープリズム株式会社の開発者ブログです。

Union Find Tree (前編)

この投稿は インタープリズムはAdvent Calendarを愛しています。世界中のだれよりも。 Advent Calendar 2017の20日目 の記事です。

まえがき

どうもこんにちは。k.u.です。
本日と明日の2日間にかけて、Union Find Treeの紹介をさせていただきます。

Union Find Treeは、互いに素な集合を効率的に扱うことの出来るデータ構造で、

  • 集合の併合
  • 同じ集合に入っているかどうかの判定

が、とても少ない計算量で出来ます。まぁ要するにグループ分けが効率良く出来るという代物です。

しかし、集合を木構造で扱うため、グラフ理論をかじっていない場合には少々勝手が難しいかと思います。 私の文章により、アルゴリズムやデータ構造に少しでも興味を持っていただけると幸いです。

というわけで早速、Union Find Treeにまつわる物語を紹介いたします。 最後までお付き合いいただけると幸いです。







Union Find Tree (前編)

これは大きな大きな森の中の、小さな小さな動物たちのお話。

プロローグ ー森の始まりー

この森の中では様々な動物が暮らしています。彼らは遊ぶ時も食料を得る時も、1匹1匹独立して動いています。 うさぎもこの森の住人の1羽で、働くときも、食事をするときも、勉強をするときも1羽で行っていました。

f:id:interprism:20171218102410p:plain

ある時うさぎが、食料を得る仕事は自分1羽ではなく他の動物たちとも協力してこなせば効率がいいのではないかと気付き、 食料を得るための団体を結成することにしました。

これが後のインタープリズムと言われています。

この協力をきっかけに、森では様々な動物たちが団体を結成し、協力して食料を得るようになっていきました。

どうやら動物たちそれぞれは、1匹が複数の団体に属するということはしないようですね。

こうして森の動物たちは、効率的な暮らしを手に入れました。

第1章 ー森の動物たちと旅人ー

ある日、森に旅人がやってきました。

旅人は森の動物たちに以下の質問をしました。

「ねこといぬは同じ団体かい?」

団体を組んで協力していた森の動物たちですが、団体の情報をまともに管理していなかったため、この質問にただちに答えられません。
さて、この質問に答えるためにはどうすればよいでしょうか。

増えすぎた協力体制を整理するため、動物たちはそれぞれ団体の中に上司を1匹決めることにしました。
ここで、団体の中で1匹だけ、上司のいない一番偉い動物を決めておきます。
そのような動物は、いわばその団体の代表です。

f:id:interprism:20171218100906p:plain

あまり記憶力が良くない動物たちなので、上司の名前を1匹だけ覚えておけばいいというのは楽でいいですね。
ちなみにこの時の各団体は、木構造(特に、団体の代表を根とする根付き木の構造)をなしていて、動物全体で森をなしています。

ここで、2匹の動物が同じ団体に属していることと、その2匹の動物の所属する団体の代表は同じ動物であることは必要十分条件になっていることに気をつけましょう。 *1 もちろん片方の動物が団体の代表だとしても、これは成り立ちます。

このように決めると、どうすれば旅人の質問に答えられるでしょうか。

ねこといぬが同じ団体に属しているかどうかは、

  • ねこの所属する団体(以下、チームねこと呼びます。)の代表
  • いぬの所属する団体(以下、チームいぬ *2 と呼びます。)の代表

の、2匹の動物が同じ動物かどうかを調べれば分かりますね。

まず、チームねこの代表を調べます。ねこの上司はねこに聞いてみないと分からないですが、 チームねこの代表は自分か自分より偉いはずなので、

  • ねこの上司がねこ自身ならば、チームねこの代表はねこである。
  • ねこの上司がねこ自身でないならば、チームねこの代表は、ねこの上司の代表である。更にねこの上司は、ねこよりも代表に近い位置にいる。

ということが分かります。

ということは、チームねこの代表を知るには、
ねこの上司を聞き、
ねこの上司の上司を聞き、
ねこの上司の上司の上司を聞き・・・
という風に、上司を聞く質問をチームねこの代表が見つかるまで繰り返せば分かります。

上の図の場合は、以下の手順になります。

  1. ねこの上司を聞き、うさぎだと分かる。
  2. うさぎの上司を聞き、うさぎが代表だと分かる。

同じように、チームいぬの代表についても調べて、代表が同一動物かどうかを調べれば解決しますね。

このようにして、動物たちは旅人の質問に答えることが出来ました。めでたしめでたし。

第2章 ー動物たちの願いー

団体に属したいという動物が、続々と現れています。

2匹1組で、それぞれの組について動物たちが同じ団体になりたいと思っています。
また、動物たちは一度団体を組んだら、その団体を離れたくないようです。
そのため、2匹の動物が同じ団体になるならば、どちらかの動物が団体を移籍するのではなく、その2匹が所属する団体ごと統合して、1つの団体になりたいという意思のようです。
1匹の動物が複数の団体に属さなかった理由が分かりましたね。

彼らの願いを叶えていきましょう。

最初に、パンダとライオンについて処理を行います。

ここで、動物たちが団体の中で決めている上司は1匹だけだったことに注意しましょう。

仮にパンダがライオンの上司としようと思うと、今までライオンに上司がいた場合に、上司が2匹になってしまいます。
そのため、2つの団体の今までの構造を上手く変更して1つにする必要があります。

どうやら、実際に上司が存在していて、キリンが上司のようですね。f:id:interprism:20171219100146p:plain

ここで、団体には代表の立場の動物が、ただ1匹だけ存在するということを思い出しましょう。
団体が2つということは代表も2匹存在していて、1団体に統合するということは代表が1匹になるということです。
というわけで、団体の代表同士が上司部下の関係を持つようにすれば、不都合無く団体が統合されることになります。
仮にパンダとライオンが実は最初から同じ団体に属していたという場合でも、団体の代表を見つける過程で同じ代表が見つかり、 元々同じ団体に属していたということに気付くことが出来るので、必要以上の上司部下の関係が生まれることも無いですね。

f:id:interprism:20171219101012p:plain

このパンダとライオンの団体統合方法を順番に適用することで、同じ団体に属したいという動物たちの願いを無事に叶えることが出来ました。





と、長くなってしまったので今日はここまで。

Union Findのアルゴリズムについて、素集合森で集合を表し、第1章ではfind、第2章ではunionの方法を紹介いたしました。
しかしUnion Find Treeの高速化手法をまだ取り入れていないので、動物たちの数が多くなると、unionもfindも時間がかかってしまいます。
動物たちはどうなってしまうのでしょうか。

続きはまた明日。お楽しみに。

storyteller : k.u.
illustration : irasutoya

インタープリズムのページ

*1:このことから、2匹の動物が同じ団体に属しているかどうかを調べるためには、2匹の動物の所属する団体の代表は同じ動物であるであるかどうかを調べればよいということが分かります。

*2:もちろんチームねことチームいぬが同一の団体を指している可能性もあります。

PAGE TOP