( )を使った式の計算には次のようなきまりがあります。
（□ ＋ ○） × △ ＝ □ × △ ＋ ○ × △
（□ － ○） × △ ＝ □ × △ － ○ × △
...たし算とかけ算には、次のようなきまりがあります。
□ ＋ ○ ＝ ○ ＋ □
（□ ＋ ○） ＋ △ ＝ □ ＋ （○ ＋ △）
□ × ○ ＝ ○ × □
（□ × ○） × △ ＝ □ × （○ × △）
この考えを使って、くふうして暗算で計算しよう。
分配法則・交換法則・結合法則。 とても当たり前で、当たり前すぎて、ほとんどの人は、もう特に意識することもない法則かもしれません。 でも、プログラミングを知っている僕らは、立ち止まってこの法則の価値に触れることができる。
最近のコンパイラは、こんな最適化をします。
int sumUpto(int n) {
if( n != 0 )
return n + sumUpto(n-1);
else
return 0;
}
こういう再帰的な関数呼び出しで計算するコードを、
int sumUpto(int n) { // _sumUpto:
// movl 4(%esp), %edx
int result = 0; // xorl %eax, %eax
while( n != 0 ) { // testl %edx, %edx
// je L2
// L3:
result = result + n; // addl %edx, %eax
n = n-1; // subl $1, %edx
} // jne L3
// L2:
// rep
return n; // ret
}
自動で、ループに直す（例は gcc）。 これによって、スタックの消費を減らしたり、関数呼び出しのオーバーヘッドを減らしたりできます。
しかし、よく見ると、最適化前と後では、違う計算をしています。お気づきでしょうか。 最適化前の sumUpto(5) は、5 と sumUpto(4) の結果を足し算し、sumUpto(4) は 4 と sumUpto(3) の…なので、 実行される計算は、こうです。
5 + (4 + (3 + (2 + (1 + 0))))一方で、ループバージョンの方は、大きい方から順に数を足し込んで行くので…求めているものは、こうです。
((((0 + 5) + 4) + 3) + 2) + 1intの足し算は結合法則が成り立つので、 こんな風に計算の順序を変えても問題ないぜ！ と最適化が行われます。
逆に、たとえば、浮動小数点数の足し算は精度の問題で結合法則が成り立ちません （(大きい数＋小)＋小 より 大＋(小＋小) の方が誤差が減ります）から、 次のようなコードは、プログラムの意味を変えてはいけないコンパイラには最適化できず、 スタック溢れで落ちます。
double sumUpto(double n) {
if( n > 0 )
return n + sumUpto(n-1);
else
return 0;
}
sumUpto(123456789);
こんな風に、○○ ＝ △△ という算数の法則は、左辺を右辺に、 あるいは右辺を左辺に書き換える最適化のチャンス！ なのです。
Intel Thread Building Blocks のドキュメントより。
template<typename Range, typename Value, typename Func, typename Reduction> Value parallel_reduce( const Range& range, const Value& identity, const Func& func, const Reduction& reduction, ... );... The reduction operation should be associative, but does not have to be commutative. ... (訳: ...reduction演算としては結合法則が成り立つものを指定するべきですが、 交換法則はなくても良く...)
長い配列の要素全部の足し算
a[0] + a[1] + a[2] + ... + a[999999]
は、
結合法則を使うと
(a[0] + ... + a[500000]) + (a[500001] + ... + a[999999])
と等しいので、
こう変形すれば、左側と右側を別々のCPUで並列に計算できるので速い、というような並列化をしてくれます。
これはコンパイラの最適化と違って自己責任で演算を指定するものなので、double の配列の足し算でも、
「まあ誤差とかそこまで気にしないからいいや」と思って使えば結合法則が成り立つつもりになって並列計算してくれます。
でも、明らかに全く結合法則が成り立たないもの…たとえば引き算
a[0] - a[1] - a[2] - ... - a[999999]
を変形して
(a[0] - ... - a[500000]) - (a[500001] - ... - a[999999])
こんなことをしてしまうと、結果が全然違うので、気にしないとかそういうレベルではなくなります。やめましょう。
でも、かわりに、一度足し算に変形すると
a[0] - (a[1] + a[2] + ... + a[999999])
これなら、後ろの大量の足し算が並列化できます。めでたいですね。
こんな風に、○○ ＝ △△ 的な法則（今回は結合法則）が成り立つ演算は、 いろいろな意味で、扱いやすい、筋のいい演算ということができます。 引き算のような筋の悪い（全国の引き算ファンの皆様すみません！）演算の裏にも、 筋の良い足し算を見出して整理してみると、色々と嬉しいことがあるかもしれません。
長いので意味もなく節を分けました。
さっき引き算を貶しすぎてしまったので、反省して、今度は褒めることにします。
int の配列 a[0] ... a[N-1] が入力されます。 配列の長さに比例する O(N) 時間準備していいですから、 以降、「i番目からk番目までの総和 a[i]+...+a[k] を教えて？」と聞かれたらどんな i と k でも即座に O(1) 時間で答えられるようにして下さい。
データベースに対して少し時間を掛けてインデクス作っていいですから、クエリには即座に答えられるようにしてください。 何も準備しないでいると、クエリのたびにforループなどで和を計算するはめになり、即座に答えることはできません。 といって、全ての (i, k) の組み合わせ全部の答えをループで前もって計算しておくのは、 配列長 N に比例する時間では終わりません。時間掛かりすぎです。
今回キーとなる性質は、「足し算と引き算はキャンセルし合う」法則。
□＋△－△ ＝ □
小学校の算数でこれって名前ついていましたっけ。覚えてませんが、結合法則や交換法則以上に、 もう当たり前過ぎてどうしましょうという性質です。でも、これはとても便利な使い道があります。
(a[i]+...+a[k]) = (a[i]+...+a[k]) + (a[k+1]+...+a[N-1]) - (a[k+1]+...+a[N-1])
= (a[i]+...+a[N-1]) - (a[k+1]+...+a[N-1])
(a[i]+...+a[k]) を求めるのに、それより後ろ全部、
(a[k+1]+...+a[N-1]) を足して、引く。
これを結合法則で整理すると、欲しいクエリの答えは、
「a[i]から最後まで」 - 「a[k+1]から最後まで」のように、
「最後まで」の和の結果だけあればすぐに引き算１発で求まることがわかります。
「最後まで」の和だけなら、インデックスを予め作っておけます。
1 8 4 9 3が入力配列だったとしたら、「最後までの和」配列は後ろから順に足し算していけば作れて
1 8 4 9 3
25 24 16 12 3
あとは、「2 番目から 4 番目！？ (8+4+9 = ?)」と聞かれたら2番目から5番目を引く(24-3 = 21) のが答えです。
足し算引き算に限らず、結合法則があって、キャンセルする相手がいる演算なら、 なんでもこのインデックスの張り方は可能です。 このキャンセル性も、とても便利な筋の良い性質なのですね。 単に結合法則だけでは不足で、たとえば、問題を変えて「a[i]からa[k]までの最小値を即座に返せるようにしてね！」 だと、 こんな簡単には行きません。最小値を求める演算はキャンセルする相手がいませんから。
今度は最小値さんを貶してしまったので、褒めます。
ある地点からある地点へ最短で移動できる経路を求めましょう。 それは地下鉄の路線図だったり、障害物の並んだゲームのマップだったりします。 アルゴリズムの参考書には必ず ダイクストラ法 や ウォーシャル・フロイド法 などの方法が載っていると思いますが、これらの計算手法が着目している最重要な事実は共通です。
「地点Ａから地点Ｂを通って地点Ｃに行く最短経路」 は、 「地点Ａから地点Ｂに行く最短経路」 に 「地点Ｂから地点Ｃに行く最短経路」 を繋げたものである。
当たり前、ですよね？ でも、この当たり前の事実をきちんと活用するだけで、効率的な最短路計算アルゴリズムが生まれます。
簡単な例の場合を、式で書いてみましょう。
地点Ａから地点Ｂに行く経路が x と y の２通りあったとします。
地点Ｂから地点Ｃに行く経路が z の１通りだけ。
この時「地点Ａから地点Ｂを通って地点Ｃに行く経路」は、x+z と y+z の２通りなので、
「最短経路」はその最小値、min(x+y, y+z)。
これが「ＡからＢの最短路」＋「ＢからＣの最短路」に等しい、というのが先程の主張で、つまりこうです。
min(x+z, y+z) = min(x, y) + z
まだわかりにくいので、min(foo, bar) のことを演算子で書くことにします。
foo▼bar で最小値を表すという記法を導入。書き直すと…
(x＋z)▼(y＋z) ＝ (x▼y)＋z
これは、分配法則です。記号が違うだけで、足し算と掛け算の分配法則 (x×z) ＋ (y×z) ＝（x＋y） × z と全く同じ形をしています。
「Ａ地点からＣ地点の最短経路」という条件を文字通りに書くと
(x＋z)▼(y＋z) つまり全部の可能な経路を作ってみて最小値を取る、
という計算になりますが、等式をみたら最適化のチャンス！ min と ＋ の分配法則によると、
(x▼y)＋z つまり、代わりにまず落ち着いて途中までの最短路 (x▼y) を計算してから、
+z じっくり経路を延ばす、という計算法でも正しく答えが求まるわけです。
というのがダイクストラ法であり、ウォーシャル・フロイド法です。
さっきは、引き算の裏に結合法則の成り立つ足し算を見出して並列化をしました。 同じように、素直に書いたプログラムの裏に分配法則が潜んでいないか考えるのも重要です。 分配法則を使って高速な計算をするアルゴリズム導出法はあまりにも重要なので名前がついていて、 動的計画法 といいます。 競技プログラマーさんにはおなじみでしょう。
結合法則すごいよ！分配法則すごいよ！という話をしました。 もちろんこれ以外にも応用は山ほどあって、たとえば3Dグラフィックスで使う 変換の同次座標表現 などは特に好きで語り出すと止まらないのですが、 この辺で止めておきます。
ところで、結合法則のことを、数学用語では 半群 といいます。結合法則を仮定するとどんなことができるか、一例をここまで紹介してきましたが、 それを突き詰めて、とにかく結合法則に秘められたパワー全てを暴きだそうとするのが、半群論です。 「結合法則＋キャンセルする相手」のことは、 群 と言います。 キャンセルする相手がいるという事実をバネにしてできることは何か、 あるいは日常に潜んだ群を見つけ出すには…？ 「分配法則」のことは (半)環 と名前がついています。
本当に、それだけです。 ブログやTwitterを読んでいて、 「群」や「環」や「半群」や「モノイド」や「体」…という単語を見ると、 なにか難しい数学だと逃げ出したくなる人も多いかと思いますが、 何のことはない、ぜんぶ基本は、小学校５年生で習った話です。 半群の話をしている人がいたら、結合法則のことかーと理解すれば100%合ってます。 半環の話をしている人がいたら、ああこの人は分配法則マニアなんだなあと思うと良いです。
以上。
参考文献：