Google App Engineでランキングを実現する方法
準備
まず、例えば以下のようなリストをTaskQueueを使って事前に用意します。
これは単純に、得点の上位から1000人区切りでキリ番の人がそれぞれ何点なのかを記録してます。
1000人目 98432点
2000人目 83563点
3000人目 68779点
.
.
.
これが基準点となります。
ポイントは「人数」で区切っていること。
これで得点の分布がどうであろうと関係なくなります。
そしたら実行。
1
例えば77777点の人が自分は何位なのか知りたい場合、
まず、上の表で77777点より一つ上の基準点を探します。(点asc, limit 1で見つかる)
この場合は、83563点が見つかってその時点で自分が2000位より下であることが分かります。
２
後は、実際の点数表から83563点から77777点まで、
何人の人がいるかを数えるだけで順位がわかります。
(点desc, 83563>点, 点>77777のリストサイズを調べる)
コスト高そうですが、1000人単位で区切っているため、
サイズ1000以上のリストが帰ってくることはないです。
7687698998432点とか取っちゃった人は1000以内確定として、
98432点から逆に人数を数えればいいと思います。
点desc, 点>7687698998432で問い合わせればいいと思います。
３
ここまでが、大枠の考え方ですが、一つ困ることがあります。
例えば、基準点である83563点を取った人が999人いる場合です。
(1000人いた場合は自ずと基準点が次になるはず。)
83563点+1点の人は本当は2999位なのに、2001位に見えてしまう。
これには最初の表を以下のようにすることで対処します。
1000人目 98432点 5人
2000人目 83563点 999人
3000人目 68779点 1人
.
.
.
同じように、77777点に複数人いた場合も実行時に同点の人数をチェックすることで調整できます。
（点＝77777点の人を、(2)と同じ並び順で自分まで数える）
自分の得点より前の人数を出すのでここは必要ないですね。
id:bufferingsさん、ありがとうございます。
まとめ
-
- 準備 ○人単位でそれぞれ何点か（＝基準点）の表を持つ
-
- 自分はどの基準点のすぐ下なのか問い合わせ
- 基準点から自分まで何人いるのか問い合わせ
自分と同点の人が何人いるのか問い合わせ
どうでしょうか？
実際に組んでないのでアレですが、、、
どんな規模や分布にも左右されず、
必ず３クエリ2クエリで答えが出せるという点でいいかなと思っています。
パフォーマンスも一定です。
あとは、人数単位の基準表をいかに素早く更新するか、ですが、
TQのとかの工夫でどうにかなると思っています（適当w）
追記
元の点数表に更新がある度に、基準表を更新すれば、
総なめは初回だけでいいかもしれないですね。
元の点、新しい点を更新機能に渡すようにして、
基準点をまたぐ時だけ、基準点を±すればいいのでは、と思っています。
あたらしく基準点が生まれるタイミングをどうにか捕まえる必要がありますが。
そう考えると、基準点が生まれるタイミングさえ逃さなければ、
最初から総なめではなく、その方式でいいかもしれない。
