アルゴリズムとデータ構造 - 配列
2019年10月31日概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 配列 データを1列に並べたもの データへのアクセスは容易だが、追加や削除には時間がかかる 配列のデータはメモリの連続した領域に順番に格納される 固定長のメモリを確保する 宣言時に確保（静的確保） 実行時に確保（動的確保） ...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 配列 データを1列に並べたもの データへのアクセスは容易だが、追加や削除には時間がかかる 配列のデータはメモリの連続した領域に順番に格納される 固定長のメモリを確保する 宣言時に確保（静的確保） 実行時に確保（動的確保） ...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 リスト（線形リストの片方向リスト） データを一直線上に並べた構造 各ノードは次のノードへのポインタを持つ データの追加や削除は容易だが、アクセスには時間がかかる リストでは、データは連続したメモリ領域に格納される必要はない 一...
概要トライ木のアルゴリズムと実装についてかく。 bmf-san/road-to-algorithm-master トライ木とはトライ木（プレフィックス木ともいう。英語はそれぞれ、trie、prefix tree）は文字列の集合を扱う木構造の一種。 各ノードは単一または複数の文字列あるいは数値を持ち（ノードは必ずしも値を持つ必要はない）、根ノードから葉に向かって探索して値をつなげていくことで単語を...
概要URLルーティングをつくる エピソード1 とURLルーティングをつくる エピソード2 でURLルーティングの自作について試行錯誤の過程を記してきたが、ようやく一段落させることができたので完結編という形で締括くりたい。 完結、といっても課題はいくらでもあるし突き詰めるとこればっかりに時間をかけることができるようなモノであるということは承知している。。。 前回までの話しエピソード1 では、ルーティ...
概要URLルーティングをつくる エピソード1の続き。 とりあえず動く形のものを仕上げてpackagist - ahi-routerという名前でパッケージ公開した。 エピソード1からの変更点エピソード1では、データ構造に木構造を採用してルーティングを作ろうというと試みた。 パフォーマンスが考慮されているライブラリでは、木構造を生成するロジックを用意して、最適化された探索アルゴリズムを実装するような形...
URLルーティングをつくる エピソード1概要以前、Reactで非常に軟弱なルーティング（cf. ReactとHistory APIを使ってrouterを自作する）を作ったが、改めてそこそこにちゃんとしたルーティングを自作したいと思い、挑戦することにした。きっかけは、最近触っているGolangだ。Golangでは標準ライブラリを駆使することでアプリーケーションをうすーく実装できるようだが、ルーティン...
概要JavaScriptでアルゴリズムを学ぶ。 サーチのアルゴリズムリニアサーチリストや配列のデータに対して、先頭から順番に比較を行っていくアルゴリズム。 配列の長さ分処理を繰り返し、目的のデータに到達したら処理を終了する。目的とするデータが後ろにあるほど処理が遅くなる。 const targetData = 5; const data = [1, 2, 3, 4, 5, 6, 7, 8, 9, ...
概要アルゴリズムの演算性能をざっくりと計算するO記法と計算量の求め方についての前提知識をまとめる。 計算量（オーダー）とは アルゴリズムの演算性能をデータ量の増加に対し、実行時間がどれくらい増加するかの割合で表した指標。 時間計算量 処理時間 空間計算量 メモリ使用量 Big O/Big θ/Big Ωそれぞれ計算時間を記述するものだが、学術的な意味の違いについてまとめる。 Big...