Data Sturucture

概要 ～数十億の大規模データ上で、特定範囲の極値や頻度などが高速に求められる構造。 多次元への拡張も可能。 読んだやつ Francisco Claude and Gonzalo Navarro. The Wavelet Matrix. Proc. SPIRE'12, pages 167-179. LNCS 7608 ウェーブレット木の世界 人工知能学会 私のブックマーク Vol.26 No.6 (2011/11) 簡潔データ構造 簡潔ビットベクトル(完備辞書) ウェーブレット行列最速攻略 Eating Your Own Cat Food コード ウェーブレット行列(wavelet matrix) ウェーブレット行列で競プロの問題を解く 動的ウェーブレット行列(dynamic wavelet matrix) 3 次元空間のクエリを処理する Wavelet Matrix SIGGRAPH Asia の最優秀賞論文を解説してみた（2D Wavelet 行列を用いた定数時間メディアンフィルタ） ウェーブレット行列の構造についてはすでに分かりやすい資料がある（とくに 2., 6., 8. がおすすめ）。 ...

std::unordered_map や boost::flat_map などのハッシュマップはほぼ $O(1)$ で探索でき，赤黒木の std::map に比べて探索も走査も速いとされている． [C++] STLの型の使い分け std::mapを線形探索してはいけない100の理由 mapとunordered_mapのアイテム全走査の比較とmapの存在意義について考える また unordered_map と map の使用は似ており，置換すること自体はさほど難しくない． ...