Algorithm & Architecture

アルゴリズムやデータ構造、設計パターンに関するあれこれ。

構造的アルゴリズム

B+Tree

B-Tree の派生型である B+Tree は、個々のキーの検索効率を下げる代わりに、ある範囲のデータをまとめて取得するケースに適した構造を持つ。B-Tree が中間ノードにもデータエントリを保持していたのに対して、B+Tree では末端の葉にのみエントリを保持し、葉は相互にリンクしたリストの構造を持っている。…

2018年4月15日(Sun)

R-Tree

R-Tree は深さ平衡木 (depth-balanced tree)。葉ノード

2018年4月7日(Sat)

論文翻訳: The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree

空間インデックス (spatial index) のためのアルゴリズム Priority R-Tree (2004) に関する論文。

2018年4月5日(Thu) 2004年の論文作業中

論文翻訳: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

大量のデータから要素数を推定するアルゴリズム HyperLogLog に関する 2007 年の論文。

2018年10月30日(Tue) 2007年の論文作業中

Data Encoding

可変長整数エンコーディング

いくつかの可変長整数エンコーディング実装について。このページの話題は任意精度整数演算ではなくデータ圧縮の目的で整数値をエンコーディングする方法である。

2018年3月26日(Mon)

基数変換

Base64 はバイナリを 64 種類の文字を使用した文字列に変換する。これは、基数 256 の数列を基数 64 の数列に変換し、それぞれの桁を文字にマッピングすることと等価である。Base58 のような 64 以外の符号化についても、対象とする基数が異なるだけで同じ処理となることが分かるだろう。…

2019年2月2日(Sat) 作業中

設計パターン

Resource Pooing 実装

リソースプーリング (resource pooling) は有限のリソースをプールしアプリケーション内の複数の処理で共有 (resource sharing) する仕組み。一般的に、生成や消滅のコストの高いリソースを初期化を終えた状態で共有、再利用することによるパフォーマンス向上の効果を目的としている。…

2018年11月27日(Tue)