Algorithm & Architecture

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

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

構造的アルゴリズム

Data Encoding

擬似乱数生成

ランダムサンプリング

ランダムサンプリング

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

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

非復元サンプリングの公平性

Inverse (逆数) の重み分布に対して ×1,000 を実行してみれば明らかなように、それぞれの要素の選択頻度の分布 (Actual Win Rate) は重みの分布とは一致しない。唯一一致する分布は Flat だけだが、これはすべての要素の重みが等価であることから一様ランダムサンプリングと同じ意味である。…

2020年6月5日(Fri) #RandomSampling #WRS

論文翻訳: 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

設計パターン