Skip to content

Instantly share code, notes, and snippets.

@showa-93

showa-93/!Algorithm.md

Last active October 2, 2023 17:03
Show Gist options
  • Save showa-93/1ff2c1488c358bb2b924720696116dc2 to your computer and use it in GitHub Desktop.
Save showa-93/1ff2c1488c358bb2b924720696116dc2 to your computer and use it in GitHub Desktop.
Download ZIP
Algorithm
Raw
!Algorithm.md
Raw
dp---!dp.md
title type weight lastmod
動的計画法
docs
1
{"lastmod"=>nil}
Raw
dp---ナップサック問題.md
title type weight lastmod
ナップサック問題
docs
1
{"lastmod"=>nil}

TBD

Raw
dp---循環するケース.md
title type weight lastmod
循環するケース
docs
1
{"lastmod"=>nil}

ある順列の１番目とn番目が隣接し、循環している場合のDPに関してまとめる。

問題

  • ABC285 E - Work or Rest
    • 過去にやってた
  • ABC307 E - Distinct Adjacent
    • 循環の起点となる1番目だけ注目し、１番目と同じかどうかの２パターンの個数を考えることで簡単にしている。
      • i-1番目が1番目と同じ → i番目はm-1とりうる
      • i-1番目が1番目と同じでない → 1番目と同じはとれないかつ隣と同じ数字はとれないのでi番目はm-2とりうる
Raw
graph---!graph.md
title type weight lastmod
Graph
docs
1
{"lastmod"=>nil}
Raw
graph---ダイクストラ法.md
title type weight lastmod
ダイクストラ法
docs
1
{"lastmod"=>nil}

単一始点最短経路問題(SSSP)を解くためのアルゴリズムのひとつ。
ベルマンフォード法($O(|E|\times|V|)$)よりも高速に動作できる一方、グラフに負の辺がある場合利用できない。(性質上最短経路を確定できなくなる)

[実装 https://go.dev/play/p/dSjWm_VlUUi]

始点を始点からの最短経路がゼロと確定した頂点とし、他の頂点を未確定の頂点(始点からの距離が十分に大きい)とする。
最短経路が確定した頂点と最短経路が未確定の頂点との間の辺とその重みを集計し、重みが最小の辺につながる頂点を最短距離が確定した頂点とする。この条件が成立するのは負の辺が存在しない場合である。負の辺がなければ最短経路になるのは最小の重みの辺であることが一意にわかる。

愚直にすべての頂点に対して最短となる辺をすべての頂点で探索した場合、計算量は$O(|V|^2)$となる。
ヒープや優先度付きキューなどを使った場合、最短距離となる辺の探索が$O(log|V|)$で計算でき、これを辺の数だけその探索をおこなう。
このときの計算量は$O(|E|log|V|)$となり、辺の数が小さければ高速に動作する。

問題

参考

Raw
graph---トポロジカルソート.md
title type weight lastmod
トポロジカルソート
docs
1
{"lastmod"=>nil}

閉路のない有向グラフの辺が左から右に向くように頂点を左から右に一列に並べるソートのこと。
グラフがトポロジカルソート可能であるということは、そのグラフがDAGであることと等価。
物事の依存関係や因果関係などをモデル化するのに有効。MakefileやJOB Scheduleなどがある。

実装

トポロジカルソートの実装にはBFSまたはDFSを利用して実装できる。どちらの場合でも計算量は$O(|E|+|V|)$（E=辺、V=頂点）となる。

BFSを利用した場合

幅優先探索を利用する場合、各頂点の入次数を記録しておきます。
入次数がゼロの頂点がトポロジカルソートの開始位置となる。この頂点からBFSで探索を行います。
頂点から辺を辿って各頂点を見つけるたびに入次数を減らし、入次数がゼロになったものが次にBFSをおこなう頂点となる。

DFSを利用した場合

適当な頂点から探索を開始する。末尾まで探索が終わった後に頂点をたどるときの順番(帰りがけ順 postorder)の逆順がトポロジカルソートした結果となる。
前述の探索でまだ未チェックの頂点があれば同様の探索を繰り返すことでグラフのトポロジカルソートができる。

閉路検出

トポロジカルソートはその性質からトポロジカルソートができない＝グラフに閉路が存在することを確認できる。
BFSを利用している場合、すべての探索をおこなった場合、入次数がゼロにならない頂点が存在する。
DFSを利用した場合、すでに訪問したアクティブな頂点に再度訪問した場合、そのグラフに閉路が存在することを検出できる。

参考

Raw
graph---ベルマン-フォード法.md
title type weight lastmod
ベルマン-フォード法
docs
1
{"lastmod"=>nil}

単一始点最短経路問題(SSSP)を解くためのアルゴリズムのひとつ。
ダイクストラ法より計算量は大きいが負の辺が含まれていても利用ができる。また、負の閉路が存在する場合検出することも可能。

実装

いずれかの頂点で最短距離が更新されなくなるか、$|V|$回目の更新が終わるまで繰り返す。
最短距離を更新する処理はすべての辺に対して、辺の終点の$v$の最短距離より辺の始点の$u$の最短距離+辺の重みのほうが小さい場合、最短距離を更新する。

$$d[v] = min(d[u] + 辺eの重み)$$

１回の更新で少なくとも１つの頂点の最短距離が決まるため、始点となる頂点を除いた$|V|-1$回の更新で最短距離が求まる。
グラフ上に負の閉路が存在する場合、最短距離の更新が必ず発生するため、$|V|-1$回の更新で終わらない。よって、$|V|$回更新された場合、負の閉路が存在することがわかる。

すべての頂点の最短経路がわかるまですべての辺の走査を$|V|-1$回の更新を繰り返すため、計算量は$O(|V| \times |E|)$となる。

距離の最大化

最短距離ではなく最大化したい場合、グラフの辺に$-1$をかけることで最大化を計算できる。
これは負の辺が存在しても計算できるために利用できる方法。ダイクストラではこの方法は適用できない。

問題

参考

Raw
graph---ワーシャルフロイド法.md
title type weight lastmod
ワーシャルフロイド法
docs
1
{"lastmod"=>nil}

TBD

Raw
graph---巡回セールスマン問題.md
title type weight lastmod
巡回セールスマン問題
docs
1
{"lastmod"=>nil}

Traveling salesman problem, TSP

都市の集合と各2都市間の移動コストが与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める組合せ最適化問題である。
wikiより抜粋

NP困難とよばれる問題。多項式時間で解けるアルゴリズムがみつからず計算量的に解くのが困難な問題。
すべての経路を計算する場合、$O(n!)$のため、都市数が20以上の場合、現実的な範囲でなくなる。

解法

bit DP

集合に対する動的計画法のひとつ。$n$個のものに対して$n!$通りの順序の中から最適なものを求めるときに使える。
巡回セールスマン問題で巡回する集合の部分集合Sを巡回する $\mid S \mid!$通りの経路のうち最短のものの距離のうち、最後に頂点vに到達したときのみ考える。
頂点uからvまでの距離を $cost(u,v)$ とすると以下のようになる。
計算量は $O(2^nn^2)$程度になる。

$$dp[S \cup {v}][v] = \min_{u \in S}(dp[S \cup {v}][v], dp[S][u] + cost(u, v))$$

問題

参考

Raw
graph---強連結成分分解.md
title type weight lastmod
強連結成分分解
docs
1
{"lastmod"=>nil}

強連結とは、有向グラフ$G$の部分集合$S$の任意の２頂点を選んだとき、頂点同士が互いに行き来可能であることである。
部分集合$S$にほかの頂点集合を付け加えても強連結にならないとき、部分集合$S$は強連結成分(SCC, Storongly Connected Component)である。
有向グラフを強連結成分となる部分集合ごとに分解することを強連結成分分解と呼ぶ。

強連結成分部分を頂点とみなすと非DAGをDAG(有向非巡回グラフ)とみなして走査できるようになる。

実装

有向グラフ$G$をDFSで探索し帰りがけに頂点を番号でラベリングする。これを未探索の頂点がなくなるまで繰り返す。
辺の方向を逆向きにした$G^T$を一番大きい番号の頂点から探索する。探索が完了した頂点の集合が1つのSCCとなる。
未探索の頂点がなくなるまで探索することですべてのSCCをみつけることができる。
２回目のグラフ探索が逆グラフを探索するのは、最大番号の頂点は逆グラフだと最下流になるため、元のグラフにおける下流の連結成分まで誤って連結成分として探索してしまうことがなくなる。

計算量は頂点と辺に線形で $O(|E|+|V|)$。

問題

参考

Raw
graph---超頂点.md
title type weight lastmod
超頂点
docs
1
{"lastmod"=>nil}

すべての集合をそのまま頂点としたグラフにするとN個の頂点の数だけ変数ができ、$O(N^2)$となるため、コストの計算が間に合わない。
そこで集合の内容の頂点とそれらをまとめる集合をあらわす頂点（超頂点）を用意しグラフを作成する。
超頂点を利用することで各集合間のつながりが超頂点を介するようになるので、辺の数が$\sum A$となり探索可能な範囲まで辺を減らすことができる。

問題

参考

Raw
hash---!hash.md
title type weight lastmod
ハッシュ関数
docs
1
{"lastmod"=>nil}

任意長のメッセージに対して、メッセージを代表する固定長の値を出力する関数。ハッシュ関数の出力する固定長の値をハッシュ値と呼ぶ。
同じハッシュ関数に同じメッセージが入力された場合、同じハッシュ値が出力されなければならない。さらに入力のメッセージのサイズに問わず高速に計算できることが求められます。

完全ハッシュ関数

ハッシュ関数が単射(→必ず唯一の値に射影される)で正しい入力に対して必ず異なるハッシュ値が一意に定まる場合のハッシュ関数を完全と呼ぶ。１つのハッシュテーブルで目的のデータを直接探すことができる。入力の範囲がわかっており変化しない場合に成立する。
n個のキーに対してn個の連続する整数がハッシュの値域となる場合、最小完全ハッシュ関数と呼ぶ。参照の単純化と無駄なデータ領域が発生しないのでコンパクトになる。
完全ハッシュ関数が有効なケースは

  • 更新が無い莫大なkey、valueのデータセット
  • keyの探索(lookup)が高頻度

安全性

暗号学的ハッシュ関数の安全性は以下の３種類の性質で議論される。

  • 原像計算困難性（一方向性）
    与えられたハッシュ値の元のメッセージを求めることが困難である性質。逆計算が困難な関数を一方向性関数と呼ぶ。
    この一方向性を破ろうとする攻撃のことを原像攻撃と呼ぶ。同じハッシュ値が得られるメッセージを出力することが目的の攻撃です。

  • 第２原像計算困難性
    メッセージ（第１原像）とそのハッシュ値を与えられたとき、同じハッシュ値を出力するメッセージ（第２原像）を求めることが困難である性質。

  • 衝突困難性
    同じハッシュ値になるような２つのメッセージを求めることが困難である性質。
    ハッシュ関数が出力するハッシュ値は、入力のメッセージより要素数が小さくなるため、同じハッシュ値をもつメッセージが存在する。
    この同じハッシュ値が出力される現象をハッシュ値の衝突と呼ぶ。また、衝突した２つのメッセージを衝突ペアと呼ぶ。

安全性の強弱

第２原像計算困難性を破ることと衝突困難性を破ることを比較した場合、衝突困難性を破る方が実現しやすい。特定のハッシュ値の衝突より任意のハッシュ値の衝突のほうが条件がゆるいため。
攻撃が容易な性質を防ぐ方が安全性が強いため、衝突困難性のほうが安全性が高い。
衝突困難性を持つならば、異なる２つのメッセージが同じハッシュ値を持つことが困難であるため、ハッシュ値から元のメッセージの復元が困難である。
よって、衝突困難性を持つならば原像計算困難性をもつため、衝突困難性のほうが安全性が強いと言える。

安全性評価

アルゴリズムの安全性を表す指標としてセキュリティビットが用いられる。あるアルゴリズムに対して必要な攻撃の計算量が$2^n$のとき、そのアルゴリズムの安全性はnビットセキュリティという。
前述の安全性に対する総当り攻撃による計算量は次の表のようになる。

安全性の種類 計算量 ビットセキュリティ
原像計算困難性（一方向性） $2^{n-1}$ $n$
第２原像計算困難性 $2^{n-1}$ $n$
衝突困難性 $2^{n/2}$ $n/2$

その他の安全性

  • 近似衝突困難性
    よく似たハッシュ値をもつ２つの異なるメッセージを特定が困難である性質。
  • 部分原像計算困難性
    一部が不明なメッセージとそのハッシュ値から不明な一部を特定することが困難である性質。

ハッシュ関数の構成

反復型ハッシュ関数

  • Miyaguchi-Preneel構造
  • Merkle-Damgård構造
  • Davies-Meyer構造

Sponge構造

攻撃

誕生日攻撃

バースデーパラドックスを利用した攻撃。

バースデーパラドックスとは、「何人集まれば誕生日の一致するペアが存在するか」という問題（誕生日問題）を考えたときの直感の確率と数学的事実の乖離についてのパラドックです。
n個の箱にq個のボールを入れるとき$q=\sqrt{n}$のときに同じ箱に２個以上入る確率は0.3以上であることが知られている。特に$q=1.18\sqrt{n}$のときの確率は0.5以上となる。
これを誕生日問題についてあてはめると20人$(\sqrt{365})$で0.3という確率で一致するペアが存在する。また、24人$(1.18\sqrt{365})$集まれば$1/2$の確率になる。

前述の内容をハッシュ関数の世界で考えると、ハッシュ値がkビットとすると$2^k$通りの箱が存在する。
先程の数学的事実より$q=\sqrt{2^k}=2^{k/2}$回計算すると0.3以上の確率で衝突ペアが求まる。

伸長攻撃（Length Extension Attack）

$H$をMD5やSHA1などの反復型ハッシュ関数としたときに、$H(m_1)$から$H(m_1||m_2)$を求める攻撃のことを伸長攻撃と呼ぶ。
既知のハッシュ値とメッセージから未知のSALTを先頭に結合されたメッセージのハッシュ値でも攻撃者が任意のメッセージを付与した新しいハッシュ値を計算することができる。

反復型ハッシュ関数では入力のメッセージをブロックに分けてブロックごとに処理をする。メッセージのビット数がブロックのサイズの倍数でない場合、メッセージの最後にパディングが付け足される。
最初のブロックで初期ベクトルⅣを与えブロックを処理する。計算した結果を順番に並べた結果がハッシュ値となるがブロック数が多い場合、前回計算したハッシュ値を初期ベクトルⅣとして同様の処理をする。
つまり、一つ前のブロックのハッシュ値がわかればメッセージを追加したハッシュ値を計算することが可能であることがわかる。

伸長攻撃では次のような攻撃に利用できる。（By ChatGPT4）

  • データ改ざん：既知のハッシュ値とメッセージに追加のデータを付加して、新しいハッシュ値を計算することができる。
  • メッセージの偽装：新しいハッシュ値を使用して偽のメッセージを送信することができる。
  • 認証の回避；新しいハッシュ値を使用して認証を回避することができます。
  • 署名の偽造: 新しいハッシュ値を使用してデジタル署名を偽造することができる。

HashDoS攻撃

ハッシュテーブルの脆弱性を利用したWebアプリケーションのCPU資源を枯渇させるサービス妨害攻撃。
ハッシュテーブルのハッシュ値が衝突するような多くの異なるキーがテーブルにマップされているとハッシュテーブルに対するあらゆる操作の計算量が単純なリンクトリストの操作まで落ちる。
これを利用してHTTPのリクエストの処理にハッシュテーブルを利用しているようなサーバーに対して、ハッシュ値がおなじになるキーを大量にリクエストのパラメータに含ませることでⅠ回のPOSTリクエストでCPUを枯渇させます。

暗号学的ハッシュ関数

MD5

SHA1

SHA2

SHA3

Whirlpool

非暗号化ハッシュ

Division Method

Multiplication Method

Universal Hashing

Lookup3

MurmurHash

ハッシュベースの検索向けのハッシュ関数である。2008年にAustin Applebyによって作成された。名前は内部ループで使用される2つの基本演算、乗算（MU）と回転（R）に由来する。

最新のバージョンはMurmurHash3である。32bitまたは128bitのハッシュ値を生成する。128bitの場合、プラットフォームごとに最適化されているためx86とx64では同じ値が得られない。MurmurHash2は32bitまたは64bitのハッシュ値を生成する。多くのバリエーションがあり、オリジナルの修正版のMurmurHash2Aやインクリメンタルに動作するCMurmurHash2A、x64に最適化されたMurmurHash64Aなどがある。MurmurHash1はLookup3より高速な関数を作る試みとして作られた。MurmurHash1ではLookup3のように64bitのハッシュ値を生成できなかった。

MurmurHashは衝突攻撃に脆弱な可能性がある。ランダムなシート値をつかった実装でもHashDoS攻撃に対して脆弱であることが示されている。

MurmurHash3の実装は、以下のステップで構成されています。Goによる実装

  1. 初期化: ハッシュ関数は、初期ハッシュ値としてシード値を受け取ります。このシード値は、異なるハッシュ値を生成するために変更することができます。
  2. ブロック処理: 入力データは、固定サイズのブロックに分割されます。各ブロックは、ハッシュ関数によって個別に処理されます。ブロックのサイズは、x86アーキテクチャでは4バイト、x64アーキテクチャでは16バイトです。
  3. ミキシング: 各ブロックは、ビットシフト、ビットXOR、乗算などの操作を使用してミキシングされます。これにより、ハッシュ値の分布が均一になります。
  4. 結合: ミキシングされたブロックは、初期ハッシュ値と結合されます。これによりハッシュ値が生成されます。
  5. 最終処理: 最後のブロックが処理された後、ハッシュ値は最終処理ステップを経て、最終的なハッシュ値が生成されます。

CityHash

FNV (Fowler-Noll-Vo) Hash

Jenkins Hash Function

参考

Raw
hash---bloomfilter.md
title type weight lastmod
Bloom Filter
docs
1
{"lastmod"=>nil}

TBD

Raw
hash---hashtable.md
title type weight lastmod
ハッシュテーブル
docs
1
{"lastmod"=>nil}

キーと値の組（エントリ）を格納し、キーに対応するあ愛を高速に参照するためのデータ構造。
ハッシュテーブルはキーをもとに生成したハッシュ値を添え字とした配列。キーを要約するハッシュ値を添え字として管理することでデータ量によらず定数時間$O(1)$の検索を実現している。
衝突しやすいハッシュ関数など選んだハッシュ関数によっては最悪の場合$O(n)$となる。

ハッシュ関数

ハッシュテーブルで利用されるハッシュ関数は、高速であり、入力データに対して均等に分散されたハッシュ値を生成することが求められます。（simple uniform hashing）以下は、ハッシュテーブルでよく利用されるハッシュ関数の一部です。(By ChatGPT)

  • Division Method
    キーをテーブルのサイズで割った余りをハッシュ値として使用します。テーブルのサイズを素数にすると、より均等な分散が得られることが多いです。
  • Multiplication Method
    キーに定数を掛け、結果の小数部分を取り出して、テーブルのサイズを掛けることでハッシュ値を得ます。
  • Universal Hashing
  • MurmurHash
  • CityHash
  • FNV (Fowler-Noll-Vo) Hash
  • Jenkins Hash Function

ハッシュ値の衝突

ハッシュテーブルはキーをもとに生成したハッシュ値を添え字として利用するが、ハッシュ値は多くの場合入力となるキー全体より小さいため、異なるキー値に同じハッシュ値が生成される可能性がある。（鳩の巣原理 - Wikipedia）このハッシュ値の衝突がおきた場合、異なるキーで同じハッシュ値のデータを区別して保管する必要がある。
衝突が発生したときの対処法としては、チェイン法（Chaining/連鎖法）とオープンアドレス法（Open Addressing/開番地法）に大別される。

チェイン法（Chaining）

衝突したキーのエントリを連結リストとしてもつ方式。
配列にはエントリそのものではなく、連結リストを格納する。

オープンアドレス法（Open Addressing）

キーが衝突した場合、テーブルの中の開いている別のスロットを探索する方式。ハッシュ関数とは別の関数で次の候補となるスロットを求める。（再ハッシュ）
ただし、テーブルからキーを削除したときにスロットに格納されたデータを空にすると問題が発生する。削除されたキーよりあとに候補になるスロットにあるキーを検索した場合、削除されたスロットで走査が終了してしまいキーが存在しないことになってしまう。そのために削除を示す状態を保持する必要がある。
メモリ使用効率が高いが、テーブルが満杯に近づくと性能が低下する可能性がある。

線形探査（Linear Probing）

ハッシュ値から求めたスロットが衝突していた場合、次のスロットを順番に調べて最初の空きスロットにデータを格納する。パフォーマンスを維持するならload factorが0.5程度になったときresizeするのが目安。
$h'(k)=(h(k)+1) mod(m)$

この方法の主な問題点としてPrimary clusteringが知られている。
線形探索によって連続するスロットが埋まることでクラスタ（連続するスロットのグループ）が形成されると、そのクラスタ内の衝突の確率が高くなる。クラスタは時間とともに成長し、ハッシュテーブルの性能が低下する。

二次探査（Quadratic Probing）

次のスロットを任意の実数のi乗($0<=i<m$)のステップでスロットを順番に調べて最初の空きスロットにデータを格納する。
ハッシュテーブル全体に均一なレコード分布を得られる利点がある。
$h'(k)=(h(k)+c_1^i+c_2^{i^2}) mod(m)$

線形探査と異なり、クラスタが発生しないためPrimary clusteringがおきないようになっている。
しかし、異なるキーが同じスロットにハッシュされた場合、同じ探査シーケンスをもつため、特定のスロット周辺で衝突が頻発する可能性がある。この問題をsecondary clusteringと呼ぶ。

二重ハッシング（Double Hashing）

2つの独立したハッシュ関数を使って衝突の解決をおこなう。
$h'(k)=(h_1(k)+i \times h_2(k))mod(m) (i \in (1..m-1))$
1つ目のハッシュ関数$h_1$では最初のスロットを決めるためのハッシュ値を求める。2つ目のハッシュ関数$h_2$で次のスロットをみつけるためのステップの大きさを求める。

利点として、空きスロットを探索するステップの値を別のハッシュ関数を利用しているため、初期位置が同じでも探索範囲がことなるため衝突の発生確率がさがる。問題点としては、２つのハッシュ関数による計算の必要があるため、挿入と探索の計算量が増える可能性がある。また、２つのハッシュ関数が互いに素でなければ衝突確率が高くなる可能性がある。

Cuckoo hashing

衝突解決のための処理がカッコウの雛が孵化したら巣の鳥の卵を捨ててしまうカッコウの習性と類似していることが名前の由来。
他の手法と異なり、エントリの検索が最悪でも定数時間$O(1)$内で完了する。
Cuckoo hashingでは２種類のハッシュ関数$h_1$, $h_2$と２つのテーブル$T_1$, $T_2$を使用する。

キー$x$をハッシュテーブルに挿入する場合を考える。$T_1$の$h_1(x)$のスロットにキー$x$のエントリを格納する。このときスロットに既にエントリが存在した場合、古いエントリのキー$y$をもう一方のテーブル$T_2$に格納する。この追い出して格納の処理が完了するまで繰り返すことでエントリを挿入する。作成されたテーブルにはキー$x$が$T_1$または$T_2$のどちらかに入っていることが保証されるため、最悪２回の検索で見つけることができる。
ただし、エントリの挿入時に循環参照になった場合、追い出し処理が完了しないため処理回数に上限をつけテーブルをrehashする必要がある。load factorが0.5を超えない限り挿入コストは$O(1)$が保たれる。0.5を超えた場合、性能低下することがしられている。

Hopscotch hashing

Robin Hood Hashing

load factorとRehash

ハッシュテーブルはエントリの数が配列のサイズに近づくほど衝突の確率が高くなり性能が悪化する。
この比率をload factor（座席利用率）と呼び、$n/m$の形で表す。$n$はエントリの数、$m$は配列のサイズを指す。

チェイン法の場合、load factorの増加に対して線形に性能が悪化する。
オープンアドレス法では衝突したキーが空いた番地に格納されるため、load factorが0.7~0.8付近から急激に性能が悪化する。

この問題を回避するためにload factorが一定の値を超えた場合、より大きいハッシュテーブルを用意して格納しなおすrehashが必要になる。
すべての要素を再計算した場合、必要な計算量は$O(n)$程度となる。
rehashせずにあらかじめ十分なサイズの配列を用意する方法もあるが、エントリ数を事前に想定できない場合は適用できない。

rehashの高速化

テーブルのサイズに合わせて素直にハッシュ値を計算し直そうとすると$O(n)$だけ時間がかかるため、テーブルのサイズがおおきくなるにつれて時間がかかる。
以下にrehashの速度の向上させる方法について列挙する。

  • Incremental Resizing
    一度にエントリをrehashするのではなく、各操作（挿入、削除、検索）の後にエントリを古いテーブル（古いテーブルのスロットの位置）から新しいテーブルに移動する。rehashのコストを各操作に分散できる。
  • 並列rehash
  • ハッシュ関数の計算速度の向上
  • テーブルサイズ
  • メモリの事前確保
  • データの局所性の利用

並行ハッシュテーブル

参考

Raw
hash---hmac.md
title type weight lastmod
HMAC
docs
1
{"lastmod"=>nil}

TBD

Raw
hash---murmur3.go
package murmur3
import (
"encoding/binary"
"hash"
"math/bits"
)
const Size = 16
const BlockSize = 16
const (
c1_128 uint64 = 0x87c37b91114253d5
c2_128 uint64 = 0x4cf5ad432745937f
n1_128 uint64 = 0x52dce729
n2_128 uint64 = 0x38495ab5
f1_128 uint64 = 0xff51afd7ed558ccd
f2_128 uint64 = 0xc4ceb9fe1a85ec53
)
var _ Hash128 = (*digest128)(nil)
type Hash128 interface {
hash.Hash
Sum128() (uint64, uint64)
}
type digest128 struct {
tail []byte
h1 uint64
h2 uint64
len int
seed uint32
}
func New128(seed uint32) Hash128 {
d := new(digest128)
d.seed = seed
d.Reset()
return d
}
// BlockSize implements Hash128.
func (*digest128) BlockSize() int { return BlockSize }
// Reset implements Hash128.
func (d *digest128) Reset() {
d.len = 0
d.tail = nil
d.h1 = uint64(d.seed)
d.h2 = uint64(d.seed)
}
// Size implements Hash128.
// 128bitのハッシュ値を返すため16byteを返す
func (*digest128) Size() int { return Size }
// Write implements Hash128.
func (d *digest128) Write(p []byte) (n int, err error) {
n = len(p)
d.len += n
if len(d.tail) > 0 {
p = append(d.tail, p...)
}
d.tail = d.mix(p)
return n, nil
}
func (d *digest128) mix(p []byte) []byte {
h1, h2 := d.h1, d.h2
for len(p) >= d.BlockSize() {
k1 := binary.LittleEndian.Uint64(p[:8])
k2 := binary.LittleEndian.Uint64(p[8:16])
p = p[16:]
k1 *= c1_128
k1 = bits.RotateLeft64(k1, 31)
k1 *= c2_128
h1 ^= k1
h1 = bits.RotateLeft64(h1, 27)
h1 += h2
h1 = h1*5 + n1_128
k2 *= c2_128
k2 = bits.RotateLeft64(k2, 33)
k2 *= c1_128
h2 ^= k2
h2 = bits.RotateLeft64(h2, 31)
h2 += h1
h2 = h2*5 + n2_128
}
d.h1, d.h2 = h1, h2
return p
}
// Sum implements Hash128.
func (d *digest128) Sum(b []byte) []byte {
h1, h2 := d.Sum128()
b = binary.BigEndian.AppendUint64(b, h1)
b = binary.BigEndian.AppendUint64(b, h2)
return b
}
// Sum128 implements Hash128.
func (d *digest128) Sum128() (uint64, uint64) {
h1, h2 := d.h1, d.h2
var k1, k2 uint64
switch len(d.tail) & 15 {
case 15:
k2 ^= uint64(d.tail[14]) << 48
fallthrough
case 14:
k2 ^= uint64(d.tail[13]) << 40
fallthrough
case 13:
k2 ^= uint64(d.tail[12]) << 32
fallthrough
case 12:
k2 ^= uint64(d.tail[11]) << 24
fallthrough
case 11:
k2 ^= uint64(d.tail[10]) << 16
fallthrough
case 10:
k2 ^= uint64(d.tail[9]) << 8
fallthrough
case 9:
k2 ^= uint64(d.tail[8]) << 0
k2 *= c2_128
k2 = bits.RotateLeft64(k2, 33)
k2 *= c1_128
h2 ^= k2
fallthrough
case 8:
k1 ^= uint64(d.tail[7]) << 56
fallthrough
case 7:
k1 ^= uint64(d.tail[6]) << 48
fallthrough
case 6:
k1 ^= uint64(d.tail[5]) << 40
fallthrough
case 5:
k1 ^= uint64(d.tail[4]) << 32
fallthrough
case 4:
k1 ^= uint64(d.tail[3]) << 24
fallthrough
case 3:
k1 ^= uint64(d.tail[2]) << 16
fallthrough
case 2:
k1 ^= uint64(d.tail[1]) << 8
fallthrough
case 1:
k1 ^= uint64(d.tail[0]) << 0
k1 *= c1_128
k1 = bits.RotateLeft64(k1, 31)
k1 *= c2_128
h1 ^= k1
}
h1 ^= uint64(d.len)
h2 ^= uint64(d.len)
h1 += h2
h2 += h1
h1 = fmix64(h1)
h2 = fmix64(h2)
h1 += h2
h2 += h1
return h1, h2
}
func fmix64(h uint64) uint64 {
h ^= h >> 33
h *= f1_128
h ^= h >> 33
h *= f2_128
h ^= h >> 33
return h
}
func Sum128(data []byte, seed uint32) (h1 uint64, h2 uint64) {
d := New128(seed)
d.Write(data)
return d.Sum128()
}
Raw
math---!math.md
title type weight lastmod
Math
docs
1
{"lastmod"=>nil}

ユークリッドの互除法

２つの自然数の最大公約数(GCD, Greatest Common Divisor)を求める手法。

$a = bq + r$（$a \geqq b$）において、「$a$と$b$の最大公約数」=「$b$と$r$の最大公約数」

という性質が成立するため、この性質を利用してあまりがゼロ(公約数)になるまで再帰的に演算をすれば２つの自然数の最大公約数を求めることができる。

ユークリッドの互除法 - Wikipedia

Raw
math---三角関数.md
title type weight lastmod
三角関数
docs
1
{"lastmod"=>nil}

記憶から消えてるのでまとめる TBD

Raw
math---包除原理.md
title type weight lastmod
包除原理
docs
1
{"lastmod"=>nil}

包除原理（ほうじょげんり、英: Inclusion-exclusion principle, principle of inclusion and exclusion, Principle of inclusion-exclusion, PIE）あるいは包含と排除の原理とは、数え上げ組合せ論における基本的な結果のひとつ。
特別な場合には「有限集合 A と B の和集合に属する元の数を計算するには、まずそれぞれに属する元の数 |A| と |B| を足しあわせた後、それらの共通部分に属する元の数 |A ∩ B| を引き去ればよい」というものである。つまり単に数え上げた後で重複を取り除くことに相当する。
包除原理 - Wikipedia

問題

参考

Raw
tmp.md
title type author lastmod waight
tmp
docs
showa
{"lastmod"=>nil}
1

ScrapBoxから移行中

アルゴリズム

アルゴリズム

整数論

数列/集合

ソート

  • ![image](挿入ソート https://go.dev/play/p/27ZG-NkZNte)
    • 1個ずつ全部と順番にくらべていくやつ
    • シェルソート
      • 一定の間隔で先に大雑把に並び替えて、ある程度整列した状態をつくることで
      • ソートの効率をあげたソート
      • O(N^1.25)くらいまで性能がでると予測されてる
  • ![image](バブルソート https://go.dev/play/p/hj4SYpxFoOi)
    • 端っこから隣同士をくらべるやつ
  • ![image](選択ソート https://go.dev/play/p/hrsihLuVKwf)
    • 配列の最小の要素を探して順番に先頭と交換していくあれ
  • 安定ソートとは
    • 比較する値に同じ値があった場合、入力と同じ順序で出力されるソート
    • バブルソートは安定ソートだが、選択ソートはちがう
  • トポロジカルソート
    • 参考
    • 閉路のない有向グラフを仕事の手順をあらわすデータ構造として利用した場合に、着手すべき順番に列挙するときにおこなうソート

探索

  • 線形探索
    • O(n)
    • 番兵：検索したい対象を配列に配置することで条件を簡略化して定数倍の高速化をおこなえる
  • 二分探索
    • [$ O(log2n)]
  • 全探索
    • [半分全列挙]
      • N/2 ずつの 2 グループに分けて全列挙し、2グループ同士を組み合わせる際に高速化する
        • 半分のグループ A を全列挙
        • もう半分のグループ B を全列挙
        • Aの全ての要素について以下を行う
          • A から選ぶ要素を1つに固定したとき、条件に合う要素をBから高速に探す
      • [半分全列挙による全探索の高速化 | アルゴリズムロジック https://algo-logic.info/split-and-list/]
  • ハッシュ法
    • O(1)※衝突がなければ
    • ハッシュテーブルを用いた検索
    • ハッシュ関数でキーを生成して一意に求める
  • ヒュースティック探索
    • ![image](8クイーン問題 https://go.dev/play/p/OFZpirNhGjn)
      • チェス盤に８つのクイーンをお互いに襲撃できないようなおき方を解く問題
      • バックトラックをつかってとくよん
    • 8パズル
      • 幅優先探索や深さ優先探索で愚直に計算できる大きさ
      • パズルの状態を記憶して、解法になるパターンを順番に見つけていく
      • サンプルの実装は幅優先探索で実装
    • 15パズル
      • [反復深化（Iterative Deepening）]
        • IDA*（反復深化A*）
          • 推定値（＝ヒュースティック）を用いて枝を刈り取るアルゴリズム
          • リンクは15パネルを反復深化で解いた
          • 解法との距離をマンハッタン距離で推定値をだして、推定値と実際の値がゼロになるまで深さ優先探索を繰り返す
          • [A*]
            • 反復深化A*に用いた推定値を優先度付きキューを用いたダイクストラをベースとした探索アルゴリズム
            • 「始点から現在地までのコスト＋現在地からゴールまでの推定値」が最も小さい状態から優先的に状態遷移することで速度があがる

分割統治

  • 分割統治法（Divide and Conquer）

高等的整列

  • マージソート
    • [$ O(nlog2n)]
    • 配列のマージを行うことでソートをおこなう
    • 対象の配列以外で一次保存のためのメモリが必要
    • ai > aj and i < j である組の個数を反転数と呼ぶ
  • パーティション
    • O(n)
    • ある基準より大きいか小さいかを分類するアルゴリズム
  • クイックソート
    • 平均=O(nlog2n)
    • どんなデータに対しても一定のソートをおこなうのでソート済みのデータなどではO(n^2)
      • 基準をランダムに選ぶなどで工夫する必要がある
    • パーティションを使って離れた要素の交換をおこなうため、安定ソートではない
    • マージソートと異なり追加メモリが必要ではない
  • 計数ソート
    • O(n + k)
    • 各要素がk以下の数列に対してソートをおこなう
    • ソート時に後ろから取得することで安定ソートになる
    • 対象の配列以外で一次保存のためのメモリが必要

動的計画法

  • 計算結果をメモリに保持することで効率化をおこなう
    • フィボナッチ
    • 漸化式でiとi+1しか存在しない場合、偶数と奇数のそれぞれの場合の２つの配列だけでDPテーブルの再利用が可能になるケースがある
  • ![image](最長共通部分列（LCS） https://go.dev/play/p/vo0f3weQOMs)
    • 二つの列の最長の共通部分列を求める
    • 部分問題に分割して漸化式として解くことができる
  • 連鎖行列積
    • 行列の積の計算順序を変えられるため、最小の計算回数になるような順序を求めるアルゴリズム
    • 最小限の組み合わせから順番にコストを求めて、最小になるようなコストを求める
    • わかったようなわかってないような感じ
  • コイン問題
    • j円を支払う時の最小枚数を記録していく
  • ナップサック問題
    • 個数制限付きナップサック問題
      • DPテーブルを１次元に圧縮
      • 価値と重さが決まっている複数の品物を容量が一定のナップサックに詰め込むとき、ナップサックに詰め込める品物の価値の和の最大値は何であるか？
      • 解法パターンにはメモ化再帰を使う場合と漸化式の場合がある
      • 参考
    • 個数制限付き部分和ナップサック問題
      • 個数に着目して、品物を順番に配置したとき、計算したい値に残りの個数（0以上）が記録されていたかで計算できる
    • 個数制限なしナップサック問題
      • DPテーブルを１次元に圧縮
        • １次元に圧縮すると個数制限あり、なしの違いはループの方向だけ
      • i番目の品物を重さをこえない範囲でk個選んで最大の価値にする
      • k個選ぶ＝dpテーブルにおいてi番目の品物を選ぶときにi番目の重さを差し引いた残りの重さで最大の価値に加算することで表現できる
        • i番目で重さ２、価値３の場合
        • j（重さ）=4のとき、i番目の重さを差し引いたj=2のときの最大の価値が３の場合、i番目の価値をたした場合、価値が６になる
  • ![image](分割数 https://go.dev/play/p/lMtaGqZo1Oj)
  • 最長増加部分列（LIS）
    • ２分探索をつかってDPで記録した値を更新していく
    • 参考
  • 最大正方形
    • 最大の正方形を調べる問題
    • 動的計画法で書くマスごとに足し上げていく
      • 計算量：[$ O(HW)≒O(n^2)]
  • 最大長方形
    • 最大の長方形を調べる問題
    • 列方向の前処理をおこなったDPテーブルを用意して、スタックを使って各行の最大面積を求めていく
    • 計算量：O(HW)≒O(n^2)
  • ![image](Levenshtein Distance)
  • ![image](Traveling Salesman Problem)
    • 巡回セールスマン問題
      • [ビットDP(bit DP)の考え方 集合に対する動的計画法 | アルゴリズムロジック https://algo-logic.info/bit-dp/]
      • [ABC274 E問題]でbitdpを使った類似問題が出題された
  • ![image](Chinese Postman Problem)

データ構造

木

  • 節点（node）と節点同士を結ぶ辺（edge）で表されるデータ構造

  • ある節点と辺がつながっており、浅い節点を親（parent）

    • 同じ親をもつ節点同士を兄弟（sibling）

  • ある節点と辺がつながっており、深い節点を子（child）

    • 節点の子の数を次数（degree）
    • 子を持たない節点を外部節点（external node）または葉（leaf）
    • 葉でない節点を内部節点（internal node）

  • 根（root）と呼ばれる頂点をあらわす節点を持つ木を[根つき木（rooted tree） https://go.dev/play/p/AA5dlyDHdD8]

    • 根から節点までの長さを深さ（depth）
    • 節点から葉までの最大値を高さ（height）

  • 木の直径

    • 木の節点の中で一番遠い節点間の距離のこと
    • 参考

  • 二分木

    • すべての節点の子の数が２以下の木
    • ![image](木の巡回 https://go.dev/play/p/0MRkF9Sy5oj)
      • 木が深いと再帰が深くなるので注意
    • 木の復元
      • 先行順巡回で根から順番にたどり、中間順巡回で部分木を抽出し、葉から順番にノードを再構築する
    • 二分探索木
      • 二分探索木条件（binary search tree property）
        • ある節点xの左分木の節点yは x < y を満たす
        • ある節点xの右分木の節点zは z < x を満たす
      • 挿入
      • 探索
        • O(h) h=木の高さ
      • 削除
        • O(h) h=木の高さ
      • [回転]
        • 平衡二分木
    • [二分ヒープ(https://go.dev/play/p/4i1fgeL_QjD])
      • １つの配列の各要素に対応した完全二分木であらわされたデータ構造
      • max-ヒープ：節点のキーがその親のキー以下である
      • min-ヒープ：節点のキーがその親のキー以上である
      • 優先度付きキュー
        • 挿入、削除：O(logn)

  • 全域木

    • グラフのすべての頂点を含む部分グラフで、木（閉路を持たないグラフ）である限りできるだけ多くの辺をもつ木
    • グラフは複数の全域木をもつ
    • 最小全域木（MST）：全域木の中で辺の重みが最小のもの
    • 最小全域有向木 （Minimum-Cost Arborescence）
      • 重み付き有向グラフで指定された頂点を根とする最小有向木を求める
      • [Edmondsのアルゴリズム]
    • [シュタイナー木問題]
      • 与えられたすべての点を通る最小全域木を求めるのに対して、与えられた部分集合をつなぐ木を求める
    • 最短経路問題
      • 単一始点最短経路
        • 与えられた１つの頂点からすべての頂点への最短経路を求める問題
        • ダイクストラ
          • 最短経路を探しながらコストの計算をおこなう
          • 親の頂点のコストと辺のコストを加算しながら距離を計算する
          • 負の辺が存在する場合計算ができない
        • ベルマンフォード
          • 負の重みが存在する場合の単一始点最短経路
          • [ベルマンフォード法による単一始点最短経路を求めるアルゴリズム | アルゴリズムロジック https://algo-logic.info/bellman-ford/]
      • 全点対間最短経路（All Pairs Shortest Path:APSP）
        • すべての頂点のペア間の最短経路を求める問題
        • 優先度付きキューをつかったダイクストラでO(|V|(|E|+|V|)log{V}))
        • ワーシャルフロイド
          • 全ての頂点間の最短距離を調べて経路の検出をおこなう
          • ダイクストラとことなり負の辺が存在しても計算可能
          • O(|V^3|)なので実用には向かない
          • 参考
    • ![image](Level Ancestor Problem)
      • 頂点u の祖先であって深さが d であるものを求める問題
        • クエリが事前にわかってるならDFSで探索しながらキューの中身からとれる
      • [Jump Pointer Algorithm（ダンブリング） https://go.dev/play/p/mAe1EIOo34G]
        • ちゃんと実装できてないで
      • [Level Ancestor Problem – 37zigenのHP https://37zigen.com/level-ancestor-problem/]

![image](グラフ https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-all.pdf)

  • 対象の集合とそれらのつながりを表す集合
    • 連結成分
    • [強連結成分（strongly connected component）]
      • 有向グラフにおいて、すべての頂点対u, vについて互いに到達可能な連結成分
      • 参考
  • 対象を頂点（Vertex）、つながりを辺（edge）であらわす
  • G = (V, E)
    • 頂点の数：|V|
    • 辺の数：|E|
    • 辺：e = (u, v)
    • 辺の重み：w(u, v)
  • 頂点uとvの間に辺(u, v)が存在するとき隣接（adjacent）している
  • 隣接している頂点の列をパス（path）という
    • 始点と終点が同じパスを閉路（cycle）
  • ![image](間接点（Articulation Point） https://go.dev/play/p/kqb_cLGbmAs)
  • フローネットワーク
  • マッチング
    • どの各点も２辺以上つながっていない部分グラフ
    • 参考
  • グラフの実装
    • 隣接リスト表現
      • メモリ消費量が辺の数しか必要としない
      • 頂点間の関係を調べるには隣接する頂点を順番に調べる必要がある（O(n)）
      • 連結リストに依存するため辺の削除の操作が効率的でない
    • ![image](隣接行列表現 https://go.dev/play/p/lRujH0xq7In)
      • 頂点間の関係を定数時間で確認できる
      • 辺の追加削除を定数時間でおこなえる
      • メモリ消費量が頂点の数の２乗
      • 頂点間の関係を１つしか記録できない
  • 探索
  • ２部グラフ
    • 各頂点を白または黒でぬったとき、隣接する頂点が異なる色になるグラフのこと
    • [二部グラフ判定をUnionFindTreeで行う - noshi91のメモ https://noshi91.hatenablog.com/entry/2018/04/17/183132]
      • 頂点Xの色わけをするとき、色Aと色BをXとX+nの２種類のグラフで考える
      • 各色を２頂点でわけたUnionFindTreeをつくったときにXとX+nが同じDejointSetに含まれるなら、同じ頂点に両方の色が同時に存在することになり、矛盾するため二部グラフを満たさないことがわかる

素集合（DejointSet）

  • 互いな素な集合
  • １つの要素が複数の集合に属することのない互いに素な集合に分類して管理するためのデータ構造
  • Union Find：指定された２つの要素x,ｙが同じ集合な属するか探索する

[領域探索（kD Tree） https://go.dev/play/p/rm35zu-nrqK]

  • 点の集合から二分探索木を生成する
  • 二分探索木の根から探索をはじえｍて、ノードに関連づいている点が範囲内に存在するかをチェックしていく
  • 更にその子のノードに関しても再帰的に探索をおこなう
  • これはk次元の空間に拡張可能なため、kD木と呼ばれるデータ構造を構築することで探索をおこなえる
  • 木の深さによってポイントのソートの基準を変更することでk次元に対して探索をおこなう

Range Minimum Query（セグメント木）

  • 要素の値が動的に変化する数列に対して、範囲内の最小の要素を高速に求める[$ O(log(n))]
    • 指定の範囲内の最小値を求める
    • 数列の![image]($ a_i)を更新する
  • RMQを実現する別解として![image](Sparse Table https://ikatakos.com/pot/programming_algorithm/data_structure/sparse_table)による実装がある
    • 構築に[$ O(nlog(n))]、クエリに[$ O(log(1))]で求められる
    • 値の更新がセグメント木よりも高速におこなえない

バケット法

列や平面をバケットと呼ばれる任意の単位で分割して、バケットごとにデータを管理することで効率的に計算や操作をおこなう手法

  • 平方分割
    • n個の要素からなる列を![image]($ \sqrt n)程度ごとのバケットにまとめて管理する手法
    • 区間に対する処理が[$ O(\sqrt n)]程度でおこなえる
    • セグメント木は各操作が[$ O(logn)]なので、一般的にセグメント木を使うほうが効率的
    • ただし、平方分割のほうが実装がシンプルであったり、セグメント木で実現できない機能も実現可能な場合がある

Range Sum Query（動的セグメント木）

  • 要素の値が動的に変化する数列に対して、範囲内の要素の和を高速に求める

Suffix Array

計算機科学

  • ベクトルライブラリ
  • ![image](マンハッタン幾何（線分交差問題） https://go.dev/play/p/nKpe1kVfSIj)
  • [Closest Pair]
  • ![image](Diameter of a Convex Polygon)
    • 凸多角形の直径（＝最遠頂点対間距離）を求める問題
    • キャリパー法
  • [Convex Cut]
    • 凸多角形を直線で切断する問題

計算量解析

書籍ででてきたなにか

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment