Thread by @genkuroki

#Julia言語

[f(x) for x in X if cond(x)] では、実際に条件を満たすすべてのxについてf(x)を計算して、Array(配列)ができ、その分だけのメモリ割当が生じる。

(f(x) for x in X if cond(x)) は単に条件を満たすf(x)達の生成の仕方を記述したオブジェクトになり、メモリをほとんど消費しない。

https://twitter.com/genkuroki/status/1373168173248253956

#Julia言語

sum([f(x) for x in X if cond(x)]) では [f(x) for x in X if cond(x)] の分の配列が作られて、その分だけのメモリ割当が生じる。

一方、sum(f(x) for x in X if cond(x)) ではそのような無駄なメモリ割当は発生せず、条件を満たす各々のxについてf(x)が計算され、即足し上げられる。

#Julia言語 これらの違いはループの内側でそのような和を計算するときにはパフォーマンスに決定的な影響を与える。

条件無しに単に x∈X について和を計算したい場合には

sum(f, X)

とも書ける。誤差の観点からはこちらの方が好ましい(Float32で計算する場合は特にそうである)。

#Julia言語 Σ_{n=1}^N f(n) の計算で((f(1) + f(2)) + f(3)) + f(4)のようにリニアに足して行くと、f(1)+…+f(k)と比較してf(k+1)が小さいときに(f(1)+…+f(k))+f(k+1)の計算で大きな桁落ちが発生する。

「塵を集めて大きくしてから足すこと」を帰納的に実行しないと無用に誤差が大きくなる。

#Julia言語 足し上げ方はトーナメント戦の組み方と一対一に対応している。

リニアに足し上げることは添付画像のAに対応している。多くに場合にこれで用が足りるが、稀にまずい場合が出て来る。

別の極端な場合がBである。これなら「塵を集めて大きくしてから足し上げること」が起こり易い。

#数楽 n人のトーナメント戦の組み方の形の個数にはCatalan数という名前がついている。

そういう名前を知っていることは、検索時には必要だが、数学を理解していることとは無関係である。

しかし、トーナメント戦の組み方が一見関係無さそうな問題によく出て来ることは数学的に重要である。

#Julia言語 リニアな足し上げは速いのでパフォーマンスを落とさないようにAとBの中間の方式を採用するのが合理的。

https://twitter.com/genkuroki/status/1373173080122564608

#Julia言語 sumひとつだけでも多くのことを学ぶことができる。

多分、大学の学部向けの半年分の講義を sum 関連の話だけで立派に終わらせることも可能。

#Julia言語 で sum は

github.com/JuliaLang/juli…

で実装されている。

めちゃくちゃ地道に細かいことをやっている。

我々一般ユーザーには普段見えない部分を眺めると多くの発見がある。