スタックとキューの実装
2023年7月25日Goでスタックとキューをそれぞれ実装してみた。 スライスを使ったパターンと連結リストを使ったパターンをそれぞれ実装している。 個人的にはスライスを使ったパターンの方が実装は楽かなと思う。 スタックのpush、pop、キューのenqueue、dequeueの時間計算量はそれぞれO(1)で実装できるが、一部サボってO(N)になってしまっているものがある。 スタック ソースコード：stack 連結リスト...
Goでスタックとキューをそれぞれ実装してみた。 スライスを使ったパターンと連結リストを使ったパターンをそれぞれ実装している。 個人的にはスライスを使ったパターンの方が実装は楽かなと思う。 スタックのpush、pop、キューのenqueue、dequeueの時間計算量はそれぞれO(1)で実装できるが、一部サボってO(N)になってしまっているものがある。 スタック ソースコード：stack 連結リスト...
連結リストの走査で役立つランナーテクニックについてまとめる。 世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法で紹介されていて初めて知った。 ランナーテクニックとは 連結リストの先頭から走査していくポインタと、そのポインタより先から走査していくポインタの2種類を用意して、同時に走査していく方法。 これが何に役立つかというと、例えば次のような例題を解くのに役立つ。 例題 単...
再帰処理はプログラマーの嗜み！エレガントにかけて当たり前！・・・と自信を持って言いたいところだが、自分は正直なところ苦手である。 日頃再帰処理を書く機会といえばコーディングクイズくらいで実際のところあまり書く機会がない.. 再帰処理はケースによってはメモ化や末尾最適化までエレガントにやらないと計算量が大きくなったり、メモリを食うだけのコードになってしまうが、アルゴリズムによってはシンプルなコードに...
概要 コーディングクイズを解く日課を再開するに当たって、リハビリを兼ねてアルゴリズムとデータ構造の基本について復習。 配列 連続した配置でメモリを確保する 単一のデータ型 サイズは一般的には固定だが、言語によっては動的（可変長配列） サブアレイ 配列内から連続した形で取り出される配列 [1, 2, 3, 4, 5] →[2, 3, 4] サブシーケンス 要素順を変更せずに、一部の要素...
カウントソートとは ソートアルゴリズムの中でも比較を使わずにソートする変わった？アルゴリズム。 比較せずに要素をカウントすることでソートができる。 カウントしてソートすることができるというのは不思議！と思ったので調べてみた。 前提 累積和について知っておく必要がある。 cf. qiita.com - 累積和とは（超初心者用） 実装 ソースコードは以下。 count_sort package mai...
プログラミング脳をこれから鍛える本を読んだ。 算数を題材として思考法についてトレーニングが書かれた本。内容は平易で大人向けではないかもしれない。 ...
バックトラッキングとは 指定された制約を満たすような組み合わせを探索するアルゴリズム。 重複しない組み合わせ（nCr）を全て探索するようなときに使える。 実装 ソースコードは以下。 backtrack 与えられた配列からN個の重複しないサブシーケンスを取得する処理。 以下は4C3の例。 package main import "fmt" func backtrack(rs...
Makuake Advent Calendar 2022の9日目の記事です！ Goで始めるコードのパフォーマンス改善 自作HTTP Routerのgoblinのパフォーマンス改善をしよう思った際に、Goのパフォーマンス改善について取り組んでみたので、その際のアプローチと実践した取り組みについて書く。 前提知識 より奥深いチューニングをする上ではもっと必要な知識があると思うが、最低限必要なことだけリ...
概要 MySQLのトランザクションのアノマリーについてまとめる。 MySQLのバージョンは8系を想定する。 検証環境 検証に使う環境はdocker-composeで用意した。（1コンテナだけなのでcomposeを使わなくも良いのだが..） . ├── docker-compose.yml └── initdb.d └── 1_schema.sql docker-compose.yml v...