連結リストのランナーテクニック
2023年7月22日連結リストの走査で役立つランナーテクニックについてまとめる。 世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法で紹介されていて初めて知った。 ランナーテクニックとは 連結リストの先頭から走査していくポインタと、そのポインタより先から走査していくポインタの2種類を用意して、同時に走査していく方法。 これが何に役立つかというと、例えば次のような例題を解くのに役立つ。 例題 単...
連結リストの走査で役立つランナーテクニックについてまとめる。 世界で闘うプログラミング力を鍛える本 ~コーディング面接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...
概要 トランザクションについてまとめる。 トランザクション データを正しく保つための手法。DB固有の概念ではなく、一つの理論として独立している。 多数のクライアントからDBサーバーに対して同時アクセスが発生するような状況や、DBサーバーまたはアプリケーションが更新処理途中にクラッシュするという状況などからデータの整合性を守りたい時に必要とされる。 トランザクションが提供する機能は2点ある。 同時...
概要 Google Cloud認定アソシエイトクラウドエンジニアを受験して合格したので、再受験するときや別の試験を受けるときのために勉強した過程を振り返っておく。 前提 ソフトウェアエンジニア7~8年目くらい。 GCPの経験は2年くらいあるかな・・どちらかというとAWSのほうが触っている感じ。 モチベーション 業務でAWSとGCPの両方を触る機会があり、AWSの方はアソシエイトレベルの認定を取得し...