この投稿は インタープリズムはAdvent Calendarを愛しています。世界中のだれよりも。 Advent Calendar 2017の21日目 の記事です。
まえがき
どうもこんにちは。k.u.です。
この記事は昨日の記事の後編です。
昨日の記事では、Union Findのアルゴリズムについて、素集合森で集合を表し、第１章でfind、第２章でunionの方法を紹介いたしました。
しかしUnion Find Treeの高速化手法をまだ取り入れていないので、動物たちの数が多くなるとunionもfindも時間がかかってしまう状態です。
さてさて森の動物たちは、どうなってしまうのでしょうか。
ー後編と聞いて、Cohen-Macaulayを思い出す貴方へー
「それはコーエンです。」
これは大きな大きな森の中の、小さな小さな動物たちのお話。
Union Find Tree (後編)
月日は経ち、続々と動物たちが団体に属しています。何かの団体に属している動物の数は現在匹を超えています。
大きい団体では、所属する動物の数も分からず、2匹の動物たちが同じ団体に属しているかどうかの判定も時間がかかってしまいます。
第１章での同じ団体に属しているかどうかの判定法を行っているようでは、上司を聞く質問回数が3000回を超えることも多くなっていて、動物を見つけて1回質問するまでが30秒で終わっても、2匹の動物についての同じ団体かどうかの判定に2日以上掛かる場合も出てきました。
人間でも1日掛かってしまっていては長く感じるのに、寿命の短い動物も多くいるこの森にとっては文字通り死活問題になっています。
そもそもは効率良く食料を得るための団体だったのに、その団体の管理のせいで動物たちは時間を取られてしまっています。
森の動物たちはどうなってしまうのでしょうか。
第３章 ー経験と勘ー
今もまた、たぬきときつねが同じ団体に属したがっているようです。
いつものようにたぬきが属する団体の代表を調べ、いつものようにきつねが属する団体の代表を調べます。
どうやらたぬきは今まで団体に属したことが無く、いわば自分が代表の1匹の団体でした。
一方きつねは、昔から団体に属していたため、何匹いるかは分かってないようですが相当多くの動物たちが所属する団体の一員のようです。
たぬきは、上司を覚えておかなくてよいことに気付き、代表になってみようと思い、きつねの所属する団体の代表、うさぎを部下に設定しようとしていました。
「ちょっと待った！」
と言わんばかりの形相で、経験豊富なきつねはたぬきを上司にはせず、部下にしたほうがいいという提案をしました。
大きな団体であれ、団体の管理のための形式的な代表です。初めて団体に属することになるたぬきでも、全く荷が重くない立場です。
きつねの言い分はこうです。
- たぬきを上司にすると、元々の団体のメンバー全員について代表を見つけるための質問回数が1回増えてしまう。
- たぬきを部下にすると、代表を見つけるための質問回数はたぬきが1回増えるだけで済む。
確かにその通りです。たぬきも納得して、たぬきはうさぎを上司に設定しました。
ここでたぬきが、なんとなくこの話を一般化してみました。
「団体に属する動物の数を比べて、少ない方の代表が多い方の代表を上司にすると効率が良い」
確かに、この規則に則って代表の統合を行えば、1匹ずつ N 団体を1つの団体に統合する場合でも統合後の質問回数は最悪ケースでも logN 回程度になります。
というわけで、たぬきが一般化したこの方法 *1 は、団体の統合のルールに加えられましたとさ。 *2 *3
あれ？自分が属している団体の動物数なんて動物たちは知らないですね。
計算して、団体の統合の際に必ず関わる代表に覚えておいてもらいましょう。
どうやら動物たちは、
「全ての動物が同時に上司へ "1 + 前回自分が部下から言われた数の合計の値(言われていないなら0)" を伝え続ける」
という方法によって、団体に属している動物数を調べたようです。皆さんだったらどう数えあげますか？
第４章 ー経路圧縮の魔法ー
ある日、魔法使いがやってきました。
代表を探す動物たちを見て、魔法使いは言いました。
「あなたたち、経路圧縮してしまいましょう。」
魔法使いの言葉の響きに少々おびえた森の動物たちですが、悪い魔法使いには見えないので、言うことを聞くことにしました。
魔法使いからの言葉は、以下の通りです。
「代表を見つける際に、質問した代表以外の動物全員について、上司を代表にしてしまいましょう。」
試しに、パンダが所属している団体の代表を見つけてみましょう。
パンダの所属している団体 ( 一部抜粋 ) は、以下のようになっています。
ここで、団体を見つける操作を行う際に、上司は誰かという質問をして、上司が存在していた(つまり、代表ではない)動物について、代表が見つかった後に、上司を代表に変えることにします。
元々団体の管理のために形式的に上司の設定をしていただけなので、動物たちにとっては上司が変わっても同じ団体に属しているならば同じ仲間です。
無事に上司の再設定を終えると、団体は以下の図のようになります。
団体内の多くの動物たちについて、上司をたどって代表まで行く際の質問回数が減りましたね。
第３章での団体の統合時の工夫と、この経路圧縮を合わせることによって、代表を見つけるための平均質問回数はどうなるでしょうか。
実はたとえ動物が 匹いても平均 4 回から 5 回程度の質問で代表が見つかるということが知られています。 *4
よって団体の管理もスムーズになった動物たちは、効率良く平和に暮らしましたとさ。
おしまい。
あとがき
というわけで、昨日今日の2日間に渡って、Union Find Tree ー動物たちの森ー を紹介しました。
森の動物たちは協力して、木構造をなすデータ構造を用いて union と find のクエリをこなし、また、2つの高速化手法を使いこなせるようになりましたね。
1つ注意していただきたいのは、関係の削除というのは Union Find Tree では対応していないという点です。 *5
皆さんも是非一度 Union Find Tree を書いてみてください。
お相手は、k.u.でした。
*1:プログラミングコンテスト界隈では、「データ構造をマージする一般的なテク」と呼ばれています。その名の通り、「大きいほうに小さいほうをくっつける」というテクニックは、色々な場面で活用することが出来ます。
*2:これにより、集合の要素数の取得という操作も可能になりました。
*3:実は最も効率が良い方法は、「団体の動物数」ではなく「代表を見つけるための最長の質問回数」です。たぬきはこうは思いつかなかったようですが、皆さんは覚えておきましょう。
*4:オーダーの関数は、アッカーマン関数の逆関数になっています。
*5:削除操作込みでの効率の良いデータ構造は、Link-Cut Tree を用いて実装することが出来ます。
