#データ構造
21 件の記事
Goでプロセス・goroutine・メモリを覗いてみた
Goを使って、プロセスのアドレス空間・goroutineの動作・スタックとヒープの挙動を軽く覗いてみた記録です。子プロセスとの仮想アドレス空間の違いやメモリ領域の独立性を、os/execなどを用いた実装例を通して確認します。
オープンアドレスハッシュテーブルとスイステーブル
Goのブログ記事「Faster Go maps with Swiss Tables」を読んだことをきっかけに、オープンアドレス法とスイステーブル（Swiss Table）について整理した記事です。ハッシュの衝突を解決する手法や、キャッシュ効率の高いハッシュテーブルを設計するためのポイントを紹介します。
2分探索木の探索パターンを図解で理解する
2分探索木の探索パターンを解説。DFS（先行順・中間順・後行順）、BFS、一筆書き法による走査で木構造の走査順序をマスターする実践ガイドです。
アルゴリズムとデータ構造 - ハッシュマップ
アルゴリズムとデータ構造を学ぶシリーズの記事。ハッシュマップの仕組みを取り上げ、平均O(1)のアクセスや、衝突解決のオープンアドレス法とチェイン法の違いを、Goでの基本的な実装例とともに解説する。
隣接リストと隣接行列の違い｜グラフ表現の使い分け
隣接リスト（O(V+E)の空間・疎グラフに有利）と隣接行列（O(V²)の空間・O(1)の辺判定）を比較。有向・無向グラフのGo実装例とともにグラフの表現方法を解説します。
スタックとキューの実装
Goでスタックとキューをそれぞれ実装してみた記事です。スライスを使ったパターンと連結リストを使ったパターンの2通りで、LIFOのスタックとFIFOのキューを実装し、push・popやenqueue・dequeueといった操作を時間計算量O(1)で構築する方法を、パターン別に比較しながら紹介します。
連結リストのランナーテクニック
連結リストの走査に役立つ「ランナーテクニック」についてまとめた記事です。『世界で闘うプログラミング力を鍛える本（コーディング面接189問とその解法）』で紹介されていて初めて知った、2つのポインタを異なる速度で進めるこの手法の考え方と使いどころを解説します。
アルゴリズムとデータ構造の基本の復習
コーディングクイズを解く日課の再開にあたり、アルゴリズムとデータ構造の基本を総復習した記事。配列や文字列、ハッシュテーブル、連結リスト、木、スタック、キュー、ソート、計算量といった基礎を、コーディング問題を意識して整理する。
アルゴリズム図鑑 増補改訂版 絵で見てわかる33のアルゴリズム
『アルゴリズム図鑑 増補改訂版 絵で見てわかる33のアルゴリズム』の書評。ソートや探索をはじめとする33のアルゴリズムを、図解を中心にわかりやすく解説する一冊。動きを図で直感的に理解でき、リファレンスとして手元に置いておきたくなる。
二分探索木（BST）とは｜計算量とGoでの実装
二分探索木（BST）を解説。平均O(log n)の探索・挿入、DFS（先行順・中間順・後行順）とBFSによる走査を、GoでのBST実装例とともに紹介します。
アルゴリズムとデータ構造 - ヒープ
優先度付きキューを実現するmin-heap/max-heapの仕組みを解説。O(log n)の挿入・削除と、Goでのヒープ実装を紹介します。
アルゴリズムとデータ構造 - キュー
アルゴリズムとデータ構造を学ぶシリーズの記事。FIFOのキューというデータ構造を取り上げ、enqueue・dequeueの操作やスタックとの計算量の比較を、Goでの実装例とともに解説する。
アルゴリズムとデータ構造 - スタック
アルゴリズムとデータ構造を学ぶシリーズの記事。LIFOのスタックというデータ構造を取り上げ、push・pop・peekの操作と計算量を、Goのスライスを使った実装例とともに解説する。
アルゴリズムとデータ構造 - 配列
アルゴリズムとデータ構造を学ぶシリーズの記事。データ構造としての配列を取り上げ、O(1)のランダムアクセスやO(n)の挿入・削除、静的・動的なメモリ確保の違いを、Goでの実装例とともに解説する。
アルゴリズムとデータ構造 - リスト
単方向連結リストの仕組みを解説。O(n)のアクセスとO(1)の挿入・削除、ポインタによるノードの走査、Goでの線形連結リスト実装を紹介します。
Golangでトライ木（Trie）を実装する｜前方一致検索
トライ木（プレフィックス木）というデータ構造のアルゴリズムと、そのGoでの実装についてまとめた記事です。O(m)で検索・挿入ができる特徴や、HTTPルーティングなどへの応用、Radix Treeとの使い分けについて、挿入・検索の実装例を交えて解説します。
みんなのコンピュータサイエンス
『みんなのコンピュータサイエンス』の書評。コンピューターサイエンスの全体像を、要点を押さえてコンパクトに掴める一冊。個々のトピックを深掘りするより、CSという分野の見取り図をつかみたいときにちょうど良い。
URLルーティングをつくる エピソード3（完結編）
ツリー構造を使ってURLルーティングを自作するシリーズのエピソード3。PHPで、パスパラメータやHTTPメソッド、ツリーベースの探索アルゴリズムに対応したURLルーティングを完成させるまでを解説する。
URLルーティングをつくる エピソード2
ツリー構造を使ってURLルーティングを自作するシリーズのエピソード2。エピソード1のツリー構造を洗練させ、エンドポイントのマッピングやスケーラブルなルーティングロジックの実装を解説する。
URLルーティングをつくる エピソード1
ツリー構造を使ってURLルーティングを自作するシリーズのエピソード1。HTTPリクエストのマッチングやパスパラメータの扱いを軸に、効率的にリクエストを処理するルーティングの仕組みを実装しながら解説する。