JavaおじさんがPythonを使えるようになるまでの全記録（その3）

#はじめに
(その1)のコメントの中でちょっと気になったのが、「PythonってGCないのかな」ってこと。
確かにリテラルを共有するというならJavaほどアホみたいにインスタンスが増え続けるってことはなさそうだけど、そうはいってもいらないオブジェクトは自動で消してほしいよね。

で、「Python メモリモデル」でググったら
こんなページ　に

プライベートヒープの管理は、内部的には Python メモリマネージャ (Python memory manager) が確実に行います。
...
その結果、特定の状況では、Python メモリマネージャがガベージコレクションやメモリのコンパクト化、その他何らかの予防措置といった、適切な動作をトリガできることがあります。

と書いてあるので一安心。まあそりゃそうよね。
Javaと同じく過信は禁物だろうとは思うけれども。
しかし結構メモリ操作の関数は充実してるなあ...

とかつらつら眺めてたら こんなページ が。
ふむふむ、書いてあることの半分くらいはわからないけど（特に下の方）いろいろ工夫はあるものだなあ。
他にいろんなページ眺めてるとやっぱり「循環参照ダメゼッタイ」とかJavaでも見た話は出てくるね。
ここら辺のクラスの設計原則は使えそう。

余談だけどSpring JPAの相互参照オブジェクトをフレームワークで簡単に作れますよーという機能はあれはお手軽だけど結構邪悪な機能だよな...

#MIT教科書の「簡単」とは
このテキスト、全24章あって、今読んでる3章が「簡単な算術プログラム」というタイトルになっている。
確かにこの章で出てくる平方根/立方根の近似値とかニュートン-ラフソン法とか積分もベクトルも出てこないし、実際に記述するべきコードはそんな高度な話じゃないんだけどさー、MITの学生だから耐えられるんだろうなこれｗ
日本人の数学能力って世界水準でもそこそこ高かったはずだけどそれは上位の人らの話であって、数学つらい人には向かないテキストだと思う。

まあでもそういう人はMicrosoftあたりが進めている機械学習のカジュアル化の果実を利用すればいいので住み分けはいつも通りできるような気もするしな。
APIがトラブったときにどう対処するかという話はあるけれども。

#ニュートン-ラフソン法
さて、続いてのお題は

ニュートン-ラフソン法のコードはすでに提供されていて、(その2)で見た二分探索法とどっちが計算効率がいいか追っかけるコードを追加しろというお話。
問題としては超簡単。

まず二分探索法で25の平方根を求めたときの実行結果がこんな感じ。

low = 0.0 high = 25 ans = 12.5
low = 0.0 high = 12.5 ans = 6.25
low = 0.0 high = 6.25 ans = 3.125
low = 3.125 high = 6.25 ans = 4.6875
low = 4.6875 high = 6.25 ans = 5.46875
low = 4.6875 high = 5.46875 ans = 5.078125
low = 4.6875 high = 5.078125 ans = 4.8828125
low = 4.8828125 high = 5.078125 ans = 4.98046875
low = 4.98046875 high = 5.078125 ans = 5.029296875
low = 4.98046875 high = 5.029296875 ans = 5.0048828125
low = 4.98046875 high = 5.0048828125 ans = 4.99267578125
low = 4.99267578125 high = 5.0048828125 ans = 4.998779296875
low = 4.998779296875 high = 5.0048828125 ans = 5.0018310546875
numGuesses = 13
5.00030517578125 is close to square root of 25

numGuesses = 13なので13回のループが行われている。
同様にループ回数記録を追加したコードが以下。
やってみたら計算過程もよくわからんので、そこの表示も追加してみた。

3-4.py

# ニュートン-ラフソン法の実装
# x**2 -25 = 0 で誤差がepsilon以下になるxを求める
epsilon = 0.01
k = 25.0
guess = k/2.0
numGuesses = 0
while abs(guess*guess - k) >= epsilon:
    numGuesses += 1
    print('guess =', guess)
    guess = guess - (((guess**2) - k)/(2*guess))
print('numGuesses =', numGuesses)
print('Square root of', k, 'is about', guess)

ちなみに、ニュートン-ラフソン法の一番のキモはこの1行。

3-4.py（抜粋）

    guess = guess - (((guess**2) - k)/(2*guess))

この計算式はいわゆる「逐次近似」を計算してより良い近似値を計算するためのもの。
今回は25の平方根なのでx^2-25=0の方程式の解を探すために、

1.x^2-25をx=guessを代入して計算
2.元の方程式の左辺を微分した2xにx=guessを代入して計算
3.1の計算結果を2の計算結果で割ったものをもとのguessから引いて代入

という計算を繰り返している。
このあたりの詳細かつ数学的な説明はおれの手には余るのでアルゴリズム関係の本とか見てくださいｗ
で、たとえば立方根の計算となるとおおもとの方程式がx^3-25=0ということになるので、上記1と2の式が変わるし、25以外の平方根を求めようとすると1の中身が変わってくることになる。

で、実行結果はこうなる。

uess = 12.5
guess = 7.25
guess = 5.349137931034482
guess = 5.011394106532552
numGuesses = 4
Square root of 25.0 is about 5.000012953048684

ループ回数が3分の1以下になっているし、実は近似の精度もこっちが上。
計算量が少なくて済むということはそのためのリソースも少なくて済むということにもつながるのでこれ結構重要なポイントだし精度も上がるのでどっち採用するべきかっていえばまあこっちだよね。

というわけでここで3章おしまい。
あ、浮動小数点の誤差の話は知ってるのでいいです。