Blogs

Pythonプログラミングイントロダクション3章まで読みました。

この章は算術プログラムの章で、近似について学べます。 前回は浮動小数点について書きました。今回はニュートンラフソン法についてです。

ニュートンラフソン法とは

ニュートンと同じ時期にラフソンと言う人も同じ手法を発見したのでニュートンラフソン法と言うそうです。

ある関数f(x)があるとき、f(x) = 0となるxの近似値を求める場合を考えます。このとき推定値をguessとしたとき、 下記の値は元々の推定値よりさらに良い近似値になると言う定理がニュートンラフソン法です。

\[ guess - \frac{p(guess)}{p’(guess)} \]

下記は先日1章を読んだときに出てきた25の平方根の近似を求めたプログラムですが、何気にニュートンラフソン法を使っていました。

1
2
3
4
5
6
7

x = 25
g = 3

while abs(x - g * g) > 1:
    g = (g + x / g) / 2

return g

今回の場合だと下記のf(x)の解を求めれば良いことになります。

\[ f(x) = x^2 - 25 \]

つまりニュートンラフソン法により、より良い近似値を求める式は下記になります。この式は上記Pythonプログラムのwhile文中の記述と同じですね。

\[ guess - \frac{guess^2 - 25}{2 * guess} = \frac{guess + \frac{25}{guess}}{2} \]

ニュートンラフソン法の説明についてはこちらのページが非常にわかりやすかったです。 考え方としてはある関数f(x)の近似値を求める時、最初の推定値の時のf(x)の接線とx軸の交点が、最初の推定値よりもより良い推定値になるという考え方です。 式で考えると下記のようになります。まずは接線の傾きを考えます。接線の傾きは関数を微分したものになります。

\[ guessの時の接線の傾き = f’(guess) \]

この接線とy軸との交点をa、x軸との交点をbとしたとき、

\[ f(guess) = f’(guess)guess + a \]

\[ 0 = f’(guess)b + a \]

上記からbを求めると

\[ f(guess) = f’(guess)guess - f’(guess)b \]

\[ b = \frac{f(guess)guess - f(guess)}{f’(guess)} \]

\[ b = guess - \frac{f(guess)}{f’(guess)} \]

これでニュートンラフソン法の式が導かれました。

まとめ

3章の中からニュートンラフソン法について取り上げました。 式で考えるより図で考えた方が非常に直感的でわかりやすいので、是非参考ページも見てみてください。

Pythonプログラミングイントロダクション3章まで読みました。

3章は算術プログラムの章です。近似について学べます。 全順序について述べられていたりする点、さすがアカデミックだなぁと思いつつ読み進めました。

近似に関しては2文法とニュートンラフソン法が示されています。 2分法は名前から想像しやすいですが、2分探索のようにあり得る値の中間値の計算結果の大小から推定値を移動させていく手法です。 ニュートンラフソン法は初耳でした。

また浮動小数点の説明が非常にわかりやすかったです。実際の計算結果からずれることがある、くらいの理解だったのですが、2進数の都合上なぜ、どのようにずれるかが説明してあって納得でした。

浮動小数点とは

小数を浮動小数点を用いて表現するとは、仮数、基数、指数を用いて表現することになります。 名前の通り小数点の位置が固定ではないことから浮動小数点と言います。

例えば 5/8の場合は、下記のようになります。

\[\frac{5}{8} = 5 * 2^{-3}\]

この場合,仮数は5, 基数は2, 指数は3になります。この場合は誤差は出ないです。そしてコンピュータは2進数で値を表現するので、基数は2となります。

しかし1/10の場合は誤差がどうしても出てしまいます。 下記は1/10を指数部を5,6,7と増やしていった場合の実際の値です。

\[3 * 2^{-5} = 0.9375\]

\[6 * 2^{-6} = 0.9375\]

\[12 * 2^{-7} = 0.9375\]

\[25 * 2^{-8} = 0.9765625\]

このようにいくら指数部の値を増やして行っても0.1にはたどり着けません。 浮動小数点では値によってどうしても誤差が出てしまうわけです。

0.1が実際どのような値となっているかは下記のようにして見ることができます。

1

print( format(0.1, '.55f') )

値は0.1000000000000000055511151231257827021181583404541015625となります。

まとめ

3章の中から特に浮動小数点に関して取り上げました。 金額を計算するときとか、気を付けろぐらいにしか意識していなかった浮動小数点ですが、整理できてよかったです。

Pythonプログラミングイントロダクション2章まで読みました。 2章はPythonの概要を説明し、変数や分岐、繰り返しについて学べる章です。

この辺りは普段からプログラミングをしていると目新しいことはないですが、 曖昧に理解している用語の再確認には有用です。

オブジェクト・型。スカラ・リテラル

自分の場合はスカラとかリテラルがなんとなくな理解で進んでいました。

スカラと非スカラの違いは分割可能かどうかという点で、確かにStringは分割可能なので、非スカラになります。。 逆にint, float, booleanなどは分割不可能でスカラになります。

1
2

# Stringは分割可能
print('abcde'[2:])

なお、Pythonにはchar型はありません。

リテラルは、ソースコード内に値を直接表記したものをいいます。 例えば ‘2’ は数字、‘abc’は文字列を表すリテラルで、ソースコードに直接書かれた文字列とか数字とかのことです。

まとめ

なんとなく使っているリテラルとかスカラとかの用語を整理できた点で有用でした。

独学でコンピュータサイエンスの勉強をしたくてPythonプログラミングイントロダクション第二版を購入しました。全24章、学んだことをBlogにまとめていきながら読み進めていきます。

この本はMIT(マサチューセッツ工科大学)の講義に基づいているもので、プログラミング、アルゴリズムの基礎、さらに流行りのデータサイエンスにも触れられるようです。

まずは1章からみていきます。

第1章　さあ、始めよう

コンピュータが何をするものかから簡単に説明しつつ、コンピュータ上で動作するプログラミング言語がどういったものなのかを簡単に説明しています。

試行錯誤法(guess-and-check algorithm)

アルゴリズムの説明を料理のレシピにたとえつつ、アルゴリズムの一例として試行錯誤法が挙げられていました。 例として挙げていたのは25の平方根を求めるプログラムです。 ポイントは、推定値を実際に二乗した値との差を評価しながら、推定値を (g + x / g) / 2 で更新し試行錯誤していく点です。 実際に二乗した値との誤差がある程度縮まればその値を採用するアルゴリズムです。

下記はPythonの例で、推定値の二乗との誤差が1より小さくなった際にその値を採用するようにしました。

1
2
3
4
5
6
7

x = 25
g = 3

while abs(x - g * g) > 1:
    g = (g + x / g) / 2

return g

プログラミング言語における意味論

意味論についても簡単に触れています。論理学でも学んだことがありますが、Pythonの例と対比されていて非常にわかりやすかったです。 プログラミング言語の構成要素からそれぞれの構成要素の説明がされている箇所です。

プログラミング言語は下記で構成されます。

• 基本構成要素
• 文法
• 静的意味論(static semantics)
• 意味論(semantics)

上記の構成要素について、リテラルや簡単な式を例に説明されています。

プログラムが実行でき意味を持っても、プログラマの意図通りかはまた別の話ですね。

まとめ

第1章ではコンピューターとプログラム、簡単なアルゴリズムの紹介がされていました。 上記の意味論の他に停止問題やチューリング完全にも軽く触れていましたが、本当に軽くです。これについては別の書籍で勉強していこうと思います。

Scalaは昔少し勉強して挫折した経験があります。月並みにいえば、その時こういう本があったらなぁという感想です。

そもそも会社でのポジションはSREなので、Scalaを実務で書くことはほとんどありません。Pythonは書くシチュエーションがありますが、関数型を多用することもありませんでした。

本書の読了が見えてきた頃からこの本を片手にScalaでCodility の問題を解く会社内の集まりに参加させてもらっています。Atcoder にも参加するようになりScalaプログラミングを楽しんでいます。

構成

Scalaの基本的な使い方からScalaプロジェクトを管理する上で必須のsbtやユニットテストなども含まれており、業務でScalaを使い始める人もは網羅的な内容となっています。 もちろんこの本を読んだだけでScalaを使いこなせるわけではなく、最終章の締めくくりにあるようにどんどん書いていくことが必要ですが、この本の内容を知っていたらどれだけとっかかりがスムーズだろうとか思います。

新人が入ってくるこの時期、Scalaをメインの言語として扱っている会社はこの本をとりあえず渡しておくのもありかと思います。

感想

そもそものきっかけはScalaでバックエンドを書いている会社に入ったのでScalaかけるようになりたいなと購入しました。 普段はPythonを利用していて、昔はJavaを書いていた頃がありましたが、基本的にはインフラ関連の業務が多く、Terraformと戯れることが多い毎日です。

この本の前提である1つ以上のプログラミング言語に慣れていることという点はクリアしていますが、第2章のScalaの基礎や第4章のコレクションについてはなかなか苦労しました。ここはひたすら写経ですね。

苦労したとはいえ、著者の方々がScalaに対して敷居を下げようと努力している所は随所に感じました。 サンプルプログラムや図を用いたり言い換えを行ったりして置いてきぼりにならないような配慮が随所に見受けられました。

例外処理や並列処理にも言及してあるのも良買ったです。特に例外処理はTryとかEitherとかこれまでの経験とは一味違う機構をScalaは備えているので助かりましたし、そもそも業務では必須の知識なので。本書の構成としても第3章という前の方に置いてある点から重要視しているのかなと思いました。

並列処理についてもサンプルを写経することで理解が進みました。ただ、競技プログラミングをやっているだけではなかなか登場することがないので、もうちょっと何らかの他の本を読むなりして補強していかないといけないと感じている部分です。

非機能系としてはログに関しては言及がなかったように思います。是非ログについても取り上げて欲しいですね。

そして9章、10章では何をとっかかりに調べれば良いかわからない応用的な部分や、より良いコーディングの指針などが書いてあって、これでScalaはとりあえず書けるという気にさせてくれました。 一旦かける気になったら、あとは書くだけ。おかげで前述の通り、CodilityやAtcoderでScalaプログラミングを楽しんでいます。

まとめ

初学者に優しい本書だからこそ、誤植が一部あった点が残念でした。 技術評論社さんへ連絡したらすぐにサポートページを更新してくれましたが、そもそもサポートページにたどり着くまでのステップはないに越したことはありません。

ただ、その点を差し引いても非常に網羅的で、Scalaへのいろんな障害を乗り越える上で非常に有用な本でした。