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
2020-01-05 21:18:26
概要トランザクションについてまとめる。
トランザクションデータを正しく保つための手法。DB固有の概念ではなく、一つの理論として独立している。
多数のクライアントからDBサーバーに対して同時アクセスが発生するような状況や、DBサーバーまたはアプリケーションが更新処理途中にクラッシュするという状況などからデータの整合性を守りたい時に必要とされる。
トランザクションが提供する機能は2点ある。
同時実行制御
同時アクセスによって発生し得るデータ不整合を防ぐこと。
クラッシュリカバリ
DBサーバーやアプリケーションがクラッシュしても自動的にリカバリ処理が行われること。
データ不整合を起こさな...
データベース
トランザクション
2019-12-21 12:40:46
2019年の振り返りと来年の抱負今年も残すところ1週間とちょっとくらいになったので、今年の振り返りと来年の抱負をポエムっとく。
今年の振り返りここ3年間くらい右肩上がりで公私ともに良い機会、良い経験に恵まれている。今年は特に良い年だったと思う。めんどくさいので雑に箇条書きにしていく。
パブリックな方面個別の事柄をピックアップして書きたいけど、多すぎて大変面倒なことになるので総括だけ。
リードエンジニアっぽい役回りを経験することができた。
これはすごく単純な言い方だが、チームワークというのがいかに大切で、outcomeに大きな影響を与えるのかということを学んだと思う。 これまでは個に目が向いて...
ポエム
No Tags.
2019-12-15 21:47:32
概要この記事はURLルーティング自作入門 エピソード１の続きで、Makuake Development Team Advent Calendar 2019の15日目となります。
URLルーティングを自作する前回の続きです。
ルーターを自作するにあたり、ルーターがどういった処理を行うのかデータ構造の観点から考えてみます。
ルーターがどんなInputを受け取って、どんなOutputを返すのか、動的なルーティングの場合の例を図示してみました。
URLのパス部分をInputとして受け取り、パスとマッチするデータを判定してOuputして次の処理につなげる、というのルーターの役割です。
どのようにパスの...
プログラミング
HTTP
URLルーティング
2019-12-14 23:20:25
概要この記事は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-12-06 00:05:38
概要2019年に日本国内で開催された全ての公式PHPカンファレンスにしたので参加記録をまとめる。
PHPカンファレンス参加レポートまとめ仙台に始まり、東京で終わるまでの道のり。東京以外のカンファレンスは全て初参加。
PHPカンファレンス仙台2019に参加した
Laravel JP Conference国内初開催のLaravelカンファレンス。スタッフ兼スピーカーとして参加した。来年度もスタッフとして参加予定。cf. Laravel JP Conference 2020
PHPerKaigi2019に参加・登壇してきました
PHPカンファレンス福岡2019に参加・登壇してきました過去2回くらい...
ポエム
PHP
PHPカンファレンス
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