Python入門講座第5回 : 流れを意のままに

きょうの目標

今日の講座では、while文による繰り返しで、フィボナッチ関数を再定義してみます。

などについてご説明します。

fib（）関数の別定義

これまで使ってきた漸化式を元にしたフィボナッチ数列の関数は次のような物でした。

この再帰的に定義されたfibr(n)は大きなnに対して、効率が悪く、実行速度も遅いという問題があります。 そこで、再帰を繰り返しに展開したフィボナッチ関数を次に示します。 Pythonの繰り返しにはfor文もありましたが、ここではwhile文を使って書いてみました。

Notes:

この実装は　Python.org に掲載されている$n$を超えない最大のフィボナッチ数を求める関数を少し変形して、$n$番目のフィボナッチ数を求める関数に書き換えたものです。

新しいフィボナッチ数列の定義は次のようになりました。 この定義ではPython3の代入式と while文 が使われています。これらの文法について次に解説します。

二つのフィボナッチ数列を求める関数(fibw, fibr)の値を比較してみましょう。

このように二つの関数の値は一致します。

この関数では、一時変数　a,b　に　フィボナッチ数列のある時点iでの値($f_i$)と一つ前の値($f_{i-1}$)を保存します。 その時次のステップi+1での フィボナッチ数列の値($f_{i+1}$)は、a+b, 一つ前のフィボナッチ数列の値($f_{i}$)は　aです。

i 1 2 3 4 ... n-1 n
f_{i}　 1 2 3 5 ... a a+b
f_{i-1} 1 1 2 3 ... b a

例えば、i=3の時、aは3、bは2となっています。

a,　b = a+b, a

を実行すると、aは5、bは3となって、　i=4のフィボナッチ数列の値と、一つ前のフィボナッチ数列になります。 これを n-1回繰り返すと、fib(n)が求まるというわけです。

Note:

ここでもし、ループの中が次のようなプログラムだったとします。

a=a+b
b=a

i=3でaが3、bは2の時にこのプログラムを実行すると, プログラムの実行後は　aは5となりますが、bも5になってしまいます。

ループの中身を

b=a
a=a+b

とすると、今度は、実行後の値はbは3, aは　6 (= 3+3)になってしまいます。

これを避けるためには、ループ中のプログラムを

t=a
a=a+b
b=t

とすることもできますが、pythonでは、

a,b = a+b,b

と簡単に書くことができます。

Note: for文を使ったバージョンはこちら。

Pythonの制御構造

まず、関数定義の中の、while文から見ていきましょう。

while文は、if文、for文と同じく、Pythonでのプログラムの流れを制御するための文です。

C言語などではこのほかにも,repeat-until構文、do-while構文、switch-case構文などをもつ言語もありますが、pythonの制御構造はこの三つ(if, for,while)だけです。 (2021/10/27 追記：3.10ではmatch-case構文が導入されました。)

逐次実行 if文　 for文 while 文
<文>
<文...>		 if <式>:
  <文...>
else:
  <文...>		 for var in iterable :
  <文...>
else:
  <文...>		 while <式>:
  <文...>
else:
  <文...>
逐次実行 if文 for文 while文

Notes: 構造化定理（こうぞうかていり、英: Structure theorem）とは、任意の一入力・一出力関数は、順次（sequence）、選択（ifthenelse）、繰り返し（whiledo）の３つの基本制御構造からなる関数と等価であることを主張する定理である[1]。構造化プログラム定理（structured program theorem） あるいは ベーム-ヤコピーニの定理（Böhm-Jacopini theorem）とも呼ばれる.(wikipediaより）

if文：

if <式> :
    <プログラムブロック-1>
elif <式-2> :
    <プログラムブロック-2>
else:
    <プログラムブロック->

<式>が論理値として真(True)になった時、対応する<プログラムブロックを実行する。 ifあるいはelse節に指定されたどの式も論理値としての値が偽(False)の場合、else節の<プログラムブロック>が実行される。

if-elif-else文
if <条件>:
  <文> ...
elif <条件>:
  <文>
...
else:
  <文>
if-elif-else文

for文：

  1. <繰り返し指定> の要素を<識別子>に設定して、<プログラムブロック>を実行します。
  2. 要素がなくなれば, for文は終了します。
  1. <繰り返し指定> の要素を<識別子>に設定して、<プログラムブロック-1>を実行します。
  2. 要素がなくなれば、<プログラムブロック-2>を実行して、for文を終了します。

while文

  1. <式>の値が真であれば、<プログラム　ブロック> を実行して、ループを繰り返します。
  1. <式>の論理値としての値が真であれば、<プログラム　ブロック1> を実行して、ループを繰り返す。
  2. <式>の論理値としての値が偽であれば、<プログラム　ブロック2> を実行して、ループを終了する。

break文/continue文/pass文/... (Ellipsis)

whileやforで作られたループを処理の途中で中断し、次の要素に進んだり、ループを抜け出すこともできます。 continueおよびbreakはこれらの目的に用意されています。

Books

Note: 書棚の本から目的とする本を内容を確認しながら、探すことを考えてみましょう。 書棚から順> 番に、

  1. 始： 書籍を手に取ります。
  2. タイトルをみて、目的の書籍でないことが明らかなら、次の本をチェックします。(continue)
  3. 内容をチェックして、目的の本であることがわかれば、ここで探索を終了します。(break)
    • 書棚にチェックしていない本がまだあっても、作業を終了します。
  4. 次の書籍がまだあれば、 始: に戻ります。
  5. 書棚の書籍がもうなければ(else節）、この書棚には目的の本はないということです. さあどうしましょう？

break文/continue文/pass文/... (Ellipsis)

whileやforで作られたループを処理の途中で中断し、次の要素に進んだり、ループを抜け出すこともできます。 continueおよびbreakはこれらの目的に用意されています。

break/continue

while文、for文の(else節を除く）　<プログラム　ブロック>はbreak文あるいはcontinue文　を含むことがあります。

for文 + coninue/break while 文 + coninue/break
for-beak文 while-break文

pass文/... (Ellipsis)

プログラム開発中には、詳細は後々に埋めることとして、全体の枠組みだけを作っていくことがあります。pass文や...(Ellipsis)はそのような場合の埋め草として使われます。たとえば、

while condition :
    do_something()
else:
    pass

def do_something(arg):
    ...

といった具合です。pass文も... も 何もしない(No-op) を表現しています。

代入文と代入式

次に、代入式　(n := n-1 )　を　見ていきましょう。

式文

以下の形式のプログラム中の行は 式文　と呼ばれます。

    <式＞　
    <式＞　, <式>, ...

式文では、式を評価します。　対話モードのPythonでは式の評価後の値(あるいは式のタプル）を印刷します。

代入文(assignment statement)

a = b = 1

    a = 1
    b = 1

    a, b = 1, 1

などの文は代入文です。

代入文は変数に式を評価した値を割り当てます。 （Pythonでは代入文より割り当て文と呼んだほうがいいかもしれない。個人的見解です)

<識別子> = <式> 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
    <識別子> = <識別子> =... = <式> 
    <識別子> , <識別子>, ... 　= <式>, <式>,... #式の左右で要素の数が一致していること
    <識別子> , <識別子>, ... 　= <シークエンス>   #識別子の数とシークエンスの要素数は一致していること
    <識別子0> , <識別子1>,...,*<識別子n> = <シークエンス>　　#シークエンスの要素数　は`n`以上

Pythonの代入文はC言語のそれと異なり、値を持ちません。

　代入式 assignment expression　(n := n-1)

walrus(セイウチ） expression とも呼ばれます。　 while文、if文などの条件節で、代入式(<識別子> := <式>)を使うことができます。

代入式では<識別子>への<式>の代入を行い、その式の値が代入式の値となります。

walrus(セイウチ）
セイウチ

(image source: )

Note:

代入式 , walrus(セイウチ） expression はpython 3.8で導入されました。

C-言語では代入文はなく、元々代入式であったので、なにを今更という感じかもしれません。

if v:=fib(10) > 0:
    print(v)

と書いてもエラーにはなりませんが

if v:=(fib(10) > 0):
    print(v)

と解釈されてしまうので、注意が必要です。曖昧さをなくすため、

if (v:=fib(10)) > 0:
    print(v)

とするのが良いでしょう。

Note:

C/C++言語での、代入式を使った次のプログラムと比較してみましょう。

#include <iostream>

int main(void){
    int r=0;
  
    (((r=1) || (r=r+2)) && (r=r+4));
    std::cout << r << std::endl;  
    r=0;
    (((r=1) && (r=r+2)) || (r=r+4));
    std::cout << r << std::endl;
}

比較演算子

if文、while文には 分岐／継続のための条件式が必要です。 条件式は比較演算子や論理演算子を組み合わせてつくることができます。 値の比較はC言語とほぼ同じです。 比較の結果はブール値(True または　 False)です。

    <式> == <式>　　　　　　　　# 　右辺と左辺は同じ値
    <式> != <式>　　　　　　　　# 　右辺と左辺は異なる値
    <式> > <式>
    <式> >= <式>
    <式> < <式>
    <式> <= <式>
    <式> in <式>　　　　　　　　　　　# 左辺が右辺の要素にふくまれる。　 （例：　n in (0,1))
    <式> not in <式>　　　# 左辺は右辺の要素に含まれない。 (例：　n not in (0,1))
    <式> is <式> 　　　　　　　　　# 右辺と左辺は同じオブジェクト
    <式> is not <式>　　　# 右辺と左辺は異なるオブジェクト

オブジェクトの等価性(=　=)と同一性(is)

==（二つの等号)は両辺の式の値が等しいときにTrueとなります。 is は両辺の式が同じオブジェクトであるとき、Trueとなります。

id()は引数に与えられたオブジェクトの　アイデンティティ(多くの場合は、オブジェクトのアドレス）を返します。

a, b はいずれも1,2,3を要素とするリストですが、別のオブジェクトです。

この場合、　a, b は同じオブジェクトです。もちろんその値も一致します。

リストとタプルは違う種類のオブジェクトなので、値としても異なります。

ここで質問です。

a=100
b=100

とした時、

print( a == b, a is b, id(a) == id(b))

はどんな結果になるでしょう？　結果を予想してから実行してみましょう。 解説は次回に。

Python では -5~256の整数は特別扱いされています。これらの整数はシステム初期化時に作成されたオブジェクトが使い回されます。

文字列やタプルなどのイミュータブルなオブジェクトでは、同様な最適化が行われる場合があります。

比較の連鎖

pythonでは　expr1 < expr2 < expr3のような書き方が許されています。この式は、expr1 < expr2かつexpr2 < expr3の時に限ってTrueとなります。 この式は、(expr1 < expr2) and (expr2　<　expr3)とは異なり、 expr2は一度だけ評価 されます。

論理演算(ブール演算）と　整数のビット毎の演算

論理演算はC言語の場合　( &&, || , ! ) とは異なります。　

論理式の値

一般の式に対して、論理演算を行った結果は、ブール値(True/False)とは限りません。　

<式> op <式>

結果の真偽を決めた式と同じタイプの型を持ちます。　　次の例をご覧ください：

再び、 ここで質問です。

((r:=1) or (r:=r+2)) and (r:=r+4)

および

((r:=1) and (r:=r+2)) or (r:=r+4)

の結果はそれぞれ何になりますか？

整数のビット演算

整数に対しては、　ビット毎の論理演算子：　&,　|, ^(exclusive or) , ~ (not)が使えます。 整数同士の論理演算の結果は、先ほど見たように、整数となります。

同じデータにビットごと論理演算子を使った場合、結果は全く異なります。

Note: (~n) + nをビット表現で考えると、　0xffffffff=-1になる。つまり (~n) == -n -1である。

制御などでビット反転が必要な時は、0xffffffffなどとのexclusive or(^)をとる方がいいでしょう。

高速化の手法と実行速度の測定

前回定義したフィボナッチ関数と今回のフィボナッチ関数の実行速度を比べてみましょう。

まずは前回使った定義を再度示します。再帰的に定義されていることから、fibr()と名前を変えてあります。

二つの関数の結果は一致しています。

実行時間の測定

ここでは簡単のために、jupyterのセルマジック　%%timeitを使って、プログラムの実行速度を測ってみます。

セルマジック%%timeitに変わって、ラインマジック%timeitも使えます。 また、timeit モジュールを使って、直接に実行速度を計算することもできます。

timeitモジュールを使って、より詳細にしらべることもできます。

きょうのまとめ

今日の講座では、以下の項目についてご説明しました。

付録

JIT(Just in time compiler)を使ってみる。

pythonプログラムの工夫で実行速度を短縮することができました。さらに実行速度を短縮してくれるツールもあります。

numbaはpythonプログラムをJITでコンパイルし、実行時間を大幅に短縮してくれるモジュールです。 Pythonとは別のツール、llvmコンパイラなど、のインストールが必要です。 Pythonの高速化にはこの他にもcythonなどのツールが存在しています。

ここでは、フィボナッチ関数を高速化してみます。　numbaのjitモジュールを使います。 @jitはpythonのデコレーターという機能で、定義された関数に前処理を付け加えることができます。ここでは前処理として、pythonの関数をnumba.jitでコンパイルして、 機械語バージョンの関数を使って関数を評価します。

最後の行で、fibn()は機械語にコンパイルされ、以降はfibn()の評価にこの機械語プログラムが使われます。

結果は同じになっているようなので、実行速度を測ってみます。

%%timeitはjupyterのセルマジックの一つで、timeitモジュールをつかって、セルの実行時間を測定します。

と大幅に改善されています。

しかし、別の極端な場合(n=0)をみると、jit版の方が時間がかかっています。 機械語のプログラムの呼び出し、戻り値のPythonへの変換などのオーバーヘッドがあるためと考えられます。

これら二つの関数は, n=91までは同じ値を返します。

しかし、n=92の場合を計算してみると、

とfibnはエラーになってしまいます。これは、python3の整数に上限はありませんが、numbaでコンパイルされた関数のfibn中では、オーバーフローにより、正であるべき変数が負になったためです。

jitでコンパイルされる関数でuint64=ulonglongとして、エラーを回避できるか試してみましょう。

とn=92に対しては、正しいあたいがもとまりました。ところが、n=93については、

と異なった値が出てきます。これは結果を16進表示してわかるように、結果がuint64で表現できる最大の値をこえているためです。

いくら高速でもこれでは困ります。 整数を諦めて、　結果を浮動小数点で求めることもできます。

これでとりあえずは結果が真の値から大きくずれてしまうことはありません。(float64の精度範囲で一致） しかし、　n>1475ではfloat64の表現できる数値を超えてしまいます。

関数実行プロファイルをチェックする

プログラムの動作を理解する上で、関数実行プロファイルも役に立つ情報の一つです。

Cythonも試してみましょう

%%cythonセルマジックをつかうことで、 セルの中身をcythonでコンパイルします。 --annotateオプションは cythonの解析結果をみるのに使います。

実行速度を比較してみましょう。

numbaに比べると、速度の低減率は低いですが、生のPythonに比べると、大幅に改善されていることがわかります。 cythonでもlong intのオーバーフローが発生する可能性があります。