\( \def\vector#1{\boldsymbol{#1}} \)

Algorithms

Takami Torao
  • このエントリーをはてなブックマークに追加

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

構造的アルゴリズム

B+Tree

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

2018年4月15日(Sun) #BTree

R-Tree

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

2018年4月7日(Sat) #RTree

有向非巡回グラフ

DAG (directed acyclic graph; 有向非巡回グラフ) は有向グラフの中でも閉路をもたない (つまり一度通過した頂点にふたたび戻ることはない) 構造を持つグラフ。ソフトウェアの分野ではジョブ管理システムやビルドシステム、ネットワーク問題で扱う。…

2020年7月21日(Tue) #DAG

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

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

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

Banded Hash Tree

現実的なストレージに対して追記効率が良く、累積的な構造変化の完全な履歴を保持するリスト構造 Banded Hash Tree (BHT) について説明します。この構造はデータの追加が可能なハッシュツリー (Merkle ツリー) であり、一般的なハッシュツリーと同様に小さなデータ片を用いてデータの破損や改ざんを検証することができます。…

2021年7月12日(Mon) #BHT #HashTree #MerkleTree 作業中

キャッシュ

キャッシュ (cache) はプログラムやシステムのデータアクセスの高速化を目的としたメカニズムおよびその保存領域。アクセス頻度の高いデータや、次にアクセスされることが予測されるデータ、または生成や取得に時間がかかるデータを一時的に高速に読み取りが可能なキャッシュに保存することでアプリケーションの処理時間を短縮することを狙う。…

2023年2月22日(Wed) #LRU #MRU

確率的データ構造

並行プログラミング

符号理論

データエンコーディング

擬似乱数生成

疑似乱数生成

乱数 (random number) はランダムに選択された数のこと。特定の出現パターンを持たず、選択される値が予測できないという性質を持っており、ゲームや科学技術シミュレーション、暗号セキュリティの分野で重要な役割を持っている。…

2020年2月2日(Sun) #PRNG #MersenneTwister #xorshift

論文翻訳: Xorshift RNGs

ビット演算のみを使用した非常に高速でコンパクトな Xorshift 擬似乱数生成アルゴリズムに関する 2003 年の論文。著者はキャリー付き乗算の論文にも携わっている。Abstract にあるようにこの論文自体はアイディアの説明であり、良い乱数・悪い乱数で何点かの間違いが指摘されている。…

2020年2月2日(Sun) 2003年の論文 #Xorshift #PRNG

乱数検定: RMT 検定

RMT 検定 (random matrix theory test) (1) はデータ列の乱数性を検定するためのアルゴリズム。与えられたデータ列で相互相関行列を作成し、その固有値分布が RMT に基づく理論曲線と一致すれば検定に合格する。…

2023年2月8日(Wed) #RMTTest #RMT検定

乱数検定: NIST SP 800-22

NIST SP 800-22 (1) (または単に NIST 検定) は NIST が 2001 年に刊行した論文による (疑似) 乱数生成器のランダム性を検定するための検定スイートである。…

2023年2月19日(Sun) 2001年の論文 #NIST検定 #Randomness

論文翻訳: NIST SP 800-22: A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications / 暗号アプリケーションのための乱数・擬似乱数生成器の統計的検定スイート

NIST SP 800-22 として刊行された (疑似) 乱数生成器のランダム性の検定に関する 2001 年の論文。15 の検定で構成されている。この論文に基づいた検定スイートは NIST SP 800-22: Download Documentation and Software からダウンロードできる。…

2023年2月8日(Wed) 2001年の論文 #NIST #NIST80022

ランダムサンプリング

ランダムサンプリング

ランダムサンプリング (RS; random sampling) または無作為抽出、乱択とは、ある集合から無作為に要素を選択すること。社会科学分野での統計のために利用されることも多いが、このページではソフトウェアアーキテクチャに焦点を当てている。…

2020年5月29日(Fri) #RandomSampling #WRS #ReservoirSampling

非復元ランダムサンプリングにおける公平性

Inverse (逆数) の重み分布に対して ×1,000 を実行してみれば明らかなように、それぞれの要素の選択頻度の分布 (Actual Win Rate) は重みの分布とはかけ離れた挙動となる。…

2020年7月12日(Sun) #RandomSampling #WRS #fairness

論文翻訳: Weighted Random Sampling (2005; Efraimidis, Spirakis)

重み付きランダムサンプリング (乱択) のアルゴリズムに関する 2005 年の論文。重み付き非復元ランダムサンプリング (weighted random sampling without replacement) に基づいて、開始時点でサイズが未知の母集団から 1 パスでサイズ \(m\) の部分集合を生成することができる。…

2020年5月22日(Fri) 2005年の論文 #WeightedRandomSampling #ReservoirSampling

論文翻訳: Fast Generation of Discrete Random Variables

Walker のエイリアス法を改良して正方ヒストグラムを使う方法で高速に重み付きランダムサンプリングを行うアルゴリズムに関する 2004 年の論文。

2020年5月31日(Sun) 2004年の論文 #WeightedRandomSampling #SquareHistogram

論文翻訳: Min-Wise Independent Permutations (Extended abstract)

min-wise 独立置換族 (min-wise independent permutations family) に関する 1998 年の論文。Brahms サンプリングの関連で調べたもの。…

2023年1月31日(Tue) #最小値独立置換族

グラフィックス

アルゴリズム問題

設計パターン