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
670
Other Decks in Programming
See All in Programming
JSONataを使ってみよう Step Functionsが楽しくなる実践テクニック #devio2025
dafujii
1
520
請來的 AI Agent 同事們在寫程式時,怎麼用 pytest 去除各種幻想與盲點
keitheis
0
120
Laravel Boost 超入門
fire_arlo
3
210
Rancher と Terraform
fufuhu
2
240
Ruby Parser progress report 2025
yui_knk
1
430
AIコーディングAgentとの向き合い方
eycjur
0
270
機能追加とリーダー業務の類似性
rinchoku
2
1.3k
Compose Multiplatform × AI で作る、次世代アプリ開発支援ツールの設計と実装
thagikura
0
140
ProxyによるWindow間RPC機構の構築
syumai
3
1.2k
Flutter with Dart MCP: All You Need - 박제창 2025 I/O Extended Busan
itsmedreamwalker
0
150
Testing Trophyは叫ばない
toms74209200
0
860
「手軽で便利」に潜む罠。 Popover API を WCAG 2.2の視点で安全に使うには
taitotnk
0
840
Featured
See All Featured
Into the Great Unknown - MozCon
thekraken
40
2k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
27k
Practical Orchestrator
shlominoach
190
11k
How to Think Like a Performance Engineer
csswizardry
26
1.9k
Automating Front-end Workflow
addyosmani
1370
200k
Intergalactic Javascript Robots from Outer Space
tanoku
272
27k
What’s in a name? Adding method to the madness
productmarketing
PRO
23
3.7k
How STYLIGHT went responsive
nonsquared
100
5.8k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
53
2.9k
We Have a Design System, Now What?
morganepeng
53
7.8k
For a Future-Friendly Web
brad_frost
180
9.9k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
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