Union Findアルゴリズムの様々な実装とパフォーマンス計測

CourseraにAlgorithms Part1という授業があり、これが非常に評判が良いので、会社で勉強会をしている。Week1にUnion Findというアルゴリズムが出てきて、その実装パターンがいくつかあった。それぞれ計算量が違うらしいのだけど、速度がどのように変化するか試したかったので、実装してパフォーマンス計測をしてみた。それぞれの実装の詳しい説明が知りたかったら、https://www.coursera.org/learn/algorithms-part1 を見ると良い。

Union Findとは何か

二つのノードを繋いでいき(Union)、あるノードとあるノードがつながっているか(Find or Connected)を判定するアルゴリズム。

例えば、union(1,6)、union(5,6)、union(2,7)、union(3,8)、union(4,9)、union(8,9)とすると以下のようになる。

この時、1と5はつながっている、0と7はつながっていないなどといったことを判定する。

以下の記事に説明が載っているので、こちらも参考になる。

Union Findを使えると何ができるか

例えば以下のことができたりする。

SNSで友達があった時に、ある人とある人が友達を辿っていくとつながっているかどうか調べる
電気回路があった時に、正しく電気が流れるかシミュレーション
水が上から下に流れる通路があるか調べる

実装パターン

集合を使った実装
ツリー構造を使った実装
ツリー構造をできる限りバランスするようにした実装
ツリー構造を辿る時に平坦化もしていく実装

これらの説明は http://www.slideshare.net/chokudai/union-find-49066733 にいい感じにまとまっているので省く。

集合を使った実装

配列を使い、同じ集合には同じ数字を与えていくパターン。実装は https://github.com/shibayu36/algorithms/blob/b678d6a5121e91202dd4eda64f564b06434a4b82/src/main/java/org/shibayu36/algorithms/QuickFindUF.java

union(p,q) は配列を全てなめて、pの数字だったらqの数字に置き換えるので、O(n)という計算量になる
connected(p, q)は、数字が同じならつながっているとするだけなので、O(1)という計算量

connectedは速いけど、unionは毎回配列の全要素をなめるので、感覚的にも遅そう。

ツリー構造を使った実装

今度はツリー構造にするパターン。実装は https://github.com/shibayu36/algorithms/blob/b678d6a5121e91202dd4eda64f564b06434a4b82/src/main/java/org/shibayu36/algorithms/QuickUnionUF.java

union(p,q)は両方のrootを探して、qのrootの数字をpに代入する。最悪の場合一直線のツリーになり、その時rootを探すのがO(n)なので、計算量もO(n)。
connected(p,q)は両方のrootを探して、rootの数字が一致していたら繋がっている。こちらもO(n)

配列全てをなめる必要はなくなったので、速くなっていそう。

ツリー構造をできる限りバランスするようにした実装

先程のツリー構造を考えると、ツリーの高さが少なければ高速になる。そこでツリー構造を使った実装を改良し、ツリー同士をmergeするときはサイズが小さい方のツリーを下につるすようにし、高さが増えにくくなるようにする。この実装は https://github.com/shibayu36/algorithms/blob/b678d6a5121e91202dd4eda64f564b06434a4b82/src/main/java/org/shibayu36/algorithms/WeightedQuickUnionUF.java

これをすると、高さがlog2(n)に比例するようになるらしい。そのためunionもconnectedも計算量はO(log(n))となる。

ツリー構造を辿る時に平坦化もしていく実装

上記をさらに改良し、connectedでツリー構造をたどるときに、ツリーをどんどん平坦化させていく実装。https://github.com/shibayu36/algorithms/blob/b678d6a5121e91202dd4eda64f564b06434a4b82/src/main/java/org/shibayu36/algorithms/WeightedQuickUnionWithPathCompressionUF.java

これをすると、計算量がlog*(n)になるらしい。log*(2^65536) = 5らしいので、大分はやい。

それぞれのパフォーマンスを取る

後述するベンチマークスクリプトを使ってベンチマークを取る。以下の処理をそれぞれの仕組みでベンチマークする。

10000ノードのUnion Findを行う
ランダムに10000回union、その後ランダムに10000回connectedをする

package org.shibayu36.algorithms;

import java.util.ArrayList;
import java.util.List;
import me.geso.nanobench.Benchmark;
import org.apache.commons.lang3.RandomUtils;

public class UnionFindBenchmark {

  public static void main(String[] args) throws Exception {
    new Benchmark(new UnionFindBenchmarkInner()).warmup(1).runByTime(1).timethese();
  }

  public static class UnionFindBenchmarkInner {
    private int size = 10000;
    private List<List<Integer>> unions = new ArrayList<>();
    private List<List<Integer>> connecteds = new ArrayList<>();

    // unionをするリストを作っておく
    {
      for (int i = 0; i < size; i++) {
        List<Integer> union = new ArrayList<>();
        union.add(RandomUtils.nextInt(0, size - 1));
        union.add(RandomUtils.nextInt(0, size - 1));
        unions.add(union);
      }
    }

    // connectedをするリストを作っておく
    {
      for (int i = 0; i < size; i++) {
        List<Integer> connected = new ArrayList<>();
        connected.add(RandomUtils.nextInt(0, size - 1));
        connected.add(RandomUtils.nextInt(0, size - 1));
        connecteds.add(connected);
      }
    }

    @Benchmark.Bench
    public void QuickFindUF() {
      QuickFindUF uf = new QuickFindUF(size);

      for (List<Integer> union : unions) {
        uf.union(union.get(0), union.get(1));
      }

      for (List<Integer> connected : connecteds) {
        uf.connected(connected.get(0), connected.get(1));
      }
    }

    @Benchmark.Bench
    public void QuickUnionUF() {
      QuickUnionUF uf = new QuickUnionUF(size);

      for (List<Integer> union : unions) {
        uf.union(union.get(0), union.get(1));
      }

      for (List<Integer> connected : connecteds) {
        uf.connected(connected.get(0), connected.get(1));
      }
    }

    @Benchmark.Bench
    public void WeightedQuickUnionUF() {
      WeightedQuickUnionUF uf = new WeightedQuickUnionUF(size);

      for (List<Integer> union : unions) {
        uf.union(union.get(0), union.get(1));
      }

      for (List<Integer> connected : connecteds) {
        uf.connected(connected.get(0), connected.get(1));
      }
    }

    @Benchmark.Bench
    public void WeightedQuickUnionWithPathCompressionUF() {
      WeightedQuickUnionWithPathCompressionUF uf = new WeightedQuickUnionWithPathCompressionUF(size);

      for (List<Integer> union : unions) {
        uf.union(union.get(0), union.get(1));
      }

      for (List<Integer> connected : connecteds) {
        uf.connected(connected.get(0), connected.get(1));
      }
    }
  }
}

結果は次のようになる。

Score:

QuickFindUF:  1 wallclock secs ( 1.07 usr +  0.01 sys =  1.08 CPU) @ 12.05/s (n=13)
QuickUnionUF:  1 wallclock secs ( 1.13 usr +  0.01 sys =  1.14 CPU) @ 31.50/s (n=36)
WeightedQuickUnionUF:  1 wallclock secs ( 1.03 usr +  0.03 sys =  1.06 CPU) @ 1452.27/s (n=1541)
WeightedQuickUnionWithPathCompressionUF:  1 wallclock secs ( 1.12 usr +  0.02 sys =  1.14 CPU) @ 1934.83/s (n=2199)

集合を使った実装 = 12.05/s
ツリー構造を使った実装 = 31.50/s
ツリー構造をできる限りバランスするようにした実装 = 1452.27/s
ツリー構造をできる限りバランスするようにした実装 = 1934.83/s

O(n)とO(log(n))の速度差が実感できる。これがアルゴリズムの力か。

まとめ

今回はCourseraのAlgorithms Part1のWeek1の授業を見て、実装ごとにUnion Findの速度がどのように変化するか試したかったので、簡単に実装してパフォーマンス検証をしてみた。改めてアルゴリズムの重要性を感じる。

$shibayu36->blog;

クラスター株式会社のソフトウェアエンジニアです。エンジニアリングや読書などについて書いています。