App Engineでランキングを実装する問題

SHIIBA Mitsuyuki @bufferings

@knj77 点desc, 83563>点, 点>77777 だと 77777の人は入らないのでは？ > ２ではただ単に並び順を数えるので、自分より前に同点の人がいる可能性があるかと。その場合は同率○位として順位を上げないと。 #appengine

KNJ @knj77

あ、基準表の更新の話です。＞前回の点数と今回の点数を渡すI/F #appengine

koher @koher

Skip Listというアルゴリズム（データ構造？）をDatastore上に実装すれば比較的高速にランキングを実現きるんじゃないかと思って実装しています。できあがったら報告します。 #ajn7 #appengine

koher @koher

ランキングをSkiplistで実現してみたところ、1万件のデータから平均2.7秒ほどで順位を求められています。O(log N)なので10万件でも3〜5秒程度で順位を取得可能だと思います。詳しくはブログで。 http://bit.ly/bWWmCW #appengine #ajn7

Kazunori Sato @kazunori_279

まとめ： #appengine 含むNoSQL/KVSのエントリ間でskiplistを作れば、任意ソート条件でランク、カウント、指定範囲の最大／最小／中央／平均／合計値、pagingをO(log n)で実装できる... 理解合ってますか？

Mikio Yoshida @kibayos

はい。RT @kazunori_279: まとめ： #appengine 含むNoSQL/KVSのエントリ間でskiplistを作れば、任意ソート条件でランク、カウント、指定範囲の最大／最小／中央／平均／合計値、pagingをO(log n)で実装できる... 理解合ってますか？

Mikio Yoshida @kibayos

集約Skip Graphの紹介はこっちがいいかな。http://tinyurl.com/22v2cno

App Engine Ja @appengineja

#appengine で skiplist ってすごくね? - スティルハウスの書庫 http://ff.im/-jmFZz

koher @koher

.@kazunori_279 本当ですね！集計関数も含めて実装してみます。わくわくしてきました。 #appengine > いずれにせよ #appengine 上ではすごく重要なパターンになると思いますね

Kazunori Sato @kazunori_279

Togetter - まとめ「#appengine で skiplist ってすごくね?・その2」 http://shar.es/muKu3

Kazunori Sato @kazunori_279

このランキングはどんな仕組みかな／Google App Engine Blog: Google Code Jam's Ranking Library Released http://shar.es/m50m4

Kazunori Sato @kazunori_279

@kibayos さん、@koher は6/4にお越しいただけることになりました。ぜひご参加ください。今日か明日にはATNDで告知する予定です。