記事

アルゴリズムとデータ構造の基本の復習

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

概要 コーディングクイズを解く日課を再開するに当たって、リハビリを兼ねてアルゴリズムとデータ構造の基本について復習。 配列 連続した配置でメモリを確保する 単一のデータ型 サイズは一般的には固定だが、言語によっては動的(可変長配列) サブアレイ 配列内から連続した形で取り出される配列 [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...

バックトラック

スライディングウィンドウの実装

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

スライディングウィンドウとは 配列のサブアレイを”ウィンドウ(サブセット)”をずらすしていくように探索するアルゴリズム。 ウィンドウサイズは固定または動的。 実例としては、レートリミッターで使われたりする。 実装 ソースコードは以下。 sliding_window 与えられた配列から合計がN以上になるサブアレイを探索する関数。 package main import "fmt&quot...

スライディングウィンドウ

ソフトウェアアーキテクトの振る舞いについて

ポエム

1~2年くらいに前に読んだDesign Itを読み直していたら、ソフトウェアアーキテクトとして果たすべき役割や責任について学び得ることがあったので、メモを残す。 お気持ちも交えつつ書くのでこれはポエム。 ソフトウェアアーキテクトは何をする人なのか? ソフトウェアアーキテクトはコードも書くし、プロジェクトのリードもするし、ビジネス的な視点でも思考を巡らせたりもする。 ビジネス・技術・ユーザーの3つの...

アーキテクト

MySQLのロックについて

データベース

概要 MySQLのロックについてまとめる。 MySQLのバージョンは8系を想定する。 検証環境 検証に使う環境はdocker-composeで用意した。(1コンテナだけなのでcomposeを使わなくも良いのだが..) . ├── docker-compose.yml └── initdb.d └── 1_schema.sql docker-compose.yml version: &#x...

MySQL トランザクション ロック

MySQLのトランザクションのアノマリーについて

データベース

概要 MySQLのトランザクションのアノマリーについてまとめる。 MySQLのバージョンは8系を想定する。 検証環境 検証に使う環境はdocker-composeで用意した。(1コンテナだけなのでcomposeを使わなくも良いのだが..) . ├── docker-compose.yml └── initdb.d └── 1_schema.sql docker-compose.yml v...

トランザクション MySQL

モニタリングシステムにおけるPull型とPush型のアプローチの違い

インフラストラクチャ

概要 モニタリングのシステムにおけるPull型とPush型のアプローチの違いについてまとめる。 Pull型 監視サーバー側で監視対象ホストについて設定をし、監視サーバーから監視ホストにデータを取得しにいく。 ex. Prometheus、Nagios、Zabbixなど PrometheusはPull型の欠点を補うかのように、exporterというPush型のようなアプローチのような仕組みがある。e...

モニタリング

キャッシュの書き込み方式

インフラストラクチャ

概要 キャッシュの書き込み方式についてまとめる。 ライトスルー データがキャッシュに書き込まれると同時にメインメモリにも書き込む方式。 書き込み操作がキャッシュとメインメモリ両方に対して発生する。 データの一貫性を保ちやすいが、書き込みの遅延が発生する可能性がある。 ライトバック データがキャッシュに書き込まれた後、メインメモリに書き込みをするまでキャッシュ内にデータが保持される方式。 書き込み操...

キャッシュ

シャーディングとパーティショニングの違い

データベース

概要 時々どっちがどっちか混乱してしまうので、メモを残す。 シャーディングとパーティショニングの違い 項目 シャーディング パーティショニング データの分割方法 水平方向(≒水平パーティショニング) ex. 行 垂直方向 ex. テーブル、データベース、カラム メリット パフォーマンスの向上、スケーラビリティの向上 パフォーマンスの向上、データの検索性向上 デメリット データや...

パーティショニング シャーディング