Post

プログラミング

2020-02-01 16:02:47

アルゴリズムとデータ構造 - クイックソート

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 クイックソート データ列の中から適当なデータ(ピボット)を選択し、ピボットより小さいデータを前方、大きいデータを後方に移動させる。 分割されたデータをそれぞれソートする 分割統治法の一種 計算時間 最悪計算時間 O(n²) 最良計算時間、平均計算時間 O(n log n) 実装package main import ( "fmt" "math/rand" ) func quickSort(n [...

プログラミング

アルゴリズム データ構造 クイックソート

2020-02-01 16:02:11

アルゴリズムとデータ構造 - マージソート

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 マージソート データ列が分割できなくなるまで(要素が1つ)再帰的に分割を行い、分割されたデータを複数回マージを繰り返していくことによってソートする 分割統治法に基づくソート 大きな問題を小さな問題に分割する 計算時間 最悪計算時間 O(n log n) 実装// cf. https://github.com/TheAlgorithms/Go/blob/master/sorts/merge_sort.go packa...

プログラミング

アルゴリズム データ構造 マージソート

2020-02-01 16:01:16

アルゴリズムとデータ構造 - ヒープソート

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ヒープソート 要素の並べ替えを二分ヒープ木を用いて行うソート ヒープの構築 ヒープから要素(根)を取り出す操作をヒープ木が空になるまで行う 計算時間 最悪計算時間、平均計算時間 O(n log n) 実装package main import "fmt" // Heap is a heap. type Heap struct { values []int size int max...

プログラミング

アルゴリズム データ構造 ヒープソート

2020-02-01 16:00:17

アルゴリズムとデータ構造 - 挿入ソート

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 挿入ソート データ列の先頭から順番にソートしていく ソート済みと未ソートでそれぞれ部分列に分けられる 1回目:0番目をソート済みとするので何もしない 2回目:0番目と1番目を比較して順序が逆なら入れ変える 3回目:0番目から1番目までのデータ列と比較、順序入れ替え 4回目:0番目から2番目までのデータ列と比較、順序入れ替え 以下、未ソート部分がなくなるまで繰り返す 計算時間 O(n²) 実装package main...

プログラミング

アルゴリズム データ構造 挿入ソート

2020-02-01 15:59:35

アルゴリズムとデータ構造 - 選択ソート

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 選択ソート データを昇順または降順に並べ変えるソートの一つ 1番目の要素と2番目以降の要素の中で最小の値を比較して、順序が逆なら入れ変えを行う、という操作をデータ列の最後の一つ手前まで繰り返す 計算時間 最良計算時間、平均計算時間 バブルソートと同じくО(n²) 実装package main func selectionSort(n []int) []int { for i := 0; i < len(...

プログラミング

アルゴリズム データ構造 選択ソート

2020-02-01 15:58:14

アルゴリズムとデータ構造 - バブルソート

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 バブルソート データを昇順または降順に並べ変えるソートの一つ 全要素に対して、隣合う要素同士を比較し、順序が逆なら入れ替えを行う、という操作を要素数-1回繰り返す 計算時間 最悪計算時間、最良計算時間、平均計算時間 O(n²) 実装package main import "fmt" func bubbleSort(n []int) []int { for i := 0; i < len(n)-1; i...

プログラミング

アルゴリズム データ構造 バブルソート

2020-01-26 23:57:08

GolangでgoblinというURLルーターを自作した

概要GolangでURLルーターを自作したので実装するまでの過程をメモしておく。 準備URLルーターを実装する際に行った下準備をまとめる。 データ構造とアルゴリズムURLをどのようにマッチングさせるか、というロジックについて検討する。 多くのライブラリでは、データ構造として木構造がよく扱われているので、どんな種類の木構造を採用するかを考えてみた。 文字列探索に特化した木の中で、時間的・メモリ的計算量がよりベストなものを選定しようとすると、基数木というのが良さそうに見えるので最初はそれを採用しようとしていたのだが、実装が難し過ぎて挫折をした。 もう少し身近でシンプルなものをということでトライ木を...

プログラミング

Golang URLルーティング

2020-01-15 22:40:24

アルゴリズムとデータ構造 - 二分探索木

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 二分探索木 各ノードが多くとも2つまでのノードしか持たない二分木の一種で、左の子ノード ≤ 親 ≤ 右の子ノードという制約を持った構造の木 最も左にあるノードが最小ノードで、最も右にあるノードが最大ノードとなる 二分探索木に限った話ではないが、木構造の走査(traverse)方法についてかいておく 深さ優先探索(depth-first search) 前順(行きがけ順、前置順、preorder) 中順(通りがけ順、中置順、...

プログラミング

アルゴリズム データ構造 二分探索木

2020-01-14 22:04:54

アルゴリズムとデータ構造 - ヒープ

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ヒープ 優先度付きキュー(priority queue)の一種 優先度付きキューは、集合(set)を扱うデータ型 集合に含まれる要素は優先度順に取り出される 集合を扱うデータ型の例:キュー、スタック ヒープの種類 最小ヒープ(min heap) 根が常に最小となっているヒープ。親ノードは子ノードより常に小さい。 最大ヒープ(max heap) 根が常に最大の要素となっているヒープ。親ノードは子ノードより常に...

プログラミング

アルゴリズム データ構造 ヒープ

2019-12-15 21:47:32

URLルーティング自作入門 エピソード2

概要この記事はURLルーティング自作入門 エピソード1の続きで、Makuake Development Team Advent Calendar 2019の15日目となります。 URLルーティングを自作する前回の続きです。 ルーターを自作するにあたり、ルーターがどういった処理を行うのかデータ構造の観点から考えてみます。 ルーターがどんなInputを受け取って、どんなOutputを返すのか、動的なルーティングの場合の例を図示してみました。 URLのパス部分をInputとして受け取り、パスとマッチするデータを判定してOuputして次の処理につなげる、というのルーターの役割です。 どのようにパスの...

プログラミング

HTTP URLルーティング

2019-12-14 23:20:25

URLルーティング自作入門 エピソード1

概要この記事はMakuake Development Team Advent Calendar 2019の14日目の記事です。 趣味で駆け出し※URLルーティング自作マンをやっているので、URLルーティング自作界隈※に入門したい人に向けた記事となれば幸いです。 ※駆け出しというキーワードが今年はWeb界隈で流行り?ましたね。私は去年末からURLルーティング自作を始めたので駆け出しだと思います。※そんな界隈があるのかは知らないが、世界は広いのでたぶんある。 駆け出しURLルーティング自作マンの軌跡見るに耐えないものではあるが、色々試行錯誤した過程を晒しておきます。 記事 URLルーティングを...

プログラミング

HTTP URLルーティング

2019-12-04 22:30:37

アルゴリズムとデータ構造 - ハッシュテーブル

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ハッシュテーブル ハッシュ値を添え字とした配列 ハッシュの衝突処理 開番地法 衝突が生じた際に、ハッシュ関数とは別の関数を使って別の番地を求める方法。 連鎖法 衝突が生じても新しい番地を求めずに、衝突した番地に衝突したキー同士をポインタでつないだリンクリストを格納することで対応する方式。 計算時間データへのアクセス O(1) 添字を使ってランダムアクセスが可能。 データの追加 O(1) 配列の場合は、線形探...

プログラミング

アルゴリズム データ構造 ハッシュテーブル

2019-11-17 15:30:27

アルゴリズムとデータ構造 - キュー

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 キュー 常に先に追加されたデータからしかアクセスできないようにデータを一列に並べた構造 スタックとは追加と削除の方向が逆になる。 FIFO(First In First Out) 先入れ先出し 待ち行列ともいう。 データの追加をenqueue、削除をdequeueという。 計算時間配列や連結リストなど実装形式による。 実装package main // Queue is a queue. type Queue st...

プログラミング

アルゴリズム データ構造 キュー

2019-11-17 15:28:54

アルゴリズムとデータ構造 - スタック

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 スタック 常に最新のデータからしかアクセスできないようにデータを一列に並べた構造 LIFO(Last In First Out) 後入れ先出し 常に最新のデータへアクセスしたいときに便利な構造 データの追加をPush、削除をPopという。 他にDup、Peek、Swap(またはExchange)、Rotateといった操作がある。 cf. Wikipedia - スタック 計算時間配列や連結リストなど実装形式に...

プログラミング

アルゴリズム データ構造 スタック

2019-11-03 11:03:15

GolangのHTTPサーバーのコードリーディング

概要この記事はQiita - Go6 Advent Calendar 2019の20日目の記事です。 GolangでHTTPサーバーを立てるコードの詳細を追ってコードリーディングします。 参考実装コードリーディングしていく実装はこちら。 package main import ( "net/http" ) func main() { mux := http.NewServeMux() handler := new(HelloHandler) mux.Handle("/", handler) s := http.Server{ Add...

プログラミング

Golang net/http

2019-11-02 20:47:49

アルゴリズムとデータ構造 - 配列

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 配列 データを1列に並べたもの データへのアクセスは容易だが、追加や削除には時間がかかる 配列のデータはメモリの連続した領域に順番に格納される 固定長のメモリを確保する 宣言時に確保(静的確保) 実行時に確保(動的確保) 計算時間配列に格納されているデータ数をnとする。 データへのアクセス O(1) メモリアドレスが添字を使って計算することができるため、データに直接アクセスすることができる。(ランダムアクセス)...

プログラミング

アルゴリズム データ構造 配列

2019-10-18 01:54:54

アルゴリズムとデータ構造 - リスト

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 リスト(線形リストの片方向リスト) データを一直線上に並べた構造 各ノードは次のノードへのポインタを持つ データの追加や削除は容易だが、アクセスには時間がかかる リストでは、データは連続したメモリ領域に格納される必要はない 一般的には離れた領域に格納される 計算時間リストに格納されているデータ数をnとする。 データへのアクセス O(n) データの先頭から順次アクセス(シーケンシャルアクセス)する必要があるため、線形時...

プログラミング

アルゴリズム データ構造 連結リスト 片方向リスト

2019-10-05 20:57:51

FuelPHP1.8.0→1.8.2、PHP5.6→PHP7.3へのバージョンアップした

概要FuelPHP1.8.0→1.8.2、PHP5.6→PHP7.3へのバージョンアップ対応をした。業務でアプリケーションのバージョンアップ対応を行ったので、取り組みをまとめておく。 スコープ FuelPHP1.8.0 → FuelPHP1.8.2 PHP5.6 → PHP7.3 対象リポジトリ ユーザー側アプリケーション 管理側アプリケーション パッケージリポジトリ ※ミドルウェアのバージョンとかは割愛※OSはAmazon Linux(2ではない) FuelPHP1.8.0はPHP7.2まで対応しているが、1.8.2は7.3まで対応している。 バージョンアップに取り掛かる2週間くらい前...

プログラミング

PHP FuelPHP

2019-09-25 09:36:59

A Trie implementation in Golang

概要トライ木のアルゴリズムと実装についてかく。 bmf-san/road-to-algorithm-master  トライ木とはトライ木(プレフィックス木ともいう。英語はそれぞれ、trie、prefix tree)は文字列の集合を扱う木構造の一種。 各ノードは単一または複数の文字列あるいは数値を持ち(ノードは必ずしも値を持つ必要はない)、根ノードから葉に向かって探索して値をつなげていくことで単語を表現する。 ネットワークのレイヤーならIPアドレスの探索、アプリケーションレイヤーならhttpのルーティングに、機械学習とかの文脈であれば形態素解析といったところでトライ木の応用が見受けられる。 言葉...

プログラミング

Golang アルゴリズム 基数木 トライ木

2019-08-18 18:05:25

Dive to clean architecture with golang

概要GolangでClean Architectureの実装に挑戦したみたので整理しておく。 内容は概ねスライドの内容を踏襲している。 理解しきれていないところがあったり、自分の解釈、考えを記述しているので、正しくない部分もあるかもしれない。 スライドLTをする機会があったのでスライドを貼っておく。 Dive to clean architecture with golang ソースソースはこれ。 bmf-san/go-clean-architecture-web-application-boilerplate MVCのパターンでの実装もtagを切って残してある。 1.0.0 - MVC 背景...

プログラミング

Clean Architecture Golang DIP