ねこものがたり

いちにちいっぽ

「Union-Find完全に理解した」と言いたいので理解度を言葉にしてみる

これはなんの話?

GWあたりから 問題解決力を鍛える!アルゴリズムとデータ構造 | 書籍情報 | 株式会社 講談社サイエンティフィクをやっているいる最中で*1 、全部で18章あるうちの11章の終わりまで来ました。

11章は「Union-Find」がテーマです。 他の章は「グラフ、うん、グラフ」「ソートって簡単そうにみんな言うけど私には難しんだよね」と言うふうに”データ構造やアルゴリズムという意味で理解はしてないが言葉くらいは知ってるよ!”というものがほとんど。

そんな中で「Union-Find...?ちょっと待ってなんでこれだけいきなり英語表記なん、まず名を名乗ってくださいあなたは何者ですか?」状態からの始まりで構えていたところ「何これ!!!*2楽しい!!!」となったので、気持ちを書いておきます。

Union-Find とは?

Union-Findは"union"(まとめる)操作と"find"(みつける)操作をおこなうアルゴリズムです。

この操作対象となるデータ構造は素集合。素集合というのはAというグループとBというグループがあるとして、A、Bのもつ要素が互いに重複していないもののこと。「AとBは互いに素」という。...らしいよ。

素集合があったときに、データ構造としては1つのグループが1つの木になっています。「AとBは互いに素」だった場合Aが1つの木、Bはそれからは独立したまたまた別の木です。

その木構造を使って、"ある要素x, yが同じグループに属するか判定する", "要素xの属するグループと要素yの属するグループを合併する"操作がUnion-Findです。

Union-Findの計算量

"ある要素x, yが同じグループに属するか判定する" ためには、x、yの属する木の根を比較します。 x、yの属する木の根を見つけるための計算量は木の高さです。木の高さは最大で要素数-1が考えられるので、要素数をNとすると、計算量は O(N) となります。

"要素xの属するグループと要素yの属するグループを合併する"計算量は O(1)

このことからUnion-Find全体の計算量は O(N)と言えます。 同時に、木の根を早く見つけることができればこのO(N)を削減することができます。

計算量を小さくする工夫

union by size

要素x, yがそれぞれ木X, Yに属しているとき、XをYに組み込むか、YをXに組み込むかの2択があります。この時に「要素数の大きい方に小さい方を組み込む」のがunion by sizeです。大きな方に小さい方を組み込むと、全体の木の高さが変わりません。複数回処理を繰り返すとしても計算量は、もともと複数木があったうちもっとも高さのある木に必要な計算量が基準となります。逆をしてしまうと処理を繰り返すほど木がどんどん膨らんでしまうことになります。

経路短縮

頂点xから根にたどり着くまでの間に頂点が3つあるとして、通常であればxから根にたどり着くまで「x -> x-1 -> x-2 -> x-3 -> root」と5個の頂点に対して根かどうか判定する処理が必要です。 しかしその時に「頂点x(x-1, x-2, x-3)のある木の根はroot」と覚えておけば、その次以降の操作ではxから根に行くためには1回の計算ですみます。このように覚えておくことで根までの算出を短くするのが経路短縮です。

今後ブログに図を挿入していきたい

このエントリーを書くにあたって、本では文章で説明されていたことを手元で図にしながら理解したのでここでも図示することで自分の理解度を測りたかったのですが、木構造を思ったように作図するツールを自分が使ったことがありませんでした。

普段何かを作図する時にはUML記法やMarmaid記法をよく使うんですが、いわゆる木構造となるとなんかちょっと違う...?(使いこなせてないだけかもしれません。)

なので Graphbiz*3 を落としてみました。残念ながらまだインストールしただけなので、一通り練習してみてから今後は図も載せられるような状態になっておこうと思います。

そういえばアルゴリズムの勉強が楽しい

アルゴリズムを勉強するようになってから、ペンとノートの消費が膨大に増えました。 何に使っているかというと、構造と処理を全部図にしてみています。こういう時フリクション最高。

大量に書いて行ってみて、以前から図や表にかけるほどわかっているかどうかというのは製品開発の文脈でも重要な自分の指針になっていましたが、以前よりもっと早い段階・ふわっとした話について、あるいはコードを読んでいて「これを自分は図にできるか?」という観点で考える頻度が増えたり、実際に図にかき落としてからコードを書いたりすることが増えたと思います。

また、「アルゴリズムをちゃんと勉強したい」と思った背景だった「物事を抽象化すること、問題を小さく分割すること、それに対して解決を目指して適切なアプローチを考えること」の力不足という課題に対しても、筋トレのようにじわじわ効果があるような気がしています。気がしているだけで気のせいかもしれませんが、でもやっぱり筋トレが体に変化があるのが楽しいと言われるように自分の中で変化を感じているのは事実なのできっとこれが効果と自分では思っています!

*1: https://neko314.hatenablog.com/entry/2021/05/05/134534 のエントリーでそのエントリーを書いた翌週にはこの本を1周できているだろうと過去の私が言っているようですが、1ヶ月経っても終わっていないという見積もりの外しっぷりですが、期日は自分に課さないという基本スタンスで物事を楽しくやっています

*2:2021年のR-1からZAZYという芸人さんにハマっていて、わからないものがあったら「何これ!!!」って叫んでみるとなんかわかるようになれる不思議な力があって大変良いです

*3: https://graphviz.readthedocs.io/en/stable/index.html

Nerima.rbを閉会しました

タイトルが全てだけど、もうちょっと詳しく認(したた)めてみましょう。

Nerima.rbとは

2019年にひっそり始めたRubyコミュニティーです。 めんどくさがりな私(練馬区民)が、終電とか気にしたくないので家から歩いて帰れる場所でmeet upしたいと思ったこと、「Rubyリファレンスマニュアル全部読んだらいいのでは、でも一人でやれる気がしない、よしみんなでやろう」と思ったことから始めました。

簡単な活動記録

2019/04/13(土) に初めて開催して以降、1 - 2ヶ月に1回くらいの頻度で全部で5回開催しました。

リファレンスマニュアルの中から「今回はStringクラスを」とか「次はKernelやろうぜ」などという感じで毎回やっていました。 会場は練馬区の公共施設の会議室を毎回借りていて、プロジェクターで誰かのPCを投影しながら、サンプルコードを実行してみたり「こうするとどうなるのかな?」と試してみたり、それをHackMDやesaにみんなで記録していったりする形でわいわいとやっていました。

また、2回目開催くらいのタイミングで、お世話になっている方にロゴも作っていただいて、「可愛いですねー」と愛でながら開催していたのも良い思い出。

f:id:neko314:20210606211816j:plain
Nerima.rbのロゴです

なぜ閉会にしたか

本当は会場予約も済んでいたので2020年の2月に第6回の開催を予定でした。 でも、ちょうどその頃に"新型コロナウィルス"という単語が毎日のようにきかれるようになり、「多分開催しても大丈夫だと思うんだけど、わざわざみんなに集まってもらって、何かあったら...」という不安が拭えなかったので、開催告知前に第6回の開催を保留することに決めました。

保留にした時は「 SARSと同じようなものだと言っている専門家もいる。とすると今後めちゃくちゃ流行しても2021年くらいには元に戻るのでは」と思ったので、「平穏が戻ったら次のNerima.rbを開催しよう」という気持ちでした。

しかしながらその後も、もはやいうまでもないですが、2021年6月現在も緊急事態宣言最中だったりして、全然落ち着きません。

そのような状況の中で、他のMeet Upのようにオンラインで開催することも選択肢としては頭にちらつきましたが、「オンラインでやりたいモチベーションが皆無」という自覚があったので、試みることすらしませんでした。

そうこうしている間に、自分が区外に越すことが決まったために、一旦区切りをつけることにしました。

閉会にあたって

esaはteamごと削除しました。データはエクスポートしてます。もし良い方法があったら誰でもアクセスできるところにこのデータを置いておこうと思ってますがまだやってません。 connpassは削除したり非公開にしたりできないみたいなのでそのままにしています。もし誰かが「新しいNerima.rbやりたい。connpass使いたい」と思ったら、必要に応じてお譲りします。(そんなことはあるのかな?)

最後に

不本意ながら5回しかできなかったけど毎回楽しくRubyについて学べてとても良かったです。 第1回目にStringクラスやった直後RubyKaigi2019があって、JeremyのKeynoteで「stringはfrozenにすると早くなる」というのが出てきた時に「あ、Nerima.rbでやったやつだ!」となって感動したりしましたw それ以外にも新い出会いが生まれたり思い出ができたりしてとても充実した時間になりました。拙い主催者でしたが、やって良かったなって思っています。

また、「Nerima.rb始めるんですよー」ってお話ししたら「いいですね!」とたくさんの方が喜んでくださいました。それは私にとって意外な反応だったのですが、すごく嬉しくて、実は結構「やりたいからやるけどやってみたら自己満になっちゃうのでは」というふうに緊張していた私が開催を楽しむように背中を押してくれる声となりました。そんなふうに見守ってくださった皆様、参加してくださった皆様、ツールスポンサーの制度で無償で利用させてくださったesaの方々や運営を支えてくださった皆様ありがとうございました。