また、星田さんの記事に対するコメントである。
今回は短い。と思う。多分。
> 2021/10/22
今日は条件式だったけど練習問題が等比数列。意味は分かるけど等比数列の和の公式とか言われても記憶にございません・・
うん、まぁ誰でもそんなもんでしょ(笑)。
大体このネット時代、大概ネットで検索すればこのテの公式はすぐ見つかるんで、大した問題じゃないです。
しかし、この問題で示唆されてる事が一つある。
数学系のプログラミングをする場合、やっぱ「抽象化のレベルがある」って事なのね。
言い方を変えると、「人の手で最適化してるかどうか」。
あるいは「人間が人間コンパイラになってるか否か」って事。
ここではPythonに浮気して(笑)、例えば良くある、「1から1000まで足してください」と言う問題を考える。sumは使わないでね。
実は「等差数列の公式②」を使うと次のようになる。
def S0(a, n, d = 1):
return (n * (2 * a + (n - 1) * d)) / 2
いわゆる「プログラミング教室」とか「プログラミングの入門書」に書かれてるようなコードだと、等差数列の公式を利用して次のようになっちゃう。
def S1(a, n, d = 1):
i = 1
acc = 0
while i <= n:
acc += a + (i - 1) * d
i += 1
return acc
星田さんみたいなLisper(笑)だとこう書いちゃう。
def S2(a, n, d = 1):
def rec(i, acc):
if i > n:
return acc
else:
return rec(i + 1, acc + a + (i - 1) * d)
return rec(1, 0)
実は後者に行けば行くほど、「式そのまんまの状態」を書いちゃってるのね。
んで、例によってプロファイラを使って「効率」を見てみよう。
ここでは微々たる差、なんだけど、数学的な公式を使った方が圧倒的に速い。
当然なんだよな。って言うのも数学的な公式こそが最適化の極み、だから。
言い換えると、誰かがキチンと紙とペン使って解決してくれたから、だね。
2番目の「フツーのプログラミング手法」だと数学公式には敵わない。
そして3番目の再帰、言い換えると「何も考えないでそのままプログラミング」すると、末尾再帰最適化の機能が無いPythonだとこの中では全然成績が良くなくなる。
でも、計算スピードを出す、って事は言い換えると紙とペンで「最適化」を人力でやらなアカン、って事でしょ。ここではたまたま「数学的に証明してくれた」人が過去にいたお陰で恩恵に授かれるわけなんだけど、毎回毎回そうだとは限らない。
結果、数学的に証明する、って事は「超人的な人間コンパイラになる」って事なんだ。
2番目の一般的なwhileを使った手法だと、やっぱりある程度「問題」を「分解」せなアカン、って事だ。コンピュータに理解可能なように問題を「書き換える」と言うことは、やっぱり最適化の為に「人間コンパイラになってる」って事だな。
3番目はホントものぐさ。何も考えずに言われた通りに式をぶち込んだだけ(笑)。でも末尾再帰最適化を施したプログラミング言語だと2番と良い勝負になるでしょう。
結果ね、再帰って難しいどころか、ものぐさで何も考えたくない人向けなんだよ(笑)。そして関数型プログラミングとは実はものぐさな人向けのプログラミング技法だ。
こうやって効率に差が出るのはプログラミング言語側の最適化技法に問題があると考えちゃうの(笑)。
「なんで人間様がコンパイラがすべきことをせんとアカンのじゃ」と(笑)。
実はわざわざ差を出す為にPython使ったのね。Schemeだと末尾再帰最適化してくれちゃうんで、まさしくものぐさな人の為のプログラミング言語だからこの実験には適さなかったのです。
おお、ちゃんと和になってる！
ここで一つだけTipsを。
っつーか、Lisp語族の恐ろしさを目にするでしょう(笑)。
これは実はこう書ける。
気づいた?
実は今では一般に、Lispでは分数が扱えるの。Lispにはフツーのプログラミング言語が備えていない分数型なるものがあるのだ。
だから分数が関わる問題で、これも「人間コンパイラに」なって小数を入力せんでエエのだ。
殆どのLispでは、
「正確な値は正確な値としてそのまま使えるようにしようぜ」
って事で、例えば「割り切れない」1/3とか、そのまま扱うのを是とする恐ろしいプログラミング言語になってるのだ。
まぁ、最近だとPythonやRubyもLispの後追いして分数を扱えるように機能を拡張してきたけど、扱いやすさではまだまだLispの域には達してないです。
例えばPythonではfractionsモジュールなるものが提供されていて、importすれば分数が扱えるようにはなってるんだけど・・・・・・。
>>> import fractions
>>> fractions.Fraction(1, 3)
Fraction(1, 3)
>>>
とかな。
でも見た目直感的じゃなくって、いまだ全然この辺はLispには勝てないと思う(そもそもimportするのがメンド臭い・笑)。
んでもう一つTips。
今問題がこうだよね。
これをもうちょっと一般化してみる。初項をaとして公比をr、項をnとすれば次のようなプログラムになる。
(define (S a r n)
(/ (- (* a (expt r n)) a) (- r 1)))
で、問題文に従いながら例えば星田さんがやったように具体的にa = 8、r = 1/2、n = 4と言う値を与えると、次のような結果が返される。
> (S 8 1/2 4)
15
>
んで、まぁ、これはこれでイイんですよ。
ただ、問題を読むとaは8、rは1/2なんだけどnは確定値じゃないんだよ・・・・・・。
そしてこの状態だと、nを変える度にaもrも再入力せんとアカンくなる。
こういうのって、これは単純な例なんだけどプログラミングに於いてしばしば出てくるのね。
関数は書いたけど、ある値は固定しておきたいんだけど、一部は新しく与えたい、と言うケース。
こういう時も高階関数の出番です。
今まで見てきたのは引数に関数を取る関数なんだけど、今度は関数を返す関数を作ります。
具体的には次のようにして書く。
(define (S a r)
(lambda (n)
(/ (- (* a (expt r n)) a) (- r 1))))
内側にラムダ式を仕込んで、それの引数をnとする。
そうすれば例えば、
> (define q3 (S 8 1/2))
> (q3 4)
15
> (q3 5)
15 1/2
>
みたいにしてテキトーな変数(この場合はq3)と具体的な初項8と公比1/2を与えたSを束縛して、nを引数にする関数にする事が出来る。8と1/2と言う情報はSに束縛されたまま、になるのね。
こういう機能をクロージャと呼ぶんですが。関数型言語のかなり重要な機能です。
上で関数型プログラミングはものぐさな人の為の方法論と書きましたが。これもそうです。つまり何らかの決定は先送りに出来る、と言うこと。今決めんでもエエじゃないか、と。
上の、元々の問題でも具体的なnは決められていない。つまり先送り対象なのね。そしてこう言う「問題の先送り」もC言語じゃ出来ない事なの。
女の子がいるとするでしょ。C言語ちゃんとLispちゃんと。二人に迫られるわけなんだけど、C言語ちゃんは「今すぐ決めてよ!」と何でもかんでも今すぐの決定を要求する。
一方、巨乳気味のLispちゃんはのんびり「いいわ、私待ってるから」と言ってくれる。
違うか(笑)。
いずれにせよ、ここでも母乳がダダ漏れ、いや、母性がダダ漏れなのです。Lispは「優柔不断」を許容してくれるプログラミング言語なんだ。
もうホント、プログラミングの途中で「今決めたくねぇよ」ってのは割に良く出てくる状況です。そしてそういう時、こうやってクロージャを返す高階関数は割に便利なテクニックなんで、こういう割に明解で簡単な問題を使って覚えていただけたら良いな、と思いました。マル。
あ、一応Pythonでも使えるテクニックです。ちょっと煩雑ですけどね。
from fractions import Fraction
def S(a, r):
def foo(n):
return Fraction(a * r ** n - a, r - 1)
return foo
>>> q3 = S(8, Fraction(1, 2))
>>> q3(4)
Fraction(15, 1)
>>> q3(5)
Fraction(31, 2)
>>>
