Post

アルゴリズム

2019-03-24 21:58:28

URLルーティングをつくる エピソード3(完結編)

概要URLルーティングをつくる エピソード1 とURLルーティングをつくる エピソード2 でURLルーティングの自作について試行錯誤の過程を記してきたが、ようやく一段落させることができたので完結編という形で締括くりたい。 完結、といっても課題はいくらでもあるし突き詰めるとこればっかりに時間をかけることができるようなモノであるということは承知している。。。 前回までの話しエピソード1 では、ルーティングのデータ構造を考えたり、とりあえず手を動かして実装のイメージを掴もうとした。(動くところまで持っていけなかった。。。) エピソード2では、データ構造を見直したり、参考になりそうなリポジトリを漁って...

プログラミング

PHP URLルーティング HTTP アルゴリズム 木構造

2019-01-09 02:20:08

URLルーティングをつくる エピソード2

概要URLルーティングをつくる エピソード1の続き。 とりあえず動く形のものを仕上げてpackagist - ahi-routerという名前でパッケージ公開した。 エピソード1からの変更点エピソード1では、データ構造に木構造を採用してルーティングを作ろうというと試みた。 パフォーマンスが考慮されているライブラリでは、木構造を生成するロジックを用意して、最適化された探索アルゴリズムを実装するような形になっているようだが、木構造を生成するロジックをかくのはめん(ry 時間がかかりそうだったので、探索部分だけ頑張る方向性でやってみることにした。 前回はルーティング定義のデータ構造を、 <?ph...

プログラミング

HTTP URLルーティング アルゴリズム 木構造

2018-12-19 02:38:10

URLルーティングをつくる エピソード1

URLルーティングをつくる エピソード1概要以前、Reactで非常に軟弱なルーティング(cf. ReactとHistory APIを使ってrouterを自作する)を作ったが、改めてそこそこにちゃんとしたルーティングを自作したいと思い、挑戦することにした。きっかけは、最近触っているGolangだ。Golangでは標準ライブラリを駆使することでアプリーケーションをうすーく実装できるようだが、ルーティング周りは標準ライブラリがパワー不足なのものあって、外部のライブラリに依存するケースが多いらしい。そんなこともあってルーティングを自作できるようになるとGolangでもそれ以外でもルーティングを自前で用...

プログラミング

HTTP アルゴリズム URLルーティング 木構造

2018-07-17 01:05:15

JavaScriptで始めるアルゴリズム

概要JavaScriptでアルゴリズムを学ぶ。 サーチのアルゴリズムリニアサーチリストや配列のデータに対して、先頭から順番に比較を行っていくアルゴリズム。 配列の長さ分処理を繰り返し、目的のデータに到達したら処理を終了する。目的とするデータが後ろにあるほど処理が遅くなる。 const targetData = 5; const data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; (function () { for (let i = 0; i < data.length; i++) { if (targetData == data[i])...

プログラミング

アルゴリズム バイナリーサーチ リニアサーチ バブルソート セレクションソート

2018-04-22 12:42:55

O(オーダー)記法とアルゴリズムの計算量の求め方

概要アルゴリズムの演算性能をざっくりと計算するO記法と計算量の求め方についてまとめる。 計算量(オーダー)とは アルゴリズムの演算性能をデータ量の増加に対し、実行時間がどれくらい増加するかの割合で表した指標。 時間計算量 処理時間 空間計算量 メモリ使用量 O(オーダー)記法 O記法 計算理論における名称 概要 O(₁) 定数時間 データ量が増加しても処理時間が増加しない O(log n) 対数時間 データ量が増えても計算時間がほとんど増えない O(n) 線形時間 データ量が増加した分だけ処理時間が増える O(n log n) 準線形、線形対数時間 O(n...

アルゴリズム

O記法 アルゴリズム