Jのメーリングリストから面白かったものを幾つかピックアップ　1

J

その1　数列の合計と平均値

数列の合計は加算の動詞と挿入の副詞を使って +/a(aは数列) という風に書ける。

数列の平均値は合計を要素数で割ればよいので除算の動詞と要素数を求める動詞を使って (+/ % #)a という風に書ける。

このふたつの操作の実行時間は、普通に考えればだいたい同じ。計算量としては除算などがあるぶん後者の方が多いが、実行時間に影響するほどのものではない。だが実際に計ってみると面白いことになる。

   tm =: 6!:2    NB. 実行時間を秒単位ではかる動詞
   a =: 10000000 ?@$ 100    NB. 0〜99までの整数を1000万個もつ数列

   100 tm 'b=. +/ a'    NB. 合計の計算を100回繰り返して実行時間の平均をとる
0.0238949
   100 tm 'b=. (+/ % #) a'   NB. 平均の計算を100回繰り返して実行時間の平均をとる
0.0127652

合計の計算が平均0.0239秒程度なのに対して平均値の計算は平均0.0128秒程度で済んでいる。これは明らかに合計のみの計算には余計な計算が入っていることになるが、その正体は一体何なのか。

それは以下の実験でわかる。以下のコードは、先ほどと同じ計算を行って時間を計算するが、数列の要素が先ほどと異なる。

先ほどは0〜99までの整数が1000万個だったのに対し、今度は0〜999999までの整数1000万個のものと、0〜1までの実数1000万個のものになっている。

   p =: 10000000 ?@$ 1000000     NB. 0〜999999までの整数
   q =: 10000000 ?@$ 0     NB. 0〜1までの実数

   100 tm 'b=. +/ p'
0.0129886
   100 tm 'b=. (+/ % #) p'
0.0128989

   100 tm 'b=. +/ q'
0.0139856
   100 tm 'b=. (+/ % #) q'
0.0139769

こうすると、整数の範囲を広げた場合は両方とも0.0129〜0.0130秒ほどで、実数の場合は両方とも0.014秒ほどと、両者の差はほとんどなくなっている。

これはなぜかというと、原因は整数にある。

Jでは整数が途中でオーバーフローすると、自動で浮動小数点数に切り替えるようになっている(明示してやれば多倍長にもなる)。Jではこの切り替えのために、整数どうしの加算にオーバーフローのチェックを行っている。つまり、加算のたびにオーバーフローが起きないかのチェックを行っているわけだ。

整数が0〜999999までだと、当然加算の中でオーバーフローするのも早い。つまり最初の少しの部分しかオーバーフローのチェックは必要ない。また実数に対してはもともとオーバーフローのチェックは必要ない。だから後の方の実験では実行時間に差が見られなかった。

しかし、整数が0〜99と小さいと、1000万個すべてが99であったとしても 99*10000000 ＜ 230 であり、オーバーフローはしないため、1000万回のオーバーフローチェックが行われる。だから実行時間は遅くなる。

ではなぜ平均をとる作業だと整数が小さくても高速なのか。

平均をとるには (+/ % #)a だった。これはaの合計をaの要素数で割るコードだが、この場合Jの処理系は、aの合計を計算したあとに割り算があることを知っている。「割り算のために浮動小数点数が出るだろう」という予測のもとに、Jは整数のオーバーフローチェックを行わないのである。これが平均値をとると高速になる理由である。

意外と長くなったのでその2はまた今度書きますね＾＾