Google App Engineのランキング問題
Google App Engineで何かと話題になってたランキング問題。
appengine ja night #8(ajn8)に参加された方ならご存知のように、既にid:koherentさんがSkiplistというアルゴリズムを使って解決しています。
参考：http://d.hatena.ne.jp/koherent/20100425/1272176872
そのほかにも、id:bufferingsさんの実装例もあります。
参考：http://d.hatena.ne.jp/bufferings/20100225/1267121912
id:bufferingsさんのとほぼ同じアイデアを自分でも思いついてたんで、ちょっとslim3使って実装してみました。
http://tetz-lab.appspot.com/ranking/
事前に乱数で10万件の点数データを入れてあります。
って、何を今更な感じなんですが、せっかく思いついて実装までしちゃったので、日記に残しておきます。
ロジックを簡単に説明します。
まず、
- 点数ごとにその点数を取った人数を格納する領域を用意する。
- その領域をサイズ16の配列に格納する。点数の下位4ビットが配列へのindexとして使用される。
- その上位4ビットをindexとして持つ配列に、上記の配列を格納する。この配列では格納された全配列の保持された人数の合計値を保持する。
- さらに上位4ビット･･･(繰り返し)
というデータ構造を作ります。
69,533点(16進数で10F9D)を例に考えると、下の図みたいな感じの構造です。
ランキングを計算するときには、赤い矢印で示したより高い点数の領域に格納された人数の合計値を計算し、最後に+1すればOKです。
今回の実装では、全Layerの配列をまとめて一つのEntityに保存しているので、getは一回で済みます。
ちなみに、もし配列毎にEntityを分けても、ランキング計算・更新処理ともに一番上Layerには必ずアクセスする必要があるので、分散させることはできません。分散に関しては後述。
ランキング計算にかかる時間は初回は600〜1000ミリ秒程度、2回目以降は70〜120ミリ秒程度でした。
2回目以降が早いのは、多分Datastore側にキャッシュされるからかな？(spin upは計算時間に入れてないから、関係ないはず。)
頻繁にアクセスがある場合には、70〜120ミリ秒で処理できる、ということになりそうです。
更新は120〜200ミリ秒程度かかっています。
この方式のアルゴリズムの速度は、Skiplistと違って点数の件数には影響を受けず、点数の取りうる範囲に影響を受けます。
点数が取りうる値が0〜Xだとすると、アルゴリズムの速度は、
O(log 16 (X))
になるんじゃないかと思います(多分)。
