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

App Engine(KVS)でランキングを実装する方法についてのtweetを集めました。
appengine GAE kvs
4730view 0コメント
4
あおうさ @bluerabbit777jp
#appengine でランキングを実装するには? androidアプリのゲームで得点を元にユーザが何位だったのかを算出したい。昨日これを聞かれて、あーなかなか思ったよりも難しいなーと考え中。みんなならどうする?(ユーザ数は仮に10万だとして考える)
あおうさ @bluerabbit777jp
#appengine ランキング。大事なのは前提を変えることかな。何位を正確に算出せずに100〜150位ですみたいな仕様にする。または、翌日に正確な順位を伝える(ランキングは昨日の結果より算出してます)など。正確な順位は上位20くらいにするとか。落し所を考えるのも大事
ほるっふーdeveloper @pto_developer
@bluerabbit777jp 難しいですねー<ランキング どうしても正確な順位を出したいなら外部にサーバ立てちゃうかな。そっちが落ちたら概算順位にフォールバックとか。 #appengine
ほるっふーdeveloper @pto_developer
#appengine ランキング。0~100点なら得点に対する人数分布を数えちゃえばいい。これを拡張して、10^n、10^(n-1)、・・・1点区切りの分布を数えることにすれば、n+1回の更新とn+1回のgetで正確な順位が更新・算出できるかも。
ほるっふーdeveloper @pto_developer
#appengine ランキング。間違えた。取得はn+1じゃないや。O(nlogn)になるのかな。
ほるっふーdeveloper @pto_developer
#appengine ランキング。実際132点のランキングが知りたい場合、0~99点はn1人、100~109点はn2人、110~119点はn3人、120~129点はn4人、130~131点はn5人って数えれば、sum(n1~n5)位。どうじゃろ。底は10でなくても良いけど。
ほるっふーdeveloper @pto_developer
#appengine ランキング。O(nlogn)で良さそうだけど、それを証明するには余白がなんたらかんたら。分布数えソートの亜種になるのかな。故に、得点は有限の整数っていう前提が必要。
Suguru ARAKAWA @ashigeru
@bluerabbit777jp 100位までのランカーは普通に表示して、それ以降はグレードだけ表示する、とかですかね。毎晩1000件ぐらいランダムサンプリングして、分布をモデリングしてAランクからEランクくらいまで出す感じ。趣旨と違うかも。 #appengine
佐々木竹充/SASAKI TAKERU @urekat
@bluerabbit777jp 10万なら1000*100だから数時間〜1日に1回のバッチで正確に順位を数えてあげるのも可能かな。リアルタイムはTOP1000ぐらいを対象にしてmemcacheで10分ぐらいキャッシュしてあげればいい感じかな。 #appengine
あおうさ @bluerabbit777jp
@fm021 ランキング実装の件、これが正解というのは一概に言えません。この例でもわかる通りGAEでは要件(前提)を変える事も含めて進める必要があるからです。実装案はいくつか #appengine タグにつぶやきがあります。
あおうさ @bluerabbit777jp
#appengine QT @bluerabbit777jp その前提なら、ユーザ名:得点マップと得点:取得者数マップと全ユーザ数があれば簡単に算出できると思うよ。最高点の人は何人いても1位だし、その下は直上得点順位+直上得点取得者数で求められるんじゃないかな /via @tkz
あおうさ @bluerabbit777jp
#appengine QT @bluerabbit777jp appengineに限らないけど、日次でバッチしてチートを作っておいて、その時点で何位ですとしておいて最高得点を更新した時だけチート表を更新みたいな。ってかぶってますね。... /via @fm021
きしだൠ @kis
@bluerabbit777jp ランキングの問題、5点ごととか10点ごとで得点の分布を計算しておいて線形補完で順位をだして、上位100位くらいはlistで持っておくっていう感じがいいでしょうかね。
きしだൠ @kis
@bluerabbit777jp 該当の分布のところをカウントアップするだけなので、リアルタイムでいいんじゃないでしょうかね。線形補完は、100点の人が60位で200点の人が40位ってデータあるなら、150点の人は50位って具合に単純な比率で補完する感じで。
きしだൠ @kis
@bluerabbit777jp あと、点数は正規分布すると思うので、最低点とか最高点に近いところは目を荒くして、平均に近いところは細かい点数で数えておくとか。一番強引なのは、もう正規分布することにして、平均と分散から適当に順位を計算してしまう作戦。
Suguru ARAKAWA @ashigeru
@kis それだと密集地帯で精度が落ちるのと、得点の範囲があらかじめ固定されちゃいそうな気がするんですよね。なのでランダムサンプリングでもいいかなと
きしだൠ @kis
@ashigeru 得点の範囲がある程度しぼれるゲームなら、分布とればらくしょーなんだけどね。1000プレイされたときに平均と分散とっておいて・・・とか思ったけど、得点ってインフレーションするし。
Suguru ARAKAWA @ashigeru
@kis オンラインゲームとかだと特にそんな気がします>インフレ。累積しないタイプなら何とかなりそうですね
Kenji🚀 @knj77
TQで1000人単位とかで基準点を求めておいて、その基準点から何人並んでるか。ではダメですかね。ランキング問題。どの基準点を使うかで1クエリ使うけど。 #appengine
najeira @najeira
これいいですね RT @knj77: TQで1000人単位とかで基準点を求めておいて、その基準点から何人並んでるか。ではダメですかね。ランキング問題。どの基準点を使うかで1クエリ使うけど。 #appengine
Kenji🚀 @knj77
TQで基準点上の人数求めておくのと、実行時に求める人と同点の人数で微調整すれば求めれば解決。かな。ランキング #appengine
Mitsuyuki Shiiba @bufferings
#appengine ランキング。0点以上100万点未満。ブロック化数を100にしたら、読み書き共に3エンティティへのキーによるアクセスだけでいけそうだなー。間違ってるかなー。どうかなー。今日はもう寝よう。
Mitsuyuki Shiiba @bufferings
帰ったら実装をブログにupしま。 RT @bufferings: #appengine ランキング。0点以上100万点未満。ブロック化数を100にしたら、読み書き共に3エンティティへのキーによるアクセスだけでいけそうだなー。間違ってるかなー。どうかなー。今日はもう寝よう。
Mitsuyuki Shiiba @bufferings
あ。タグ。 #appengine RT @bufferings: 日記書いた > Google App Engine で Ranking について考察 http://goo.gl/oOTu
Kenji🚀 @knj77
ランキング問題の解決案を書いてみました。http://d.hatena.ne.jp/knj77/20100227 #appengine
残りを読む(12)
ログインして広告を非表示にする
ログインして広告を非表示にする