Algorithm

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

この章ではプログラムを書く上で避けては通れない関数、スコープ、抽象化についてです。

プログラミングにおいては処理をひたすら書いていくだけではなく、共通の処理は関数として切り出したり、変数のスコープを意識して変数が見える範囲を理解する必要があります。 スコープを理解していないと処理の対象がなんなのか、どこまで参照可能なのかを分からずにプログラミングすることになり、効率が悪くなります。

静的スコープ

Pythonは静的スコープ(レキシカルスコープ)の言語です。本書で出てくるスコープに関連する用語を整理しておきます。

同じ名前の変数 x をプログラム内で使用した場合、それぞれの関数ではどの x が参照されているか見ていきます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def hoge():
    def fuga():
        x = 'fuga'
        print('fuga print x: ' + x)

    def moga():
        print('moga print x: ' + x)


    x = 'hoge'
    print('hoge print x: ' + x)
    fuga()
    moga()
    foo()

def foo():
    print('foo print x: ' + x)


x = 'foo'
hoge()

出力は下記のようになります。

: hoge print x: hoge
: fuga print x: fuga
: moga print x: hoge
: foo print x: foo

下記は全て違うものになります。

• globalで定義された x
• hoge関数で定義された x
• fuga関数で定義された x

下記は同じものになります。

• hoge関数で定義された x とmoga関数で参照された x
• globalで定義された x とfoo関数で参照された x

このように、関数がどこから呼び出されたかに関係なく、どこに定義されているかで変数のスコープが変わるのが静的スコープになります。 また、Pythonではlocal変数やグローバル変数をlocals()関数やglobals()関数で表示させることができます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def hoge():
    def fuga():
        x = 'fuga'
        print('fuga locals: ', locals())

    def moga():
        print('moga locals: ', locals())


    x = 'hoge'
    fuga()
    moga()
    foo()

    print('hoge locals: ', locals())

def foo():
    print('foo locals: ', locals())

x = 'foo'
hoge()
print('globals: ', globals())

結果は下記のようになります。同じ変数名 x でfuga, hoge, globalに定義がされていることがわかります。

: fuga locals:  {'x': 'fuga'}
: moga locals:  {}
: foo locals:  {}
: hoge locals:  {'fuga': <function hoge.<locals>.fuga at 0x1014db440>, 'moga': <function hoge.<locals>.moga at 0x1014db4d0>, 'x': 'hoge'}
: globals:  {'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <class '_frozen_importlib.BuiltinImporter'>, '__spec__': None, '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, '__file__': '<stdin>', '__cached__': None, 'hoge': <function hoge at 0x1014db320>, 'foo': <function foo at 0x1014db3b0>, 'x': 'foo'}

動的スコープ

静的があれば動的もあります。関数がどこから呼び出されたかで変数のスコープが変わるのが動的スコープになります。 bashで変数にlocalをつけると動的スコープになります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#!/bin/bash
x="hoge"

hoge() {
    echo "in hoge x is $x"
}

foo() {
    local x="foo"
    hoge
}

foo
hoge

in hoge x is foo
in hoge x is hoge

foo関数からhoge関数が呼ばれていますが、hoge関数で参照される x はfoo関数が呼び出す直前に設定された x になっています。

まとめ

本書で説明されている静的スコープと対比して、動的スコープがどうなっているかを bashのlocal変数の例で整理してみました。 本書ではlocals()関数で表示されるシンボルテーブルの取り扱いをわかりやすい図で説明してくれています。是非こちらも参照してみてください。

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