何か妙なタイトルだけど、言いたいことはこれだけです。
D言語で競技プログラミングのコードを書く時は、可能な限り static foreach を使うと良いぞ。
タイトルにこれをねじ込んで終わり、でも良かったのですが、もう少し解説します。
static foreach とは
D言語のテンプレートメタプログラミング機能の一つで、コンパイル時に foreach 文を評価し、 コードを展開 してくれます。
相方の static if もそうなのですが、これは普通の foreach 文とはかなり違っていて、コンパイル時に新たなコードを生成する為の機能です。
具体例を見てみましょう。
static foreach (i; 1..4) {
writeln("#", i);
}
これは、コンパイル時に解決され、吐き出されたバイナリの中では次のような処理になっています。
（実際にコードが吐き出されるわけではなく、あくまでこんな風に書いたのと同じ、という意味です。）
writeln("#", 1);
writeln("#", 2);
writeln("#", 3);
コードの上では存在していたループが消え去り、全て書き下されています。
static foreach を使うための条件
static foreach は、しかし「普通の foreach に static を付ければそれで使える」というものではありません。
コンパイル時にループを展開する関係上、利用する値がコンパイル時に決定されている必要があります。
つまり、
auto n = readln.chomp.to!int;
static foreach (i; 0..n) {
...
}
こういうことはできないわけですね。入力から与えられる n はコンパイル時には分かりません。
コンパイル時に取得できる値は、定数、リテラル、そしてコンパイル時に実行可能な関数の返り値などです（あと、それらが代入された変数）。D言語は CTFE 、コンパイル時関数評価にかなり気を遣って標準ライブラリが作られているので、割と多くの関数をコンパイル時に動かす事ができます。
どうして普通の foreach では駄目なの？
制約が多そうな static foreach ですが、では普通の foreach から置き換えるべき理由はなんでしょうか？
これは、具体的な問題を解きながら考えてみましょう。
問題文
$H$ 行 $W$ 列のマス目がある。
各マスからは、その上下左右の隣接した通過可能なマスに移動可能である。
. のマスは通過可能で、 # のマスは通過不可能である。
$s$ から $g$ まで到達可能かどうか判定せよ。
ただし、 $s$ と $g$ のマスは通過可能である。
制約
$1 \le H, W \le 3000$
例
入力例1
3 3
s..
.#.
..g
出力例1
Yes
入力例2
1 3
s#g
出力例2
No
雑に幅優先探索で解いてみましょう。
import std.stdio, std.conv, std.range, std.string;
void main()
{
auto hw = readln.split.to!(int[]);
auto H = hw[0];
auto W = hw[1];
auto field = new bool[][](H, W);
int sx, sy, gx, gy;
foreach (i; 0..H) foreach (j, c; readln.chomp) {
if (c == 's') {
sx = j.to!int;
sy = i;
} else if (c == 'g') {
gx = j.to!int;
gy = i;
} else if (c == '#') {
field[i][j] = true;
}
}
auto memo = new bool[][](H, W);
memo[sy][sx] = true;
auto Q = [[sx, sy]];
while (!Q.empty) {
auto X = Q[0][0];
auto Y = Q[0][1];
Q = Q[1..$];
foreach (d; [[1,0], [0,1], [-1,0], [0,-1]]) {
auto x = X+d[0];
auto y = Y+d[1];
if (0 <= x && x < W && 0 <= y && y < H && !field[y][x] && !memo[y][x]) {
memo[y][x] = true;
Q ~= [x, y];
}
}
}
writeln(T[gy][gx] ? "Yes" : "No");
}
さて、実行してみましょう。
試しに H=3000, W=3000 で、左上が s 、右下が g 、その他全て . という入力を試してみます。
AtCoder のコードテストで試したかったのですが、入力が 8MiB くらいになってしまったので（コードテストの入力の上限は 512KiB ）、手元での実行結果を示します。
$ dmd foreach.d
$ time ./foreach < input1.txt
Yes
./foreach < input1.txt 3.20s user 0.10s system 91% cpu 3.590 total
3秒以上かかってしまっていますね。
しかしこれは最適化をしていません。 AtCoder の本番ジャッジでは最適化オプションを付けてコンパイルされるはずです。
$ dmd -O -release foreach.d
$ time ./foreach < input1.txt
Yes
./foreach < input1.txt 2.97s user 0.10s system 100% cpu 3.049 total
ちょっとだけ速くなりましたかね。しかしそれでも3秒近くかかっています。
static foreach を使う
では、本題の static foreach を使ってみましょう。
この部分を見てください。
foreach (d; [[1,0], [0,1], [-1,0], [0,-1]]) {
この行は、 foreach で列挙する配列の中身が直接書かれています。つまり、コンパイル時に決定されているということです。
こういう処理を行う場合、 static foreach を使うことができます。
（該当コードのみ書き換え）
static foreach (d; [[1,0], [0,1], [-1,0], [0,-1]]) {{
auto x = X+d[0];
auto y = Y+d[1];
if (0 <= x && x < W && 0 <= y && y < H && !F[y][x] && !T[y][x]) {
T[y][x] = true;
Q ~= [x, y];
}
}}
波括弧が二重になっている事に注意してください。
通常 static foreach は、コードを展開する際に波括弧を剥がします。しかし内側で変数を定義している場合、そのまま展開されてしまうと同名の変数が定義されることになるので、コンパイルエラーが起きてしまいます。
static foreach が剥がす波括弧は一つだけなので、波括弧を二重にすることで変数が定義されるコードのスコープを変え、コンパイルエラーを回避することができます。
さて、動かしてみましょう。
$ dmd foreach.d
$ time ./foreach < input1.txt
Yes
./foreach < input1.txt 1.21s user 0.06s system 86% cpu 1.476 total
$ dmd -O -release foreach.d
$ time ./foreach < input1.txt
Yes
./foreach < input1.txt 1.08s user 0.06s system 85% cpu 1.326 total
素晴らしい！ 充分に高速です！
注意事項
もちろんこれはわざとらしい例です。
定数倍のループが $3000 \times 3000 = 9000000$ 回も繰り返されるような場面になってようやく、効果を発揮する最適化です。
（とはいえ、二次元平面上を走査するような処理でそういう場面は多いとは思うのですが。）
何でもかんでも static foreach にすれば速くなる、というわけではないことに注意してください。
また、あまりに回数の多いループを static foreach で展開しようとすると、コンパイルに時間がかかりすぎることにも気を付けてください。加うるに、吐き出されるバイナリも極端に肥大化してしまうでしょう。
何故 static foreach は「速い」のか
はい、 static foreach を使うと速くなる場面があることは分かりました。
では、何故 static foreach は速いのでしょうか？
「ループをコンパイル時に展開しているから」というのは尤もな説明ですが、しかしそれで実行速度が速くなるのはどういう理由なのでしょう。
こういう場合は、実際に吐き出されたバイナリを比較してみるのが一番です。
ただし、上の節で利用したコードは余計な処理が多いことから、もう少し要点を絞ったコードを使って比較してみましょう。
int add() @nogc pure
{
int x;
foreach (i; 1..4) x += i;
return x;
}
数字を、 1 から 3 まで数え上げて全て足し合わせるだけ。簡単ですね。
これを、次のようにコンパイルします。
$ dmd -betterC -g -c non_static.d
-betterC というオプションは、ベターCモードでのコンパイルを指示するもので、このモードだと、D言語のランタイムその他を含めずコンパイルする事ができます（当然 GC などは動かなくなります）。バイナリに余計な情報を混ぜないためにこのオプションを付けたのですが、今回は単なる関数のみのコードなので、実際に吐き出されたバイナリを見てみたらあまり違いはありませんでした。
-g はデバッグ用の情報を埋め込むためのフラグです。この後、逆アセンブルをするので、見やすくする為に付しておきましょう。
同様に、 static foreach 版も書いてコンパイルします。
int add() @nogc pure
{
int x;
static foreach (i; 1..4) x += i;
return x;
}
$ dmd -betterC -g -c static.d
バイナリを読む
では、吐き出されたバイナリを実際に読んでいきましょう。
機械語が読みこなせる方であればバイナリエディタなどで開いて直接読めるのだと思いますが、私を含めそういう技能を持たない方は、適切なツールを使いましょう。
D言語の吐き出したバイナリは、 objdump コマンドを使って逆アセンブルする事ができます。
やってみましょう。
dmd_non_o_non_static.o: file format Mach-O 64-bit x86-64
Disassembly of section __TEXT,__textcoal_nt:
000000000000027c __D10non_static3addFNaNiZi:
; int add() @nogc pure
27c: 55 pushq %rbp
27d: 48 8b ec movq %rsp, %rbp
280: 48 83 ec 10 subq $16, %rsp
; int x;
284: c7 45 f0 00 00 00 00 movl $0, -16(%rbp)
; foreach (i; 1..4) x += i;
28b: c7 45 f4 01 00 00 00 movl $1, -12(%rbp)
292: c7 45 f8 04 00 00 00 movl $4, -8(%rbp)
299: 8b 45 f4 movl -12(%rbp), %eax
29c: 3b 45 f8 cmpl -8(%rbp), %eax
29f: 7d 0e jge 14 <__D10non_static3addFNaNiZi+0x33>
2a1: 8b 4d f4 movl -12(%rbp), %ecx
2a4: 89 4d fc movl %ecx, -4(%rbp)
2a7: 01 4d f0 addl %ecx, -16(%rbp)
2aa: ff 45 f4 incl -12(%rbp)
2ad: eb ea jmp -22 <__D10non_static3addFNaNiZi+0x1d>
; return x;
2af: 8b 45 f0 movl -16(%rbp), %eax
; }
2b2: c9 leave
2b3: c3 retq
これはアセンブリなので、私の環境（ MacOS なので、 AT&T 構文というやつなんですかね？）に極度に依存しています。みなさんのお手元の環境で同じことをすると、全く違う結果になるかもしれません。ただ、やっている事はそんなに変わらないと思います。
適度に元のソースコードがコメントで挿入されて、それなりに読みやすいですね。それぞれのニーモニックの意味が分かれば、何をやっているかは理解できるでしょう。
アセンブリの詳しい説明はしませんが（自信が無いのでできない、というのが正直なところです）、割と元のソースコードに忠実な処理をしていますね。
変数を $1$ ずつインクリメントしていき、 $4$ を超えたらジャンプで脱出する、といった処理が行われています。
最適化オプションを付けると、次のようなバイナリが作られます。
dmd_o_non_static.o: file format Mach-O 64-bit x86-64
Disassembly of section __TEXT,__textcoal_nt:
0000000000000274 __D10non_static3addFNaNiZi:
; int add() @nogc pure
274: 55 pushq %rbp
275: 48 8b ec movq %rsp, %rbp
278: 31 c0 xorl %eax, %eax
27a: b9 01 00 00 00 movl $1, %ecx
; foreach (i; 1..4) x += i;
27f: 03 c1 addl %ecx, %eax
281: ff c1 incl %ecx
283: 83 f9 04 cmpl $4, %ecx
286: 72 f7 jb -9 <__D10non_static3addFNaNiZi+0xb>
; }
288: 5d popq %rbp
289: c3 retq
最適化しなかった場合に比べて随分とすっきりしたアセンブリになっており、最適化の効果がはっきりと分かりますね。
ループ内については、加算処理と脱出判断の処理との順番が整理され、命令がシンプルになっています。
命令数が減っているということは、当然、その分速度の向上が期待できるはずです。
では、次に static foreach 版のバイナリを見てみましょう。
dmd_non_o_static.o: file format Mach-O 64-bit x86-64
Disassembly of section __TEXT,__textcoal_nt:
0000000000000230 __D6static3addFNaNiZi:
; int add() @nogc pure
230: 55 pushq %rbp
231: 48 8b ec movq %rsp, %rbp
234: 48 83 ec 08 subq $8, %rsp
; int x;
238: c7 45 f8 00 00 00 00 movl $0, -8(%rbp)
; static foreach (i; 1..4) x += i;
23f: ff 45 f8 incl -8(%rbp)
242: 83 45 f8 02 addl $2, -8(%rbp)
246: 83 45 f8 03 addl $3, -8(%rbp)
24a: 8b 45 f8 movl -8(%rbp), %eax
; }
24d: c9 leave
24e: c3 retq
通常 foreach 版よりずっと見やすいアセンブリですね。
命令を見てみると、単純に $0$ で初期化した一つのレジスタに $1, 2, 3$ をそれぞれ加算していく処理が行われています。
ループを回すコードに比べて、数え上げ用のレジスタをインクリメントしたり比較したりといった処理がなくなるので、更に高速になることが期待できますね。
このように、 static foreach を使うと、バイナリレベルで明確に命令数が少なくなり、高速化が期待できることが分かります。
もちろん、現代 CPU の挙動は大変複雑で、どれだけキャッシュされるか、どのようにパイプライン処理されるか、などの観点も大いに速度に関わってきます。命令数が少ないから速い、などと単純に言うことはできません。が、それでも static foreach を使った場合の方が、大抵の場合で高速なバイナリが吐き出される事はあると思います。
最後に、 static foreach 版で最適化を行ったコードを見てみましょう。
dmd_o_static.o: file format Mach-O 64-bit x86-64
Disassembly of section __TEXT,__textcoal_nt:
0000000000000230 __D6static3addFNaNiZi:
; int add() @nogc pure
230: 55 pushq %rbp
231: 48 8b ec movq %rsp, %rbp
234: b8 06 00 00 00 movl $6, %eax
; }
239: 5d popq %rbp
23a: c3 retq
EAX レジスタに $6$ を突っ込んで終わっています。 $6$ というのは、つまり $1 + 2 + 3$ ですね。
ループ回数も加算する数字もコンパイル時に分かっているので、この関数が何を返すかもコンパイル時に決定可能、というわけです。
このように、コンパイル時に可能な計算は全てコンパイル時に行ってくれれば、実行時間を極限まで削減できます。
実用的なプログラムでも、エンジニアが「ここはコンパイル時に計算できるから計算して定数を埋め込んでおこう」といちいち考えながらコーディングするのは中々大変ですし、結果を埋め込んだ定数が増えると変更に弱いプログラムになりがちです。計算を記述しつつ、結果はコンパイル時に計算してくれるのであれば、柔軟性と耐久性を両取りすることができますね。
C++ と比較してみる
ところで、同じようなコードを C++ で書くとどうなるでしょうか。
int add()
{
int x = 0;
for (int i = 1; i < 4; ++i) x += i;
return x;
}
これをコンパイルして調べてみましょう。コンパイラは clang を使いました。
cpp.o: file format Mach-O 64-bit x86-64
Disassembly of section __TEXT,__text:
0000000000000000 __Z3addv:
; {
0: 55 pushq %rbp
1: 48 89 e5 movq %rsp, %rbp
; return x;
4: b8 06 00 00 00 movl $6, %eax
9: 5d popq %rbp
a: c3 retq
……確か何の最適化オプションも付けていなかったと思うのですが、ループは全て展開され、コンパイル時に計算され、結果だけが返却されていますね。
C++ コンパイラは長い歴史を持っており、最適化テクニックが極めて洗練されています。コンパイル時の計算可能性も鋭く発見してくれて、可能な限り計算してくれます。D言語の static foreach のような構文はありませんが、そもそも静的に展開できそうな場所だと積極的に展開してくれるはずです。
競技プログラミングで、 C++ を使うと何もしなくても概ね高速に実行してくれるのは、このようなコンパイラの最適化の賜物という面も大きいかもしれません。
さらに余談ですが、 D言語のコードを DMD ではなくて LDC を使ってコンパイルしてみましょう。
まず最適化しない場合です。
ldc_non_o_non_static.o: file format Mach-O 64-bit x86-64
Disassembly of section __TEXT,__text:
0000000000000000 __D10non_static3addFNaNiZi:
; int add() @nogc pure
0: 55 pushq %rbp
1: 48 89 e5 movq %rsp, %rbp
; int x;
4: c7 45 fc 00 00 00 00 movl $0, -4(%rbp)
; foreach (i; 1..4) x += i;
b: c7 45 f8 01 00 00 00 movl $1, -8(%rbp)
12: c7 45 f4 04 00 00 00 movl $4, -12(%rbp)
19: 8b 45 f8 movl -8(%rbp), %eax
1c: 3b 45 f4 cmpl -12(%rbp), %eax
1f: 7d 1a jge 26 <__D10non_static3addFNaNiZi+0x3b>
21: 8b 45 f8 movl -8(%rbp), %eax
24: 89 45 f0 movl %eax, -16(%rbp)
27: 8b 45 f0 movl -16(%rbp), %eax
2a: 03 45 fc addl -4(%rbp), %eax
2d: 89 45 fc movl %eax, -4(%rbp)
30: 8b 45 f8 movl -8(%rbp), %eax
33: 83 c0 01 addl $1, %eax
36: 89 45 f8 movl %eax, -8(%rbp)
39: eb de jmp -34 <__D10non_static3addFNaNiZi+0x19>
; return x;
3b: 8b 45 fc movl -4(%rbp), %eax
3e: 5d popq %rbp
3f: c3 retq
DMD の時と同じような結果ですね。
次に、最適化オプションを付けてみましょう。
ldc_o_non_static.o: file format Mach-O 64-bit x86-64
Disassembly of section __TEXT,__text:
0000000000000000 __D10non_static3addFNaNiZi:
; return x;
0: b8 06 00 00 00 movl $6, %eax
5: c3 retq
確認しておきますが、これは static foreach ではなく普通の foreach を使ったコードです。
C++ のコンパイラと同じように、コンパイル時に計算可能な部分を判断して、全て計算した上で結果だけ返しています。
LDC の最適化は llvm の機能を使ったものかと思いますが、D言語でも C++ 並の素晴らしい最適化をしてくれるのですね……感動してしまった。
（たしか、上の C++ をコンパイルした clang も、バックエンドは llvm ですね。）
うーん、 llvm は凄い。
結論
D言語で競技プログラミングをするならば、可能な限り static foreach を使うと高速化できる。
（でもあまりにループ回数が多すぎるとコンパイルが終わらないから気をつけよう。）
あと、 DMD よりも LDC を使った方が、大抵の場合は速くなる。