DevFestのLTでUnion Findってアルゴリズムが紹介されてたんだけど、これ設計途中で俺が検討したアルゴリズムをもっと汎用的にしたような感じっぽいなぁ。
どういうのを検討したかというと、各セルに双方向(環状)リストで接続できるようにポインタ2つ持たせて標準では両方自分自身を指させて、各セルは右と下のみを走査して同値なら環状リストを結合(マージ)する。双方向の環状リストなのでマージは2要素だけのポインタ操作で完結できる。
自分自身がルート要素であるかどうかだけどこかで管理した方が後の数え上げが楽かな。
そうすると、最終的に結合した全要素が繋がった環状リストが各所に出来上がるので、数え上げる。数え上げは非効率といえば非効率だけどリストにカウンタ持たせるより後から一度だけリスト辿って数え上げる方が良いと思う、多分。数え上げは1回だけだから。
で、マーキングフェイズも数え上げフェイズも容易に並列化できる。何故なら、マーキングは隣接するセルが複数スレッドで同時に処理されるケースだけ気にすればいいし、数え上げは異なるルートであれば処理は衝突しない。
というようなものを考えてみたけど明らかに無駄な努力なのでやらなかった。
今晩にでもコード書いてみようかな。Cygwinなんで並列化はしないけど。