2010-06-15から1日間の記事一覧
どうも最後までお付き合いいただきまして、ありがとうございました。 もしソースみたいなんて方がおられましたら、コメントでも残して置いてください。
全点数を一つのインスタンスに格納するのではなく、適当な点数の範囲毎にインスタンスを分けて分散させるアイデアです。 今回試しに実装したものは0〜10万点の範囲で作成していますが、これを4096点毎に25個のインスタンスに分けて実装したのが↓です。 http:…
スケールするカウンタの実装として、「分散カウンタ」というのが知られています。 appengineでは更新処理に比べてgetがとても早いので、カウンタ用のEntityを複数個用意して、 ・更新はランダムに選んだどれか一つに対して実施 ・カウンタの値は全部parallel…
id:koherentさんがajn8向けに作成されたスライドを見ながら、同じことができるか考えてみました。 http://www.slideshare.net/koher/skiplists20100604 P.36 リストの要素数・・・一番上の階層の保持する人数。O(1)で計算可能。 P.37 要素番号による検索・・・要す…
このデータ構造はSkiplistと比べて、汎用性がありません。 扱うのが整数値の点数なら問題ないですが、例えばこれが小数値だと途端に難しくなります。 特に文字列を扱うのは多分無理でしょう。 Skiplistなら任意ソート条件が扱えるんですが、こちらは使用でき…
Google App Engineで何かと話題になってたランキング問題。 appengine ja night #8(ajn8)に参加された方ならご存知のように、既にid:koherentさんがSkiplistというアルゴリズムを使って解決しています。 参考:http://d.hatena.ne.jp/koherent/20100425/1272…