Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Fixstars高速化コンテスト2024準優勝解法
Search
eijirou
January 07, 2025
Programming
0
270
Fixstars高速化コンテスト2024準優勝解法
eijirou
January 07, 2025
Tweet
Share
More Decks by eijirou
See All by eijirou
AHC051解法紹介
eijirou
0
640
Other Decks in Programming
See All in Programming
私の後悔をAWS DMSで解決した話
hiramax
4
170
Nuances on Kubernetes - RubyConf Taiwan 2025
envek
0
210
Understanding Ruby Grammar Through Conflicts
yui_knk
1
140
DockerからECSへ 〜 AWSの海に出る前に知っておきたいこと 〜
ota1022
5
1.8k
MLH State of the League: 2026 Season
theycallmeswift
0
180
ライブ配信サービスの インフラのジレンマ -マルチクラウドに至ったワケ-
mirrativ
2
270
Claude Codeで実装以外の開発フロー、どこまで自動化できるか?失敗と成功
ndadayo
3
1.7k
旅行プランAIエージェント開発の裏側
ippo012
1
500
Claude Codeで挑むOSSコントリビュート
eycjur
0
180
オープンセミナー2025@広島「君はどこで動かすか?」アンケート結果
satoshi256kbyte
0
220
令和最新版手のひらコンピュータ
koba789
14
8.1k
testingを眺める
matumoto
1
120
Featured
See All Featured
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
7
830
Imperfection Machines: The Place of Print at Facebook
scottboms
268
13k
Large-scale JavaScript Application Architecture
addyosmani
512
110k
Fireside Chat
paigeccino
39
3.6k
Being A Developer After 40
akosma
90
590k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
231
53k
The Power of CSS Pseudo Elements
geoffreycrofte
77
5.9k
Unsuck your backbone
ammeep
671
58k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
61k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
Scaling GitHub
holman
463
140k
How GitHub (no longer) Works
holman
315
140k
Transcript
Fixstars 高速化コンテスト 2024 準優勝の解法紹介 eijirou
問題 https://fixstars-contest.com/contests/cpu2024/problem • 長さが 𝑁 の配列 𝑎, 𝑏 が与えられる •
各要素(宝石)は 𝐾 未満の非負整数 • 𝑎 をいくつか巡回シフトし 𝑏 と一致する要素を最大化せよ • 一致する要素の最大値とそのときのシフト数(1つでよい)を求める コンテストサイト https://fixstars-contest.com/contests/cpu2024/problem 2
問題の言い換え • 長さが 𝑁 の配列 𝑎, 𝑏 が与えられる • 各要素(宝石)は
𝐾 未満の非負整数 • 𝑎 をいくつか巡回シフトし 𝑏 と一致する要素を最大化せよ • 一致する要素の最大値とそのときのシフト数(1つでよい)を求める • 以下の値を求めよ max 𝑘∈[𝑁] # 𝑎𝑖 = 𝑏𝑗 𝑖 + 𝑗 mod 𝑁 = 𝑘 3 𝑎 を逆順にして問題を言い換える
方針 1. 要素(宝石)ごとに各シフトへの寄与を求める • 𝑔𝑎,𝑥 ≔ 𝑖 ∣ 𝑎𝑖 =
𝑥 とすると、要素 𝑥 のシフト 𝑘 への寄与は # 𝑖, 𝑗 𝑖 ∈ 𝑔𝑎,𝑥 , 𝑗 ∈ 𝑔𝑏,𝑥 , 𝑖 + 𝑗 mod 𝑁 = 𝑘 2. 各シフトへの寄与を加算し、最大値を求める 2種類の解法を紹介する 4
インクリメント解法 • 𝑔𝑎,𝑥 ≔ 𝑖 ∣ 𝑎𝑖 = 𝑥 と
𝑔𝑏,𝑥 ≔ 𝑖 𝑏𝑖 = 𝑥 を求め、二重ループを 回す • 時間計算量は要素1つにつき 𝑂 𝑔𝑎,𝑥 ⋅ 𝑔𝑏,𝑥 • 各要素の出現回数が等しければ 𝑂 𝑁2 𝐾2 、全体で 𝑂 𝑁2 𝐾 5
インクリメント解法: キャッシュ効率 • キャッシュヒット率が悪い • 書き込み先の配列(ret)がL1キャッシュに収まらない 書き込み先の配列をL1キャッシュサイズで切る 6 このままだと遅いが、 尺取り法を使うと
𝑗 ∈ 𝑙 − 𝑖, 𝑟 − 𝑖 を効率よく列挙できる
インクリメント解法: 並列化 • 書き込み先を決めるループを並列化する • 書き込み先のメモリをスレッド毎に独立にできる • 実際には配列の長さを 𝑁 にした
7 ここをスレッド並列化
インクリメント解法: 命令数の削減 • ga[x] のループをunrollすると gb[x] の読み込み回数が減る • コンテスト後に @e869120
さん に教えていただきました 279ms 253ms 8
NTT解法 畳み込みに変形し、NTTを使う 𝑓𝑎,𝑝,𝑖 ≔ ቊ 0 (𝑎𝑖 ≠ 𝑝) 1
(𝑎𝑖 = 𝑝) • 𝑓𝑎,𝑝 (𝑥) ≔ 𝑓𝑎,𝑝,0 𝑥0 + 𝑓𝑎,𝑝,1 𝑥1 + ⋯ + 𝑓𝑎,𝑝,𝑛 −1 𝑥𝑛−1 • σ𝑝=0 𝐾−1 𝑓𝑎,𝑝 𝑥 ⋅ 𝑓𝑏,𝑝 𝑥 を求めればよい • 畳み込みを 𝑂 𝑁 log 𝑁 で計算できるため、全体で 𝑂 𝐾𝑁 log 𝑁 9
NTT解法: Nyaan’s Library を使う https://nyaannyaan.github.io/library/ntt/ntt-avx2.hpp • Nyaan’s Library で行われていた高速化 •
非再帰 • in-place • 4基底 • モンゴメリ乗算による除算の除去 • SIMD • data alignment • × 1 の省略, etc. Nyaan’s Library ntt/ntt-avx2 https://nyaannyaan.github.io/library/ntt/ntt-avx2.hpp 10
NTT解法: INTTをまとめる INTTは1回でよい 𝑝=0 𝐾−1 𝑓𝑎,𝑝 𝑥 ⋅ 𝑓𝑏,𝑝
𝑥 = 𝑝=0 𝐾−1 intt ntt 𝑓𝑎,𝑝 𝑥 ⋅ ntt 𝑓𝑏,𝑝 𝑥 = intt 𝑝=0 𝐾−1 ntt 𝑓𝑎,𝑝 𝑥 ⋅ ntt 𝑓𝑏,𝑝 𝑥 11 多項式の積 要素ごとの積 要素ごとの積 mod 上の加算
NTT解法: INTTをまとめる intt 𝐴 + intt 𝐵 = intt(𝐴 +
𝐵) の正当性 12 𝐴 𝑥 = σ𝐴𝑖 𝑥𝑖 𝐵 𝑥 = σ𝐵𝑖 𝑥𝑖 𝐴 𝑟0 , ⋯ , 𝐴 𝑟𝑁−1 𝐵 𝑟0 , ⋯ , 𝐵 𝑟𝑁−1 𝐶 𝑟0 , ⋯ , 𝐶 𝑟𝑁−1 = 𝐴 𝑟0 𝐵 𝑟0 , ⋯ , 𝐴 𝑟𝑁−1 𝐵 𝑟𝑁−1 𝐶 𝑥 = 𝐴 𝑥 ⋅ 𝐵(𝑥) NTT INTT FFT/NTT で畳み込みを計算する流れ
NTT解法: INTTをまとめる intt 𝐴 + intt 𝐵 = intt(𝐴 +
𝐵) の正当性 13 𝐴 𝑥 = σ𝐴𝑖 𝑥𝑖 𝐵 𝑥 = σ𝐵𝑖 𝑥𝑖 𝐴 𝑟0 , ⋯ , 𝐴 𝑟𝑁−1 𝐵 𝑟0 , ⋯ , 𝐵 𝑟𝑁−1 𝐶 𝑟0 , ⋯ , 𝐶 𝑟𝑁−1 = 𝐴 𝑟0 + 𝐵 𝑟0 , ⋯ , 𝐴 𝑟𝑁−1 + 𝐵 𝑟𝑁−1 𝐶 𝑥 = 𝐴 𝑥 + 𝐵(𝑥) NTT INTT 加算でも成り立つ 離散フーリエ変換は行列積なので 線形性が成り立つという説明も可能
NTT解法: その他の高速化 • 最初は要素が0と1しかないため、積を省略できる • 場合によっては2周目も積を省略する • できるだけキャッシュサイズで切る • 速くならないかも
14 1 2 3 4 7 10 13 5 6 8 9 11 12 14 15 キャッシュサイズ 番号は計算順序 配列のインデックス
まとめ • インクリメント解法 • 各要素の出現回数が等しければ 𝑂 𝑁2 𝐾 • 𝐾
が大きいときに使う • NTT解法 • 𝑂(𝐾𝑁 log 𝑁) • 𝐾 が小さいときに使う • 並列化 • 定数倍高速化 • 実行命令数の削減 • キャッシュヒット率の改善 15