学生版 社会人版
JA EN

#data-structures

5 記事

01 ·データ構造·★ 会員·論文·16分で読めます 確率的データ構造 — 数えずに数える Space/Time Trade-offs in Hash Coding with Allowable Errors (Bloom ブルームフィルタ・HyperLogLog・Count-Minスケッチを前提知識ゼロから解説。「少しだけ間違える権利」と引き換えにメモリを数KBに固定する仕組みと、巨大サービスの裏でどう運用されているかまで。 02 ·データ構造·★ 会員·14分で読めます B木とLSM木 — データベースの心臓 世のデータベースはほぼ全部、B木かLSM木のどちらかの上に建っています。「ディスクはページ単位でしか書けない」という物理から出発して、両者がなぜ正反対の設計になったのか、書込増幅とは何か、PostgreSQLとRocksDBで何が違うのかを、前提知識ゼロから実務のパラメータ名まで。 03 ·データ構造·★ 会員·13分で読めます キャッシュに優しいコード — 同じO(n)で10倍差がつく理由 計算量が同じ2つの実装で実行時間が桁違いになるのは、CPUがデータを「1個ずつ」ではなく「64バイトの塊」で運ぶからです。局所性・キャッシュライン・配列と連結リストの実測差・AoS/SoA・ループ順序・false sharing を、前提知識ゼロから、最後は perf で自分の目で確かめるところまで。 04 ·データ構造·★ 会員·論文·9分で読めます ハッシュと近傍探索 — ベクトル検索の下地 Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs 「探す」を速くする2つの発明——完全一致のハッシュ表と、意味の近さで探すLSH・HNSW——を前提知識ゼロから解説。RAGやベクトルDBの裏で動いている近傍探索の仕組みが分かる。 05 ·データ構造·無料·8分で読めます データ構造の選び方 — 配列・ハッシュ・木・ヒープ 配列・ハッシュ表・木・ヒープが、それぞれ何を速くして何を諦めているのか。用途からの逆引き表と、トークナイザ・ベクトル検索・KVキャッシュといったAI実装で実際にどれが使われているかまで。