Post

プログラミング

New!

2020-01-15 22:40:24

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

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

プログラミング

Algorithm Data structure binary search tree

New!

2020-01-14 22:04:54

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

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

プログラミング

Algorithm Data structure 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) 配列の場合は、線形探...

プログラミング

Algorithm Data structure hash table

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...

プログラミング

Algorithm Data structure queue

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 - スタック 計算時間配列や連結リストなど実装形式に...

プログラミング

Algorithm Data structure stack

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) メモリアドレスが添字を使って計算することができるため、データに直接アクセスすることができる。(ランダムアクセス)...

プログラミング

Algorithm Data structure array

2019-10-18 01:54:54

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

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

プログラミング

Algorithm Data structure linked list singly linked list

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 Algorithm prefix tree trie

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

2019-05-08 17:05:41

execコマンドによるリダイレクト

概要execコマンドは現在のプロセスを実行するコマンドで置き換えるコマンドだが、引数無しで使うとリダイレクトの動的変更ができる。 ちょうどmaster直プッシュの際にプロンプトで確認するようにするで #!/bin/sh exec < /dev/tty read ANSWER というコードが出てきてよくわからなかったので調べてみたのがきっかけ。 使い方#!/bin/sh echo "Output to stdout" // 標準入力 exec > redirect.txt // ファイルディスクリプタを変更 echo "Output to file" // ファイルに出力される...

プログラミング

bash shellscript exec

2019-05-08 17:04:11

master直プッシュの際にプロンプトで確認するようにする

概要gitでmasterブランチへの直pushを未然に防ぐためのセーフーティネットの作り方。github上でmasterブランチへのpushを禁止すれば良いのだが、DevOpsの都合上でgithubの設定では問題があったのでhooksを使う方向で設定した。 導入グローバルに設定したいので~/.git_template/hooks配下にpre-pushファイルを作成する。.git_templateディレクトリが存在しない場合は作成する。 なお、グローバルに設定しても既存のリポジトリには反映されないので、既存リポジトリに反映したい場合は既存リポジトリの./git/hooks配下にpre-pushを...

プログラミング

Git shellscript

2019-04-21 00:05:50

PHPで学ぶデザインパターン - Stateパターン

概要PHPで学ぶデザインパターン Advent Calendar 2018で間に合わなかった記事。 Stateパターンとは状態をクラスで用意することで振る舞いを切り替えることができるようなパターン。 実装スイッチのオンオフの状態を切り替えるような例を想定した。シングルトンを使ったほうが良い気がする。 <?php class OnState { public function getState() { return 'ON'; } public function getNextState() { return ne...

プログラミング

GoF PHP デザインパターン State

2019-04-20 14:24:47

ゴリラで学ぶソフトウェアの法則10選

概要以前書いたソフトウェア開発の法則 の雑メモをベースにLTをしたのでスライド内容を補足する形でまとめる。 スライドは↓ゴリラで学ぶソフトウェアの法則10選 ゴリラで学ぶには無理があったのでスクリプトを書き残しておく。 ソフトウェア開発の法則ソフトウェアの文脈で語られる法則に縛らず、他分野での法則でもソフトウェアに当てはまるであろうものを”ソフトウェア開発の法則”としている。 経験則に基づくものが多いが、経営工学だったり心理学だったり、はたまたどこかの論文だったり引用元は様々である。 パーキンソンの法則(第1原則)「仕事の量は、完成のために与えられた時間を全て満たすまで増大する」 有名ど...

プログラミング

ソフトウェア開発

2019-04-11 15:09:57

Realizeを使ってgoでホットリロードを実現するメモ

概要github - oxequa/realizeを使ってみたメモ。 準備go get github.com/oxequa/realize 使い方./demo/ ├── .realize.yaml └── main.go .realize.yaml settings: legacy: force: false interval: 0s schema: - name: demo path: . commands: run: status: true watcher: extensions: - go paths:...

プログラミング

Golang realize

2019-03-24 21:58:28

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

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

プログラミング

PHP URLルーティング HTTP Algorithm 木構造

2019-02-11 12:42:49

Laravelでの機能テストの始め方雑メモ

概要Laravelでの機能テストの始め方と簡単な使い方について紹介する。入門レベルに限るのでより実践的な内容については触れない。※LTの元ネタ程度でメモくらいの内容。 対象テストを書いたことがない人向け。 テストを書いたことがなくても機能テストであればアプリケーションの仕様さえわかっていれば比較的に誰にでも楽に何を書くのかわかりやすいと思う。 特にLaravelは機能テストで使える便利なAPIやツールが充実しているので、テストに慣れていなくともテストに取り組みやすいはず。 環境 Docker Laravel5.7 MySQL 準備雑に環境を用意しておいた。 github - bmf-san/...

プログラミング

Laravel 機能テスト