Hatena::Grouptopcoder

(iwi) { 反省します

TopCoder: [[iwi]] / Twitter: @iwiwi

 | 

2013-12-26

"データ構造をマージする一般的なテク" とは?

21:48 |  "データ構造をマージする一般的なテク" とは? - (iwi) { 反省します を含むブックマーク はてなブックマーク -  "データ構造をマージする一般的なテク" とは? - (iwi) { 反省します  "データ構造をマージする一般的なテク" とは? - (iwi) { 反省します のブックマークコメント

"データ構造をマージする一般的なテク" という言葉がじわじわとプログラミングコンテスト界隈に広まっている感じがします.「聞いたことがある表現だなあ」と思っていたらどうやら僕がそう呼んだせいらしい(ソース1, ソース2).

皆 Building 2 なんてマニアック気味な問題の解説をよく読んでいるなあと思います.難しめの問題の細部ということでスライドでは端折り気味になっており申し訳ないなあと思いますので,改めてこっそり解説をしておきます.


Union-Find での例

Union-Find のデータ構造といえば以下をサポートするものです.

  • void init(n) --- 0, 1, ..., n-1 というアイテムがバラバラのグループに入っている状態で初期化
  • void merge(a, b) --- アイテム a と b が入っている 2 つのグループを 1 つのグループにまとめる
  • bool is_same_group(a, b) --- アイテム a と b が同じグループに入っているか否かを答える

親を覚えてツリーを作ってグループを表現する手法をご存知だと思います.(あの計算量にアッカーマン関数の逆関数が出てくるやつです.ご存じなければこのスライドをどうぞ.)

しかし,以下ではそれとは違うアプローチでこれを効率的に実現します.(ちなみにその親を覚える手法は,以下の手法と区別するときは Quick Union などと呼ばれるようです.)


Quick Find アルゴリズム

以下のプログラムは Union-Find のデータ構造を何も知らない人に「これらの機能を実現して」と言った時にそこそこ書かれる可能性のある感じのものじゃないかと思います.

  • 各グループ g に所属するアイテムを vector<vector<int>> で全部普通に持つ(変数 g2i)
  • アイテム i が今どのグループに所属しているかをやはり普通に vector<int> で覚えておく(変数 i2g)
  • merge は普通に片方のグループをもう片方のグループに移動させるだけ
  • is_same_group は配列 i2g を見るだけ
vector<int> i2g;          // i2g[i] := アイテム i の所属するグループの番号
vector<vector<int>> g2i;  // g2i[g] := グループ g に所属するアイテムたち

void init(int n) {
  i2g.resize(n);
  g2i.resize(n);
  for (int i = 0; i < n; ++i) {
    // 最初はアイテム i はグループ i に所属
    i2g[i] = i;
    g2i[i].assign(1, i);
  }
}

// アイテム ia の所属するグループとアイテム ib の所属するグループを 1 つにする
// (ia と ib は違うグループに所属するものとする)
void merge(int ia, int ib) {
  int ga = i2g[ia], gb = i2g[ib];
  // グループ gb に所属する全てのアイテムをグループ ga に移す
  for (int j : g2i[gb]) i2g[j] = ga;
  g2i[ga].insert(g2i[ga].end(), g2i[gb].begin(), g2i[gb].end());
  g2i[gb].clear();
}

// アイテム ia とアイテム ib は同じグループに所属しているか?
bool is_same_group(int ia, int ib) {
  return i2g[ia] == i2g[ib];
}

残念ながら,お気づきの通り,偏って merge されまくると merge に毎回 Θ(n) 時間かかり計算量が全体で Θ(n^2) になってしまいお話にならない感じです.

ちなみに,一応,こいつには Quick Find アルゴリズムという名前がついているっぽいです.まあ確かに関数 is_same_group は O(1) 時間なので Quick という名を冠していることを辛うじて許してやろうか.


Quick Find Weighted アルゴリズム

しかし,なんと実は,上のアプローチは以下のように merge にほんの少し手を加えるだけで一気に優等生になります.

void merge(int ia, int ib) {
  // ia の所属するグループが ib の所属するグループより小さくならないようにする
  if (g2i[i2g[ia]].size() < g2i[i2g[ib]].size()) {
    swap(ia, ib);
  }

  // あとはさっきと同じ
  int ga = i2g[ia], gb = i2g[ib];
  for (int j : g2i[gb]) i2g[j] = ga;
  g2i[ga].insert(g2i[ga].end(), g2i[gb].begin(), g2i[gb].end());
  g2i[gb].clear();
}

merge をする時,グループの大小に気をつけ,大きいグループの方はそのままにして,小さいグループの方のアイテムだけを移動するようにする,それだけです.

一見,比較的自明な感じなので,ふつーの定数倍高速化かな?と思われるかもしれません.でも,実はこれは本質的な変化で,なんと merge の計算量は一気にならし O(log n) 時間になります.

ならし O(log n) 時間になるということは,ある視点に気づけば比較的簡単に理解できます.その視点とは,アイテム 1 つずつに注目して考えるということです.

  • 各アイテム i について,そいつのグループが変更される回数は O(log n) 回.
    • それはなぜかというと,グループが変更されるたびに,自分が所属するグループの大きさが 2 倍になるから.
      • つまり,最初はサイズ 1 のグループに居るけど,最初の移動後は少なくともサイズ 2,その次は少なくともサイズ 4,その次は少なくともサイズ 8……というように,自分の所属するグループは少なくとも 2 の指数で大きくなっていく.
      • なぜなら,自分がグループの移動をする時は,自分より大きいグループへマージされているから.
    • なので,全体で n 個しかアイテムがなければ,log_2 n 回以下しかグループの移動はありえない.
  • よって,n 個のアイテムが関わっている時,全体での計算量は O(n log n) で抑えられる.

というわけで実は,merge がならし O(log n) 時間で is_same_group が O(1) 時間というまともに使い物になる Union-Find のデータ構造が,こうやっても作れるんですね.これは Quick Find Weighted などと呼ばれるそうです.

(ちなみに,Quick Union に比べて is_same_group はこっちのほうが高速なので,こっちのほうが有利なシチュエーションというのもあるはずです.)


データ構造をマージする一般的なテク

この,大きさに気をつけて小さい方を大きい方にくっつけるという考え方を応用することで,色々な普通のデータ構造にマージ機能を追加することができます.

例えば,std::set<int> がいっぱいあって,全体では n 個の int が記憶されてるとして,これらをがんがんマージしていくという処理をしたい気持ちになったとしましょう.std::set には効率的なマージ機能は用意されていませんが,実は以下のように書くだけでマージ部分の全体の計算量は O(n log^2 n) 時間で抑えられます.さっきと同じく,大きい方に小さい方の中身を全部挿入するだけ.

// a, b をマージする.a に全要素が入り,b が空になる.
void merge_set(set<int> *&a, set<int> *&b) {
  // b のほうが a よりサイズが小さいようにして
  if (a->size() < b->size()) swap(a, b);
  // a に b の中身を全部入れるだけ
  a->insert(b->begin(), b->end());
  b->clear();
}

これは,挿入がサポートされているデータ構造なら何でもできます.一般的だ!*1 挿入が O(ほげ) のデータ構造なら,全体の計算量は O(n log n * ほげ) になります.


応用問題

他でも何度か使った気がするけれどすぐに思い出せるのはこれぐらいかなあ.ご存知なのあれば是非教えてください.


いろいろ
  • 順位キューでやりたかったら,併合もサポートする順位キューであるところの Leftist Heap や Skew Heap が普通にあります.普通に併合が(ならし) O(log n) でできます.
  • このスライドで言っている平衡二分探索木の merge とは違うことに気をつけてください.
    • スライドの merge は,主に列を表現するために木を使っていて,木 a と木 b を merge すると表現された列が連結される.
    • 今回の merge は,木なら,順序集合を表現するために使っていて,merge された木はやっぱり順序で並んでいる.
  • 挿入の回数は最悪 O(n log n) 回ですが,merge の操作がランダムと仮定すればなんと平均は O(n) 回であることも知られています.

*1:一般的というのはそういう意味であってこういう意味ではないw

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/iwiwi/20131226
 |