今まで ドキュメント修正のPRはいくつか取り込んでもらったことがあったけど、コードの変更は初めてだったので（※2021/06/27追記、結構前のことなのですっかり忘れていたけど他のOSSでマージしてもらったことがあったのでそんなことはなかったです。なんてことだ。。。）すごく嬉しかったです。
このPRを作るきっかけになったのは、標準ライブラリのsetをirbで利用しようとして以下のようにfalseが返ってくることでした。
$ irb > require 'set' -> false
みてみると、ls.rbで require 'set'されているからのようでした。
「標準ライブラリがユーザーの意図しないところで読み込んであるのは好ましくないかも」という思いからlsをみていて、まず最初に上記のPRに至った次第です。
まだそもそもの動機が達成できてないので、require 'set'しなくても動くようにする、という変更を次に出してみようかなと思っています。
GWあたりから 問題解決力を鍛える！アルゴリズムとデータ構造 | 書籍情報 | 株式会社 講談社サイエンティフィクをやっているいる最中で*1 ､全部で18章あるうちの11章の終わりまで来ました。
11章は「Union-Find」がテーマです。 他の章は「グラフ、うん、グラフ」「ソートって簡単そうにみんな言うけど私には難しんだよね」と言うふうに”データ構造やアルゴリズムという意味で理解はしてないが言葉くらいは知ってるよ！”というものがほとんど。
そんな中で「Union-Find...？ちょっと待ってなんでこれだけいきなり英語表記なん、まず名を名乗ってくださいあなたは何者ですか？」状態からの始まりで構えていたところ「何これ！！！*2楽しい！！！」となったので、気持ちを書いておきます。
Union-Findは"union"（まとめる）操作と"find"（みつける）操作をおこなうアルゴリズムです。
この操作対象となるデータ構造は素集合。素集合というのはAというグループとBというグループがあるとして、A、Bのもつ要素が互いに重複していないもののこと。「AとBは互いに素」という。...らしいよ。
素集合があったときに、データ構造としては1つのグループが1つの木になっています。「AとBは互いに素」だった場合Aが1つの木、Bはそれからは独立したまたまた別の木です。
その木構造を使って、"ある要素x, yが同じグループに属するか判定する", "要素xの属するグループと要素yの属するグループを合併する"操作がUnion-Findです。
"ある要素x, yが同じグループに属するか判定する" ためには、x、yの属する木の根を比較します。
x、yの属する木の根を見つけるための計算量は木の高さです。木の高さは最大で要素数-1が考えられるので、要素数をNとすると、計算量は O(N) となります。
"要素xの属するグループと要素yの属するグループを合併する"計算量は O(1)
このことからUnion-Find全体の計算量は O(N)と言えます。
同時に、木の根を早く見つけることができればこのO(N)を削減することができます。
要素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という芸人さんにハマっていて、わからないものがあったら「何これ！！！」って叫んでみるとなんかわかるようになれる不思議な力があって大変良いです
