昨日一昨日、Google App Engine (GAE)に関する日本最大の勉強会(だと思う)appengine ja night #7 (ajn7)が行われました。 その中で『ランキング問題』が話題に上がりました。『ランキング問題』とは、何十万件もの点数のデータがあるときに、App Engine上で、「◯点は何位です」と高速に求めることは難しい、という問題です。(◯ページ目を表示、というページングもこれと同じ種類の問題になります。) ajn7では「上位でない限り正確な順位は必要ないのではないか」という話になりましたが、Skiplistを用いた検索アルゴリズムを使えば正確かつ高速に順位を求めることができるのではないかと思い、実装&検証してみました。 ランキング(順位取得)のデモ 下記ページで順位取得のデモを動かしています。スコア(点数)を入力すると順位と取得にかかった時間が表示されます(時