Carpe Diem

備忘録

アルゴリズム

基数木を使った効率的なパスルーティング

背景 次のようなwildcardを含んだpathをフレームワークに頼らず、自前で実装する場合にどうパターンマッチさせるか考えてみます。 /users/:id /articles/:id/comments 単純に考えると正規表現で次のようなパターンを使ってforループで回す、といったものがあ…

Goでバンディットアルゴリズムを実装する

概要 複数の案を試す際にA/Bテストがありますが、検証期間中はずっと同じ割合で試行しなければいけないため、もし悪い案であった場合に全体としてその期間損失を生むことになります。 そのような損失を少なくしつつ、良いと思われる案を優先的に試行するアル…

重み付き乱択を行う

概要 重み付き乱択アルゴリズムは結果に偏りのある抽選で ソシャゲのガチャのようにレアリティによって出現確率を変えたい リクエストを重み付けして分散したり、A/Bテストで99:1のように振り分けたい といった用途で使えます。 今回はその説明と実装方法の…

Consistent Hashing (コンシステントハッシュ法)

Consistent Hashingとは Consistent Hashingはハッシュテーブルアルゴリズムの1つです。 ハッシュテーブルのサイズの変更をしても柔軟にマッピングできるため、ノードの追加・削除が発生する分散データベースやキャッシュの保存先を決定するといった用途に…

check digitを使った誤り検出

概要 クレジットカード・シリアルナンバーなど、長くなるほど入力ミスはしやすくなります。 そんな時に毎回DBに問い合わせて正しい値かをチェックするのではなくアルゴリズムによって正しいものかどうかチェックする仕組みがcheck digit(チェックディジット…

様々なrate limitアルゴリズム

概要 インターネットに晒されているWebサービスでは TV等で紹介されたことによる大量流入 悪意ある人物からの攻撃 クライアントのバグに依る大量リクエスト など、本来想定していた以上のトラフィックが来ることはよくあります。 単純にシステムを構築すると…

B TreeとB+ Treeの違い

概要 インデックスに対してMongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しています。 どうして採用しているアルゴリズムが違うのだろう?と思って調べてみました。 主な違い B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。 リーフ…