単純な場合の Skip Graphs アルゴリズムを実装してみた - higepon blog
分散などは考えずに、単純な場合の Skip Graphs アルゴリズムを実装してみた。（僕の理解やコードが間違っている可能性があるので注意） Skip graphs by James Aspnes and Gauri Shah という論文に書かれているアルゴリズム。 実装したのは Level 0, Level1 の単純2階層の Skip Graph (= membership vector は 0 と 1 の 2種類しかない) 実装してみて分かったが階層を増やすのはとても簡単だ node の insert/search/range-search をサポート search が書ければ range-search は簡単 また理解の助けになるよう 検索経路が取得できるようにした テストコードをまじめに書いた 動作例 node20 (key=20, value="$20") のノードを開始点として
GAEの設計指針めも - あおうさ＠日記
とりあえず思いつくまま列挙。まだまだ変わる可能性は大きい。 正規化しない。RDBMSでいうところのJOIN済みのでっかいテーブル作れ。 SELECTはがんばらない。INSERT超がんばれ。 PKはString型にしてgae.encoded-pkを使用する。 PKに複合キーは使わない。(コンポジットインデックス使わない) Date型のプロパティは使わない。String型にする。 プリミティブ型はnullを許容しないので使わない テーブル間のjoinができない。→正規化せずJOIN済みのでっかいテーブルを作る 集約関数がない（group byできない）、count()で全件カウントできない →集約したい値は、集約用のエンティティを用意してInsert時に集計値を保存する（最大値／最小値も同様） 毎回対象データをすべて取得してループで集計するのは非効率（また最大1000件の制限がある）集約したい
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
