<a class="info_title emj" href="https://togetter.com/li/17225" title="App Engineでランキングを実装する問題">App Engineでランキングを実装する問題

#appengine ランキング。大事なのは前提を変えることかな。何位を正確に算出せずに100〜150位ですみたいな仕様にする。または、翌日に正確な順位を伝える(ランキングは昨日の結果より算出してます)など。正確な順位は上位20くらいにするとか。落し所を考えるのも大事

2010-02-23 07:55:51

@bluerabbit777jp 難しいですねー＜ランキングどうしても正確な順位を出したいなら外部にサーバ立てちゃうかな。そっちが落ちたら概算順位にフォールバックとか。 #appengine

2010-02-23 08:25:54

#appengine ランキング。0～100点なら得点に対する人数分布を数えちゃえばいい。これを拡張して、10^n、10^(n-1)、・・・1点区切りの分布を数えることにすれば、n+1回の更新とn+1回のgetで正確な順位が更新・算出できるかも。

2010-02-23 08:45:31

#appengine ランキング。間違えた。取得はn+1じゃないや。O(nlogn)になるのかな。

2010-02-23 08:49:21

#appengine ランキング。実際132点のランキングが知りたい場合、0～99点はn1人、100～109点はn2人、110～119点はn3人、120～129点はn4人、130～131点はn5人って数えれば、sum(n1～n5)位。どうじゃろ。底は10でなくても良いけど。

2010-02-23 08:55:36

#appengine ランキング。O(nlogn)で良さそうだけど、それを証明するには余白がなんたらかんたら。分布数えソートの亜種になるのかな。故に、得点は有限の整数っていう前提が必要。

2010-02-23 09:12:13

Suguru ARAKAWA @ashigeru

@bluerabbit777jp 100位までのランカーは普通に表示して、それ以降はグレードだけ表示する、とかですかね。毎晩1000件ぐらいランダムサンプリングして、分布をモデリングしてAランクからEランクくらいまで出す感じ。趣旨と違うかも。 #appengine

2010-02-23 10:26:07

佐々木竹充/SASAKI TAKERU @urekat

@bluerabbit777jp 10万なら1000*100だから数時間〜１日に1回のバッチで正確に順位を数えてあげるのも可能かな。リアルタイムはTOP1000ぐらいを対象にしてmemcacheで10分ぐらいキャッシュしてあげればいい感じかな。 #appengine

2010-02-23 12:45:27

@fm021 ランキング実装の件、これが正解というのは一概に言えません。この例でもわかる通りGAEでは要件(前提)を変える事も含めて進める必要があるからです。実装案はいくつか #appengine タグにつぶやきがあります。

2010-02-23 18:41:21

#appengine QT @bluerabbit777jp その前提なら、ユーザ名：得点マップと得点：取得者数マップと全ユーザ数があれば簡単に算出できると思うよ。最高点の人は何人いても１位だし、その下は直上得点順位＋直上得点取得者数で求められるんじゃないかな /via @tkz

2010-02-23 18:43:06

#appengine QT @bluerabbit777jp appengineに限らないけど、日次でバッチしてチートを作っておいて、その時点で何位ですとしておいて最高得点を更新した時だけチート表を更新みたいな。ってかぶってますね。... /via @fm021

2010-02-23 18:46:44

@bluerabbit777jp ランキングの問題、5点ごととか10点ごとで得点の分布を計算しておいて線形補完で順位をだして、上位100位くらいはlistで持っておくっていう感じがいいでしょうかね。

2010-02-24 22:23:55

@bluerabbit777jp 該当の分布のところをカウントアップするだけなので、リアルタイムでいいんじゃないでしょうかね。線形補完は、100点の人が60位で200点の人が40位ってデータあるなら、150点の人は50位って具合に単純な比率で補完する感じで。

2010-02-24 22:32:31

@bluerabbit777jp あと、点数は正規分布すると思うので、最低点とか最高点に近いところは目を荒くして、平均に近いところは細かい点数で数えておくとか。一番強引なのは、もう正規分布することにして、平均と分散から適当に順位を計算してしまう作戦。

2010-02-24 22:34:32

Suguru ARAKAWA @ashigeru

@kis それだと密集地帯で精度が落ちるのと、得点の範囲があらかじめ固定されちゃいそうな気がするんですよね。なのでランダムサンプリングでもいいかなと

2010-02-24 22:35:57