モテるアルゴリズム講座　第2回 Skip Graphでモテたい

2010年04月30日（金）17:25｜天方

天方です。

それでは、アルゴリズム講座第2回をはじめたいと思います。

おかげさまで、前回の講座では、公開後、たくさんの知り合いの方から声をかけていただきました。

やはりアルゴリズムがモテるということを実感した第1回講座でした。

さて、今日は、Google App Engine(GAE)で利用を検討したアルゴリズムについて紹介したいと思います。

GAEでは、プログラムをする際に、クラウドの特性を意識する必要があるのですが、それは、アルゴリズム、特に並列アルゴリズムの知識を生かすには非常によい環境ともいえます。

はっきりいいます。GAEでアルゴリズムができるとモテます。

この講座を通じて少しでも皆様にモテをおすそ分けできたらと思います。

さて、本日も前回と同様、アルゴリズムとデータ構造に着目しています。

GAEでは、データを格納するストレージとしてRDBMSを使う代わりにBigTableという分散Key-Value Storeを使っています。

この分散Key-Value Storeは、クラウド環境で性能をスケールさせるためには非常によいデータの格納方法なのですが、RDBMSのようなリレーションを使った機能がないという問題があります。

やはり性能をスケールさせることを中心に考えているからですが、その分、プログラマーの方が余裕をもって、しっかりマメにケアしてあげることが必要になってきます。余裕のあるマメな男がモテるのと同様です。

例えば、データは複数のコンピュータにまたがって保持されているため、RDBMSのようにソートなどを効率的に行うことができません。

ではどうするのかというと、事前にソートした結果を持っておき、ソート結果を使いたいときは、その結果のデータを見ればいいのです。GAEのDatastoreではそういったソート機能があります。

今回は、Datastoreのソート機能そのものではありませんが、そういった分散環境で使えるかもしれないSkip Graphというソートアリゴリズムについて紹介したいと思います。

Skip Graphを理解するには、そのより単純なバージョンであるSkip Listについて考えるとわかりやすいです。

SkipListのデータ構造は以下のようになっています。

Ｓｋｉｐ Listのデータ構造

ところで、この図を見て何かに似ていると思いませんか？

お気づきの方もいるでしょう。普通と急行がある電車の路線図に似ています。

Skip Listはまさに、この電車の乗り換えのアナロジーで考えられます。

電車でどこかに行きたいなら、まず急行などの途中の駅を飛ばす列車に乗り、近くの駅まで来たら普通列車に乗って目的の駅に行けば、停車時間が短縮でき早くつくのです。デートの約束の時間に遅れずにつくのもモテる男としては当然ですよね。

Skip Listの図の例だとlevel2のレベルで自分の移動したいノードの近くまで、リンクをたどり、近くまできたら次にlevel1におりてリンクをたどり、最後にlevel0で目的とするノードにたどり着けばいいということです。

電車と同じようにSkip Listでも、上のレベルのリンクを利用することで、高速に、ソート済みのデータを検索したり、項目を追加したりできます。

と、こんなアナロジーで、新入社員にSkipListの説明をしてあげたら、この先輩の説明はクールだなとモテまくります。

この図のSkip Listのデータ構造を数式で表すと

ソートする値の集合 $N$ とした場合、

$N={n_1,n_2,n_3,n_4,n_5,n_6}$

のように表現できます。

ここではデータ構造を説明するために $n$ は便宜上左から右に大きくなっていくものとします。

$n_x <= n_{x+1}$

Skip Listでは、例えば、以下のようなデータ構造で、この値を表現します。

この図では、各ソートする値 $n_i$ をノード、レベル $l$ として、右側へのリンクリストを $a_{R_{ln_i}}$ 、左側へのリンクリスト $a_{L_{ln_i}}$ があります。

リンクリストは、下からレベル0, 1, 2のようにレベルがあり、レベル0では、大小関係が維持されたまま、隣同士のノードで双方向にリンクされています。

レベルが上がるほど、途中のノードを飛ばしてリンクされています。

この状態で、Skip Listはソートがされている状態であると言えます。

もし、昇順にデータがほしいなら、左の端から、Level0のリンクをたどってノードを見ていけば、ソートされている結果が得られます。

つまり、このデータ構造を作ることができれば、ソートはされているということになります。

このデータ構造をどのように作るかはひとまず置いておいて、

ある値を検索する場合の方法について考えたいと思います。

この操作の計算量はノード数を $|N|$ とした場合、平均 $O(log_2|N|)$ です。

$log_2|N|=x$ というのは、別の表現をすると、 $x=2^{|N|}$ となります。

これは、ノード数と計算時間の対応関係を表で表すと次のようになります。

ノード数N	計算量
2	1
4	2
8	3
16	4
約1000	約10
約1000000	約20

つまり、ノード数が指数的に増加しても、検索にかかる計算量は比例しては増加しないということです。

では、次にSkip Graphについて説明したいと思います。

Skip Graphは、Skip Listの拡張版だといえます。

Skip Graphではレベル1以上のノード間のリンクの仕方が違います。

Skip Listでは、スキップされたノードはそのレベルではリンクを持たないのですが、Skip Graphでは、リンクを持つ場合があります。

例えば、下記のようなデータ構造になります。

Skip Graphでは、検索をする場合には、どのノードから初めてもいいことになります。

最初のノードが決まったら、Skip Listと同じように上位のレベルから下位のレベルに向かって探したいノードに向かって移動していきます。この計算量もやはり平均 $O(log_2|N|)$ です。

さて、いままでデータの検索の方法について扱ってきましたが、ではこのデータ構造をどのように作ればいいのでしょうか。

その方法について説明したいと思います。

まず、ノード間のリンクの仕方についてですが、ここでは、メンバーシップベクタ関数 $M(n)$ を使って確率的にリンクします。メンバーシップベクタ関数 $M(n)$ は、 $n$ によって決まる2進乱数列です。このM(n)の乱数列の長さは無限に続くのですが、Skip Graphで利用するのは長さ $log|N|$ までです。 $M(n)$ の生成方法には決まった方法がありますので、方法を考える必要があります。この $M(n)$ を各ノードについて計算しておきます。 $log_26$ ≒ $2.59$ なので、メンバーシップベクタの桁数は2桁か、3桁となります。図では2桁にしています。
さて、計算し終えたら、リンクします。リンクするルールは次の様にします。
1. まずレベル0では、すべてのノードにおいて、隣接するノードとリンクします。
2. 次にレベル1では、メンバーシップベクタの1桁目までが一致するノード同士で、順序関係を保ってにリンクします。
3. 次にレベル2では、メンバーシップベクタの2桁目までが一致するノード同士で、順序関係を保ってにリンクします。

これを一般化すると

レベルnでは、メンバーシップベクタのn桁目までが一致するノード同士で、順序関係を保ってにリンクします。

となります。

さて、最初にいっぺんにリンクを作る方法はわかりました。では、途中のノードを追加する場合はどうなるのでしょうか。

ご心配なく。そういったことも可能です。その場合の計算量も平均 $O(log_2|N|)$ です。

まず、自分が追加しようとしているノードの値に近いノードを探索します。
追加している値のノードか、もっとも近い値のノードを見つけたら、ソート順番が壊れないように、そのノードの隣にノードを追加します。このとき、レベル0では、左右のノードのリンクを、追加したノードにリンクします。
次にレベル1では、メンバーシップベクタの1桁目が一致しているノードを左右でそれぞれ探し、リンクしなおします。
レベル2では、レベル1でリンクしたノードを起点に、左のノードであれば、さらに左に、右のノードであれば、さらに右に、メンバーシップベクタの2桁目までが一致するノード同士でリンクしていきます。
最終的に、各レベルのノードが終端ノードになるか、リンクがされるまで続けます。（または、ノード数がわかっているなら、 $log_2|N|$ の値からレベル数を求めて、そのレベルまで続けます）

以上が、ノードの追加方法となります。

SkipGraphが並列アルゴリズムとして有利な点はノードを検索や追加する場合に、どのノードを基点にしても平均計算量は $O(log_2|N|)$ になるという点です。（ただし、最悪は $O(|N|)$ です。）

また、データを追加する場合にも局所的な情報の更新をするだけでいいので、並列でノードの追加などもできるのではないかと思います。

ただし、このアルゴリズムをつかっていくらモテるようになったからといって、女の子たちと並列で遊んではいけませんよ！

この記事に関するお問い合わせはこちら

FLATz

ブログ