概要
AtCoder ABC343のE問題を、日本語プログラミング言語なでしこでACするために最適化を行い20倍以上高速化しました。
本問題は実行時間制約がシビアという噂を聞いていましたので、いかに最適化して実行時間制約内に収めるかが問題となります。本記事では最適化の履歴を記録します。なでしこの高速化の参考になれば幸いです。
入力例1と入力例2の処理時間の履歴です。全探索を網羅する入力例2が2000ms以下となればACになります。最終的に入力例2が2000ms以下となり、本問題をなでしこでACすることができました。
最適化の履歴
アルゴリズムは正しいはずだが、実行時間制限に間に合っていない、下記URLのコードを基準とします。
1. 実行速度優先
なでしこには「実行速度優先」というオプションがありますのでこれを有効化します。「全て」の実行速度優先すると「それ」が使えなくなりますので、「それ」や連文を使わないように書き換える必要があります。
2. ループ内処理の関数化
もし、ループ内の処理を毎回パース・js変換しているとすれば処理が遅くなる原因になりますので、ループ内の処理で何度も呼ばれる処理は関数化しました。関数化すればパースやjs変換を削減できるのではないかという狙いです。
a2を7から0まで繰り返す
b2を7から0まで繰り返す
c2を7から0まで繰り返す
a3を7から-7まで繰り返す
b3を7から-7まで繰り返す
c3を7から-7まで繰り返す
a1とa2とa3の共通部分幅3を、dxに代入してください。
b1とb2とb3の共通部分幅3を、dyに代入してください。
c1とc2とc3の共通部分幅3を、dzに代入してください。
w3=dx*dy*dz
a1とa2の共通部分幅2を、dx12に代入してください。
b1とb2の共通部分幅2を、dy12に代入してください。
c1とc2の共通部分幅2を、dz12に代入してください。
w12=dx12*dy12*dz12
a2とa3の共通部分幅2を、dx23に代入してください。
b2とb3の共通部分幅2を、dy23に代入してください。
c2とc3の共通部分幅2を、dz23に代入してください。
w23=dx23*dy23*dz23
a3とa1の共通部分幅2を、dx31に代入してください。
b3とb1の共通部分幅2を、dy31に代入してください。
c3とc1の共通部分幅2を、dz31に代入してください。
w31=dx31*dy31*dz31
w2=w12+w23+w31-w3*3
ここまで
ここまで
ここまで
ここまで
ここまで
ここまで
●(a1とb1とc1とa2とb2とc2とa3とb3とc3の)共通部分体積3とは
a1とa2とa3の共通部分幅3を、dxに代入してください。
b1とb2とb3の共通部分幅3を、dyに代入してください。
c1とc2とc3の共通部分幅3を、dzに代入してください。
w3=dx*dy*dz
w3を戻してください。
ここまで。
●(a1とb1とc1とa2とb2とc2の)共通部分体積2とは
a1とa2の共通部分幅2を、dx12に代入してください。
b1とb2の共通部分幅2を、dy12に代入してください。
c1とc2の共通部分幅2を、dz12に代入してください。
w12=dx12*dy12*dz12
w12を戻してください。
ここまで。
a2を7から0まで繰り返す
b2を7から0まで繰り返す
c2を7から0まで繰り返す
a3を7から-7まで繰り返す
b3を7から-7まで繰り返す
c3を7から-7まで繰り返す
w3=a1とb1とc1とa2とb2とc2とa3とb3とc3の共通部分体積3
w12=a1とb1とc1とa2とb2とc2の共通部分体積2
w23=a2とb2とc2とa3とb3とc3の共通部分体積2
w31=a3とb3とc3とa1とb1とc1の共通部分体積2
w2=w12+w23+w31-w3*3
ここまで
ここまで
ここまで
ここまで
ここまで
ここまで
3. ループ内処理の1関数化
2で効果があったため、2を更に進めてループ内の処理を1関数にまとめてしまいます。
●(a1とb1とc1とa2とb2とc2とa3とb3とc3の)ループ内処理とは
w3=a1とb1とc1とa2とb2とc2とa3とb3とc3の共通部分体積3
w12=a1とb1とc1とa2とb2とc2の共通部分体積2
w23=a2とb2とc2とa3とb3とc3の共通部分体積2
w31=a3とb3とc3とa1とb1とc1の共通部分体積2
w2=w12+w23+w31-w3*3
...
ここまで。
a2を7から0まで繰り返す
b2を7から0まで繰り返す
c2を7から0まで繰り返す
a3を7から-7まで繰り返す
b3を7から-7まで繰り返す
c3を7から-7まで繰り返す
a1とb1とc1とa2とb2とc2とa3とb3とc3のループ内処理
ここまで。
ここまで。
ここまで。
ここまで。
ここまで。
ここまで。
4. ループアンローリング
C言語等では最適化有効でコンパイルする時に自動で適用してくれるループアンローリングですが、なでしこでも効果がありました。個人的にはJavaScript変換後の実行時に自動で有効になっていると思っていたので意外でした。
●(a2とb2とc2とa3とb3とc3の)ループ内処理とは
w3=a1とb1とc1とa2とb2とc2とa3とb3とc3の共通部分体積3
w12=a1とb1とc1とa2とb2とc2の共通部分体積2
w23=a2とb2とc2とa3とb3とc3の共通部分体積2
w31=a3とb3とc3とa1とb1とc1の共通部分体積2
w2=w12+w23+w31-w3*3
...
ここまで。
●(b2とc2とa3とb3とc3の)アンローリングループ内処理とは
0とb2とc2とa3とb3とc3のループ内処理
1とb2とc2とa3とb3とc3のループ内処理
2とb2とc2とa3とb3とc3のループ内処理
3とb2とc2とa3とb3とc3のループ内処理
4とb2とc2とa3とb3とc3のループ内処理
5とb2とc2とa3とb3とc3のループ内処理
6とb2とc2とa3とb3とc3のループ内処理
7とb2とc2とa3とb3とc3のループ内処理
ここまで。
b2を7から0まで繰り返す
c2を7から0まで繰り返す
a3を7から-7まで繰り返す
b3を7から-7まで繰り返す
c3を7から-7まで繰り返す
b2とc2とa3とb3とc3のアンローリングループ内処理
ここまで。
ここまで。
ここまで。
ここまで。
ここまで。
5. 敬語の廃止
なでしこにはプログラムを丁寧に記載するための敬語機能がありますが、「です」「ください」のパース処理や礼節度レベル処理に時間がかかっている可能性があります。このため繰り返し部分の敬語を廃止しました。日本語プログラミング言語ならではの書き方が失われてしまいますが、速度のためにやむを得ずの変更です。
●(a1とa2とa3の)共通部分幅3とは
[a1+7,a2+7,a3+7]の配列最小値をxmaxに代入してください。
[a1,a2,a3]の配列最大値をxminに代入してください。
答えはxmax-xminです。
もし、答えが0未満なら、
答えは0です。
ここまで。
答えを戻してください。
ここまで。
●(a1とb1とc1とa2とb2とc2とa3とb3とc3の)共通部分体積3とは
a1とa2とa3の共通部分幅3を、dxに代入してください。
b1とb2とb3の共通部分幅3を、dyに代入してください。
c1とc2とc3の共通部分幅3を、dzに代入してください。
w3=dx*dy*dz
w3を戻してください。
ここまで。
●(a1とa2の)共通部分幅2とは
[a1+7,a2+7]の配列最小値をxmaxに代入してください。
[a1,a2]の配列最大値をxminに代入してください。
答えはxmax-xminです。
もし、答えが0未満なら、
答えは0です。
ここまで。
答えを戻す。
ここまで。
●(a1とb1とc1とa2とb2とc2の)共通部分体積2とは
a1とa2の共通部分幅2を、dx12に代入してください。
b1とb2の共通部分幅2を、dy12に代入してください。
c1とc2の共通部分幅2を、dz12に代入してください。
w12=dx12*dy12*dz12
w12を戻してください。
ここまで。
●(a1とa2とa3の)共通部分幅3とは
[a1+7,a2+7,a3+7]の配列最小値をxmaxに代入。
[a1,a2,a3]の配列最大値をxminに代入。
答えはxmax-xmin。
もし、答えが0未満なら、
答えは0。
ここまで。
答えを戻す。
ここまで。
●(a1とb1とc1とa2とb2とc2とa3とb3とc3の)共通部分体積3とは
a1とa2とa3の共通部分幅3を、dxに代入。
b1とb2とb3の共通部分幅3を、dyに代入。
c1とc2とc3の共通部分幅3を、dzに代入。
w3=dx*dy*dz
w3を戻す。
ここまで。
●(a1とa2の)共通部分幅2とは
[a1+7,a2+7]の配列最小値をxmaxに代入。
[a1,a2]の配列最大値をxminに代入。
答えはxmax-xmin。
もし、答えが0未満なら、
答えは0。
ここまで。
答えを戻す。
ここまで。
●(a1とb1とc1とa2とb2とc2の)共通部分体積2とは
a1とa2の共通部分幅2を、dx12に代入。
b1とb2の共通部分幅2を、dy12に代入。
c1とc2の共通部分幅2を、dz12に代入。
w12=dx12*dy12*dz12
w12を戻す。
ここまで。
6. 「代入」の廃止
「AをXに代入」を「X=A」と書き換えました。代入命令を代入演算子の処理に置き換えることと、パース処理を減らすことで高速化することが狙いです。これも日本語プログラミング言語ならではの書き方が失われてしまいますが、速度のためにやむを得ずです。
●(a1とa2とa3の)共通部分幅3とは
xmax=[a1+7,a2+7,a3+7]の配列最小値。
xmin=[a1,a2,a3]の配列最大値。
答え=xmax-xmin。
もし、答え<0なら、
答え=0。
ここまで。
答えを戻す。
ここまで。
●(a1とb1とc1とa2とb2とc2とa3とb3とc3の)共通部分体積3とは
dx=a1とa2とa3の共通部分幅3。
dy=b1とb2とb3の共通部分幅3。
dz=c1とc2とc3の共通部分幅3。
w3=dx*dy*dz
w3を戻す。
ここまで。
●(a1とa2の)共通部分幅2とは
xmax=[a1+7,a2+7]の配列最小値。
xmin=[a1,a2]の配列最大値。
答え=xmax-xmin。
もし、答え<0なら、
答え=0。
ここまで。
答えを戻す。
ここまで。
●(a1とb1とc1とa2とb2とc2の)共通部分体積2とは
dx12=a1とa2の共通部分幅2。
dy12=b1とb2の共通部分幅2。
dz12=c1とc2の共通部分幅2。
w12=dx12*dy12*dz12
w12を戻す。
ここまで。
学び
なでしこで競技プログラミング用ライブラリを作る際は、定数倍高速化も考慮した実装にしておく方が安心です。
- ライブラリでは「それ」や連文を使わない
- ライブラリでは敬語は外しておく
- ライブラリでは「代入」を使わず
X=Aのように記載する
(おまけ) max(a, b), min(a, b)の最適化
C++やPythonのmax(a, b)やmin(a, b)を、なでしこでは[a, b]の配列最大値, [a, b]の配列最小値と実装していました。[a, b]の配列コピー処理に時間がかかるのではないかと予想して関数化してみましたが、結果は逆に遅くなってしまいました。関数処理のオーバヘッドが大きいようです。
●(a1とa2の)共通部分幅2とは
xmax=[a1+7,a2+7]の配列最小値。
xmin=[a1,a2]の配列最大値。
答え=xmax-xmin。
もし、答え<0なら、
答え=0。
ここまで。
答えを戻す。
ここまで。
●(a1とa2の)小さい方とは
もし、a1<a2なら、
a1を戻す。
違えば、
a2を戻す。
ここまで。
ここまで。
●(a1とa2の)大きい方とは
もし、a1>a2なら、
a1を戻す。
違えば、
a2を戻す。
ここまで。
ここまで。
●(a1とa2の)共通部分幅2とは
xmax=(a1+7)と(a2+7)の小さい方。
xmin=a1とa2の大きい方。
答え=xmax-xmin。
もし、答え<0なら、
答え=0。
ここまで。
答えを戻す。
ここまで。