目次と前回の記事
これまでに作成したモジュール
以下のリンクから、これまでに作成したモジュールを見ることができます。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| util.py | ユーティリティ関数の定義。現在は gui_play のみ定義されている |
| tree.py | ゲーム木に関する Node、Mbtree クラスの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
ルールベースの AI の一覧
ルールベースの AI の一覧については、下記の記事を参照して下さい。
繰り返し処理の使い分け
前回の記事で、単純な繰り返し処理であれば、while 文や for 文を使ったほうが良いということを説明しまたが、具体的にどのような処理が単純な処理であるかについて言及していませんでした。そこで、今回の記事では繰り返し処理の使い分けについて説明します。
なお、繰り返し処理 を行う際に、どの方法を使えば良いか については、特定の性質を持っていることが、特定のアルゴリズムを利用すべきであるという風に、完璧に分類できるわけではありません。今回の記事の説明は、あくまで 一つの目安 だと思ってください。
for 文による繰り返し処理の性質
for 文は、前回の記事で説明したように、あらかじめ繰り返しを行う回数が決まっている ような処理を 簡潔に記述できる という性質があります。
for 文は、for 変数 in 反復可能オブジェクト: のように記述することからわかるように、列挙することができるデータ1 に対する繰り返し処理を行うのに向いています。
具体的には、以下のような処理を行う際は、for 文が向いている可能性が高いでしょう。いずれもあらかじめ数が決められているものに対して繰り返し処理を行います。
-
range(10)のように、繰り返しのたびに、数値が規則正しく増減する処理 - list の要素のように、あらかじめ決められているデータに対する繰り返し処理
そのような繰り返し処理は良く行われるので、for 文は繰り返し処理の中で最も良く使われるのではないかと思います。
繰り返しの処理の独立性と処理の順番
あらかじめ数が決められているデータに対する繰り返し処理を行う際に、そのデータに対して、どのような順番 で繰り返しを行うかが 重要な場合 と、そうでない場合 があります。
繰り返しの処理の順番が重要かどうかは、処理の独立性 によって決まります。
処理が独立な場合は順番は重要ではない
繰り返しの 処理が独立 しているとは、ある回で行われる繰り返し処理 が、別の回 で行われる繰り返し処理に 全く影響を与えない ということを表します。
具体例として、〇×ゲームの ゲーム盤 のそれぞれのマスを 画像で描画 する繰り返し処理は 独立しています。例えば (0, 0) のマスを描画 する際に、他のマスの描画処理 は 全く影響しません。そのような場合は、どのような順番でマスを描画しても結果は変わりません。
for 文 は、繰り返しの処理が処理が 独立している場合に向いています。
例えば、Marubatsu_GUI クラスの draw_board でゲーム盤のマスを描画するプログラムは下記のようになっています。
1 # ゲーム盤のマークを描画する
2 for y in range(mb.BOARD_SIZE):
3 for x in range(mb.BOARD_SIZE):
4 color = "red" if (x, y) == mb.last_move else "black"
5 Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color, lw=lw)
4、5 行目で行われる (x, y) のマスを描画する繰り返しの処理は、他のマスの描画の処理に影響を与えない 独立した処理 です。従って、下記のプログラムの 2、3 行目のように、x や y の range の順番を逆順2にしてもプログラムは正しく動作します。なお、本記事では行いませんが、興味がある方は下記のプログラムを入力して gui_play を実行すると、ゲーム盤が正しく表示されることを確認してみて下さい。
1 # ゲーム盤のマークを描画する
2 for y in range(mb.BOARD_SIZE - 1, -1, -1):
3 for x in range(mb.BOARD_SIZE - 1, -1, -1):
4 color = "red" if (x, y) == mb.last_move else "black"
5 Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color, lw=lw)
修正箇所
# ゲーム盤のマークを描画する
-for y in range(mb.BOARD_SIZE):
+for y in range(mb.BOARD_SIZE - 1, -1, -1):
- for x in range(mb.BOARD_SIZE):
+ for x in range(mb.BOARD_SIZE - 1, -1, -1):
color = "red" if (x, y) == mb.last_move else "black"
Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color, lw=lw)
また、下記のプログラムのように、for 文の入れ子の順番を変えても正しく動作します。
1 # ゲーム盤のマークを描画する
2 for x in range(mb.BOARD_SIZE):
3 for y in range(mb.BOARD_SIZE):
4 color = "red" if (x, y) == mb.last_move else "black"
5 Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color, lw=lw)
修正箇所
# ゲーム盤のマークを描画する
-for y in range(mb.BOARD_SIZE):
+for x in range(mb.BOARD_SIZE):
- for x in range(mb.BOARD_SIZE):
+ for y in range(mb.BOARD_SIZE):
color = "red" if (x, y) == mb.last_move else "black"
Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color, lw=lw)
処理が独立でない場合
繰り返し処理が 独立でない 場合は、一般的 には 順番が重要 になります。順番が重要になる理由について少し考えてみて下さい。
その理由を箇条書きにすると以下のようになります。
- 独立ではないということは、A 回目 で行われた繰り返し処理の結果が、A より後の 回で行われた B 回目 の繰り返し処理の結果に 影響を与える ということを意味する
- B 回目で行われていた処理を A 回目より先に行ってしまうと、B 回目 の処理が A 回目の処理の影響を受けなくなってしまう
- その結果、B 回目の処理の結果 が、入れ替える前から 変化してしまう可能性が生じる
例えば、〇× ゲームの ゲーム盤を文字列で表示 する場合は、繰り返しの処理は 独立していません。画像で描画する場合は独立しているのに、文字列で表示する場合は独立していない理由について少し考えてみて下さい。
〇× ゲームのゲーム盤を文字列で表示する場合は、Marubatsu クラスのインスタンスを print で表示します。その際に呼び出される Marubatsu クラスの __str__ メソッドは下記のように定義されています。なおターン数などの表示の部分は省略しました。
1 def __str__(self):
略
2 for y in range(self.BOARD_SIZE):
3 for x in range(self.BOARD_SIZE):
4 lastx, lasty = self.last_move
5 if x == lastx and y == lasty:
6 text += self.board[x][y].upper()
7 else:
8 text += self.board[x][y]
9 text += "\n"
10 return text
上記の処理では繰り返しの処理の 6、8 行目で、ゲーム盤を表す文字列を代入する text に (x, y) のマスを表す 文字列を結合 するという処理を行っています。この処理によって、繰り返しの処理が行われるたびに text の値が更新されるので、ある繰り返しの回で行った処理が、後の繰り返しの処理を行う際の text の値に影響を与えます。また、文字列の結合 という処理は、処理が行われる順番 によって 結果が変化 します。
例えば、空文字に対して "o"、"x"、" " という 3 つの文字列を結合するという処理は、下記のプログラムのように、結合の順番によって結果が変化 します。
print("" + "o" + "x" + " ")
print("" + "x" + " " + "o")
実行結果
ox
x o
上記が文字列でゲーム盤を表示する場合は独立していない理由です。
例えば、上記のプログラムの 3 行目を for x in range(self.BOARD_SIZE - 1, -1, -1): のように修正すると、各行が 左右に反転 したゲーム盤が表示されてしまうことになります。
また、上記のプログラムの 2 行目と 3 行目を入れ替える と、x 座標と y 座標が反転したゲーム盤 が表示されてしまうことになります。
処理が独立していなくても順番を変更できる条件
繰り返しの処理が独立していない場合でも、順番が重要ではないことがあります。その例の一つが下記のプログラムの 0 から 9 までの整数の合計を計算する繰り返し処理です。
1 total = 0
2 for i in range(10):
3 total += i
4
5 print(total)
行番号のないプログラム
total = 0
for i in range(10):
total += i
print(total)
実行結果
45
上記のプログラムは、繰り返し処理の 3 行目で total という変数に i を加算しているので、先程の文字列でゲーム盤を表示する場合と同様に、繰り返しの処理は 独立していません。しかし、この場合は下記のプログラムのように、順番を変えて、9 から 0 の順番で合計を計算しても 正しい計算が行われます。その理由について少し考えてみて下さい。
total = 0
for i in range(9, -1, -1):
total += i
print(total)
修正箇所
total = 0
-for i in range(10):
+for i in range(9, -1, -1):
total += i
print(total)
実行結果
45
順番を変えても正しい計算が行われる理由は、足し算 という計算が、順番を変えても答えが変わらない という性質を持っているからです。例えば 0 に 1、2、3 という 3 つの整数を加算する場合に、下記のように順番を変えても同じ答えになります。
print(0 + 1 + 2 + 3)
print(0 + 2 + 3 + 1)
実行結果
6
6
足し算のように、順番を入れ替えても計算結果が変わらないような性質の事を 交換法則 と呼びます。足し算や掛け算は交換法則を持ちますが、引き算や割り算は下記のように、交換法則を持ちません。また、Python の 文字列の結合 も 交換法則を持ちません。
$1 - 0 ≠ 0 - 1$
$2 ÷ 1 ≠ 1 ÷ 2$
繰り返し処理の中で独立していない すべての処理 が、交換法則を持つ場合 は、順番を変更しても構わないという事です。ただし、独立していない処理が交換法則を持つかどうかが簡単にはわからないような場合が多いので、独立していない場合は、基本的には順番通りに処理を行ったほうが良い でしょう。
0 から 9 までの合計の計算の場合は、3、1、6、7、2、8、0、4、9、5 のように、0 から 9 までの整数が 1 回ずつ出現さえすれば、どのような順番で合計を計算しても計算結果は変わりません。ただし、そのような計算を行うプログラムを記述するのは面倒なので、特に理由がない限りはそのような計算は行わないほうが良いでしょう。
for 文によるボトムアップな繰り返し処理の記述
独立ではない繰り返し処理 で計算を行う際に、実際に 計算を行うことができる順番 で計算を行うアルゴリズムの事を、ボトムアップ（bottom up）な処理と呼びます。
一般用語としてのボトムアップは、会社などで複数の部署が協力して仕事を行う際に、実際の作業を行う現場の意見をもとに意思決定を行うというやり方のこと表します。下から上に意見を伝えるので下意上達も呼ばれます。
逆に、経営陣などの上層部が意思を決定して、部下に伝えるというやり方のことをトップダウンや、上意下達と呼びます。
なお、プログラミング用語としてのボトムアップやトップダウンの意味と、一般用語としての意味は若干異なる点に注意して下さい。
for 文 や while 文 は、ボトムアップな繰り返し処理を記述するのに向いており、トップダウン な繰り返し処理の記述は次回の記事で説明しますが、再帰呼び出しが向いています。
for 文や while 文でトップダウンな繰り返し処理を記述することもできますが、再帰呼び出しを使った場合と比べて記述が複雑になります。
そこでボトムアップなアルゴリズムで、 for 文による独立していない繰り返し処理を記述する方法について説明します。
独立していない繰り返し処理 を記述する場合は、過去に行った繰り返し処理の結果を覚えておく 必要があります。そのため、独立していない 繰り返し処理の 記述 は、その分だけ独立している繰り返し処理の記述の処理よりも 複雑になります。
ただし、直前の繰り返し処理の結果のみ が次の繰り返し処理の計算に影響するような場合は、例外的に for 文によって 簡潔に繰り返し処理を記述 することができます。
そのことを示すために、下記の 2 種類の独立していない繰り返し処理を for 文で記述する方法を紹介します。
- 直前の繰り返し処理のみ の結果を使って、次の繰り返し処理の計算を行う
- 直前の 2 回分 の繰り返し処理の結果を使って、次の繰り返し処理の計算を行う
漸化式
独立していない繰り返し処理を、言葉で説明する とどうしても 記述が長くなってしまいます。また、説明を正確に 行おうとすればするほど、表現が まわりくどく、長くなってしまいがち です。そのような場合は、数式で表現 することで 簡潔に記述する のが一般的です。
数学が嫌いな人にとっては、数式や記号は意味不明な暗号のように見えるかもしれません。実際に筆者もものすごい複雑な数式を見ると頭が痛くなることが良くありますが、簡単な数式や記号 であれば、慣れれば 言葉で説明するよりもはるかにわかりやすくなる ので、本記事でも以後は必要に応じて数式や記号を利用することにします。
独立していない 繰り返し処理は、以下のような性質を持つ、漸化式（ぜんかしき）という式で表現することができます。
- 同じ内容の計算を何度も繰り返すことで、何かの値を計算することを表現する式のこと
- n 回目の繰り返し で行われた計算結果の事を $x_n$ のように、繰り返しの回数 を右下の小さな 添え字で表現 する
- n は繰り返しの回数を表すので、0 以上の整数3が入る
- $x_n$ は それ以前の繰り返し で行われた 計算結果を用いた式 で計算される4
- ただし、$x_0$ のように、それ以前に行われた計算が存在しない場合は、初期値 と呼ばれる 特定の値を設定 する
なお、$x_n$ の $x$ の部分の アルファベットの記号 は、何を使っても構いません が、特別な理由がない場合は $a$、$b$、$c$ や $x$、$y$、$z$ などが良く使われます。
$x_n$、$n$ は 0 以上の整数
のように、添え字 によって 番号が付けられた、順番に並んだ数 のことを 数列 と呼びます。また、数列の それぞれの数値 の事を 項（こう） と呼びます。
数列には、端が存在するものと存在しないものがあります。例えば、自然数は 1 から始まるので片側に端がある数列ですが、整数は端がない数列です。
漸化式で表現 される $x_n$ は、並び方に 規則性がある 数列の一種ですが、サイコロの出目を記録 した数列のように、式で表現できない規則性のない数列 もあります。
n 回目の計算結果を n の関数 と考えて$x_n$ ではなく、$f(n)$ のように表記することもできます。ただし、$x_n$ のように表記した場合は、添え字の n が 整数であるという慣習 がありますが、$f(n)$ のように関数として記述した場合に、n が整数であるという慣習はない ので、「$f(n)$ ただし、n は 0 以上の整数とする」のように記述する必要があります。そのため、本記事では $x_n$ の方を採用することにします。
わかりづらいと思いますので、具体例を挙げます。0 から n までの整数の合計 の計算結果を $x_n$ と表記した場合、$x_n$ は以下のような性質を持ちます。
- 0 から n までの整数の合計は、0 から n - 1 までの整数の合計に n を足したものである
- 0 から n までの整数の合計は $x_n$ と表記される
- 0 から n - 1 までの整数の合計は $x_{n-1}$ と表記される
- 従って、$x_n = x_{n-1} + n$ と表記できる
- ただし、$x_{-1}$ は存在しないので $x_0 = x_{-1} + 0$ という式は計算できない
- 0 から 0 までの整数の合計は 0 なので、初期値として $x_0 = 0$ を設定する
上記から、0 から n までの整数の合計の計算結果を $x_n$ を表す漸化式は以下のように記述できます。また、このように記述することで、言葉で記述すると「0 から n までの整数の合計」のような 長い表記 を、$x_n$ のように 簡潔に表現することができる ようになります。
$x_n = x_{n-1} + n$、$x_0 = 0$
漸化式の $n$ を時間と考えると、漸化式は過去のデータを元に現在のデータを計算する式だと考えることもできます。そのため、世の中の現象を、漸化式を使ってうまく表現できる場合がよくあります。
例えば、時速 10 km/h で走る車の $t$ 時間後の走行距離を $x_t$ とすると、$x_t$ は、1 時間ごとに 10 増えるので下記の漸化式で表現することができます。
$x_t = x_{t - 1} + 10$、$x_0 = 0$
漸化式を、過去のデータを利用しない形の式 で表現しなおしたものを 一般項 と呼びます。例えば上記の、$x_t = x_{t - 1} + 10$、$x_0 = 0$ という漸化式の一般項は、誰でも簡単に $x_t = 10t$ であることがわかると思います。
一般項を求めることができれば、繰り返し処理を行わなくても、素早く $x_n$ を 求めることができる ようになりますが、一般項を求めることが 困難な場合 や、求めることが 不可能な場合 があります。
例えば、下記のサイコロを n 回振った場合の合計を $x_n$ を計算する漸化式の一般項を求めることは明らかに不可能でしょう。
$x_n = x_{n - 1} + サイコロの出目$、$x_0 = 0$
一般項を求めることが困難な場合や、そもそも求めることができない場合は、繰り返し処理によって $x_n$ を求める必要があります。
漸化式よりも一般項のほうがわかりやすいと思うかもしれませんが、そうとは言い切れません。例えば、下記は 0 から n までの整数の合計を表す $x_n$ の一般項ですが、この式から $x_n$ が 何を表す式であるか を 直観的に理解するのは困難 でしょう。
$x_n = n(n + 1) / 2$
一方、下記の漸化式の場合は、直前の計算結果に n を足すという式なので、0 から n まで順番に n 足した数であることが、直観的に見えるような式になっています。
$x_n = x_{n - 1} + n$、$x = 0$
このように、漸化式と一般項 は、同じ計算 を 別の側面から表す式 だと考えることができます。また、どちらがわかりやすいかについては一概にはいえません。
for 文を使った漸化式の計算
下記の漸化式に従って、0 から 5 までの整数の合計 を表す $x_5$ を、for 文 を使って ボトムアップな順番 で計算する方法を示します。
$x_n = x_{n - 1} + n$、$x_0 = 0$
この漸化式では、$x_n$ を計算するためには、一つ前の $x_{n - 1}$ の値を計算する必要があります。従って、ボトムアップな順番での $x_5$ の計算は、添え字を 0 から n まで 1 ずつ増やしながら下記の手順で計算を行います。
- $x_0 = 0$
- $x_1 = x_0 + 1 = 0 + 1 = 1$
- $x_2 = x_1 + 2 = 1 + 2 = 3$
- $x_3 = x_2 + 3 = 3 + 3 = 6$
- $x_4 = x_3 + 4 = 6 + 4 = 10$
- $x_5 = x_4 + 5 = 10 + 5 = 15$
$x_n$ は インデックスが n の list の要素 で表現することができるので、上記の処理をそのままの形で Python のプログラムに直すと、下記のようなプログラムになります。
-
1 行目：
xを空の list で初期化する -
2 行目：
xの 0 番の要素に 0 を追加する（$x_0 = 0$ の処理） -
3 行目：
nを 1 から 5 まで増やしながら for 文で繰り返す -
4 行目：
xのn番の要素にx[n - 1] + nを代入する（$x_n = x_{n - 1} + n$ の処理） -
5、6 行目：
xとx[5]を表示する
1 x = []
2 x.append(0)
3 for n in range(1, 6):
4 x.append(x[n - 1] + n)
5
6 print(x)
7 print(x[5])
行番号のないプログラム
x = []
x.append(0)
for n in range(1, 6):
x.append(x[n - 1] + n)
print(x)
print(x[5])
実行結果
[0, 1, 3, 6, 10, 15]
15
実行結果から、x の list の要素に順番に $x_0$ ~ $x_5$ 代入されていることと、x[5] に $x_5$ の値が正しく代入されていることが確認できます。
dict を使った記述
上記では list の要素に $x_n$ の値を代入して記録しましたが、list は 要素を追加 する際に、x.append(0) のように append メソッドで行う必要がある ため、どのインデックスの要素を追加したかがわかりづらい という欠点があります。dict であれば、x[0] = 0 のように、$x_n$ を追加する際に、n をキーとして直接記述 して値を追加できるので、上記のプログラムは dict を使えば下記プログラムの 2、4 行目のように わかりやすく記述 することができます。
-
1 行目：
xを空の dict で初期化するように修正する - 2、4 行目：$x_0 = 0$ と $x_n = x_{n - 1} + n$ を表す式をそのまま記述するようにする
1 x = {}
2 x[0] = 0
3 for n in range(1, 6):
4 x[n] = x[n - 1] + n
5
6 print(x)
7 print(x[5])
行番号のないプログラム
x = {}
x[0] = 0
for n in range(1, 6):
x[n] = x[n - 1] + n
print(x)
print(x[5])
修正箇所
-x = []
+x = {}
-x.append(0)
+x[0] = 0
for n in range(1, 6):
- x.append(x[n - 1] + n)
+ x[n] = x[n - 1] + n
print(x)
print(x[5])
実行結果
{0: 0, 1: 1, 2: 3, 3: 6, 4: 10, 5: 15}
15
実行結果から、正しい答えが計算されていることが確認できます。なお、dict を利用した場合は 他にも、$x_n$ の $n$ が 負の値になるような場合にも対応できる という利点があります。
メモリの消費に関する問題点
先程、下記のような説明を行いました。
独立していない繰り返し処理を記述 する場合は、過去に行った繰り返し処理の結果を覚えておく必要 があります。そのため、独立していない繰り返し処理の記述は、独立している繰り返し処理の記述の処理よりも複雑になります。
実際に上記のプログラムでは、$x_5$ の計算を行う際に、$x_0$ から $x_4$ の計算結果を x に記録しています。ただし、このように過去の計算結果をすべて記録するという方法では、$n$ が 非常に大きな数になった場合 に、n 個のデータを記録しておかなければならない という問題が発生します。例えば 0 から 1 億まで の合計を計算しようと思ったばあいは、1 憶個の数値を記録しておく必要が生じます。
具体例を挙げます。下記のプログラムは 0 から 1 憶までの合計を計算するプログラムです。なお、計算結果の表示は重要ではないので省略しました。
x = {}
x[0] = 0
for n in range(1, 100000001):
x[n] = x[n - 1] + n
上記のプログラムを実行委すると、x に 1 億個の数字が記憶されるので、それだけのメモリが消費 されます。上記の実行後に筆者のパソコンでアプリケーションの消費メモリを調べることができる Windows のタスクマネージャー5を表示した所、下図のように 12833.9 MB = 約 12 GB ものメモリが消費されていることが確認できました
このように、メモリを多く消費しすぎると パソコン全体の処理速度が著しく遅くなる 場合が生じます。そのため、大量のデータを計算 する場合は、プログラムが 無駄なメモリを消費しないように気を付ける 必要があります。
なお、JupyterLab を再起動すると、それまでに Python で消費していたメモリが解放されます。画像は省略しますが、上記の処理を実行後に JupyterLab を再起動したところ、Python のメモリの消費が 約 50 MB まで減りました。
メモリの消費に対する処理の最適化
メモリの無駄な消費や、無駄な計算処理など、必要のない 無駄な処理を行わないようにプログラムを修正すること を、プログラムの 最適化 と呼びます。
$x_n = x_{n - 1} + n$ のような、直前の繰り返し処理の結果 である $x_{n-1}$ のみを利用する漸化式を for 文で記述する場合は、無駄なメモリを消費しない ような 最適化を行うことができます。
$x_n = x_{n - 1} + n$ という式から、$x_n$ を計算する際に $x_{n - 1}$ 以外の過去の計算結果は必要がない ことがわかります。従って、この計算を行う際に、過去のすべての計算結果を記録しておく必要はありません。
具体的には、0 から 5 までの整数の合計を計算するプログラムは、下記のように記述することができます。なお、下記のプログラムの変数は以下のような意味を持ちます。
-
prevx：直前（previous）に計算した $x_n$ の計算結果 -
x：次に計算する $x_n$ を代入する変数
それぞれの行の意味は以下の通りです。
- 2 行目：繰り返しの処理では、$x_1$ から $x_5$ の順番で $x_n$ を計算する
-
1 行目：繰り返しの処理で最初に計算するのは $x_1$ なので、その前の $x_0$ の値である 0 を
prevxに代入する -
3 行目：漸化式 $x_n = x_{n - 1} + n$ の記号と変数は、
xが $x_n$、prevxが $x_{n-1}$、nが $n$ に対応するので、x = prevx + nによって、n 番目の $x_n$ の値がxに代入される -
4 行目：次の繰り返し処理では、$x_{n+1}$ が計算されるが、その時には
xに代入されている $x_n$ が $x_{n+1}$ の 1 つ前の計算結果になる。そのため、次の繰り返し処理が正しく行えるようにprevxにxを代入して更新する
prevx = 0
for n in range(1, 6):
x = prevx + n
prevx = x
print(x)
実行結果
15
上記のプログラムを実行すると、実行結果のように、0 から 5 までの整数の合計が正しく表示されます。
さらなる最適化
先程のプログラムは、下記のプログラムのように prevx を削除 することができます。また、下記の x を total に置き換える と、これまでに記述してきた 0 から 特定の整数までの合計を計算する プログラムと同様 になります。
x = 0
for n in range(1, 6):
x += n
print(x)
このように記述できる理由は、以下の通りです。
- 最初に
xに 0 を代入しておくことで、最初の $x_1$ の計算が、x = x + 1すなわちx = 0 + 1 = 1になるので、正しく計算できる - 下記の修正前のプログラムでは、3 行目で
prevxに $x_n$ を表すxを代入した後で、次の繰り返し処理で、$x_{n+1}$ を計算するためにx = prevx + iを計算しているが、prevxとxにはどちらも $x_{n+1}$ の 1 つ前の $x_n$ の値が代入されているので、x = prev + iとx = x + iは同じ計算を行う - 従って、2 行目の
x = prev + iはx = x + i、すなわちx += iに置き換えることができる - 2 行目を
x += iに置き換えると、3 行目のprevx = xは不要になる - 上記から、
prevxは不要である
for n in range(1, 6):
x = prevx + n
prevx = x
タスクマネージャーの画像は省略しますが、下記のプログラムを実行して 1 憶までの整数の合計を計算しても、Python の メモリの消費はほとんど増えません。
また、先程のプログラムは 1 億個のデータを list に記録する必要があったので、筆者のパソコンでは処理時間が約 30 秒ほどかかりましたが、下記のプログラムではそのような処理を行う必要がないので、処理時間は約 11 秒でした。このように メモリの消費の最適化 を行うことで、処理時間を短くする ことができました。
x = 0
for n in range(1, 100000001):
x += n
print(x)
実行結果
5000000050000000
x = prevx + i という式の方が、x += i よりも、行う計算の 意図がわかりやすいという利点 があります。x += i という式は、x = x + i という式を簡略化したものですが、この式は 左辺 の x が $x_i$ を、右辺の x が $x_{i - 1}$ のように、同じ x が別の意味している点 が慣れないうちはわかりづらいのではないかと思います。
とはいえ、慣れれば prevx を削除しても十分理解できると思いますし、合計の計算を行うプログラムで上記のような prevx を記述することはまずないので、prevx を削除した記述方法を使ったほうが良いでしょう。
なお、このように prevx を削除できるのは、$x_{i}$ を表す prevx の値 が、次の $x_{i+i}$ を計算するために 利用された後で、二度と使われることがない からです。そのため、わざわざ x に代入されている $x_{i}$ の値を後で利用できるように取っておくために、prevx という変数を用意する必要はありません。この次で説明するように、$x_{i}$ の値が、 $x_{i+i}$ を 計算した後でも必要になる場合 は、prevx を 削除することはできません。
直前の 2 回分の繰り返し処理の結果を使う例
直前の 2 回分の繰り返し処理の結果を使う 有名な例として、フィボナッチ数が挙げられます。フィボナッチ数とは、イタリアの数学者のフィボナッチが考案した以下のような漸化式で表される数です。なお、フィボナッチを表す記号には大文字の $F$ が良く使われるので本記事でもその記法に倣いました。
$F_n = F_{n-1} + F_{n-2}$、$F_0$ = 1、$F_1$ = 1
フィボナッチ数列は「0、1、1、2、3、5、8、13、21、34、・・・」のようになります。
フィボナッチ数は、下記のような兎の問題の答えとなる数で、数学的には他にも様々な重要な意味を持ちます。
- 1つがいの兎は、産まれて2か月後から毎月1つがいずつの兎を産む。
- 兎が死ぬことはない。
- この条件の下で、産まれたばかりの 1 つがいの兎は 1 年の間に何つがいの兎になるか？
ただし、繰り返しの処理の説明 を行う上で、フィボナッチ数の 数学的な意味を理解する必要はありません ので、意味がわからない人は計算の方法だけに注目して下さい。また、フィボナッチ数という用語を使うと難しそうな印象を与えるような気がするので、以後は原則として $F_n$ という 記号のみを使って説明する ことにします。
参考までに、フィボナッチ数の Wikipedia のリンクを下記に示します。
for 文によるフィボナッチ数の計算
まず、for 文によって $F_n$ を計算する下記のような関数を定義する事にします。
名前：for 文でフィボナッチ数（Fibonacci number）$F_n$ を計算するので、fib_by_f とする
処理：引数で指定された $F_n$ を計算する
入力：仮引数 n に計算する $F_n$ の $n$ を代入する
出力：計算した $F_n$ を返す
メモリの消費を気にしない のであれば、下記のプログラムのように記述できます。先ほどの合計を計算するプログラムとの主な違いは以下の通りです。
- 関数になった
- 変数
xの名前をfに変更した -
4 行目：
f[1]を 1 で初期化する必要がある -
5 行目：繰り返し処理を 2 から始めるようにした。
nが引数の名前として使われているので、for 文の変数の名前をiに変更した -
6 行目：
f[i]を計算する式が異なる
def fib_by_f(n):
f = {}
f[0] = 0
f[1] = 1
for i in range(2, n + 1):
f[i] = f[i - 1] + f[i - 2]
return f[n]
上記の実行後に、下記のプログラムで $F_0$ ~ $F_{9}$ までを計算すると、実行結果のように、正しい計算が行われることが確認できます。
for i in range(10):
print(f"fib({i}) = {fib_by_f(i)}")
実行結果
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
もちろん、このプログラムは先ほどと同様に n が大きくなるとメモリを大量に消費 するという欠点があるので、メモリを消費しないように 最適化するこ とにします。
$F_n = F_{n-1} + F_{n-2}$ という漸化式からわかるように、1 つ前 と、2 つ前 の合計を計算するという処理の繰り返しです。そのため、$F_n$ を計算するためには、1 つ前と 2 つ前 の $F_{n-1}$ と $F_{n-2}$ を 変数に記録 し、繰り返しのたびにその値を更新 していく必要があります。
下記はそのように fib_by_f を修正したプログラムです。なお、下記のプログラムの変数は以下のような意味を持ちます。
-
fib_p1：1 つ前に計算した $F_{n-1}$ の計算結果 -
fib_p2：2 つ前に計算した $F_{n-2}$ の計算結果 -
fib：次に計算する $F_n$ を代入する変数
それぞれの行の意味は以下の通りです。
-
2 ~ 5 行目：
nが0と1の場合は決められた答えを返す - 9 行目：繰り返しの処理では、$F_2$ から $F_n$ の順番で計算する
-
7、8 行目：繰り返しの処理で最初に計算するのは $F_2$ なので、その 2 つ前の $F_0$ の値である 0 を
fib_p2に、1 つ前の $F_1$ の値である 1 をfib_p1に代入する -
10 行目：漸化式 $F_n = F_{n - 1} + F_{n - 2}$ に従って、$F_i$ を表す
fibの値を計算する -
11、12 行目：次の繰り返し処理では、$F_{i+1}$ が計算されるが、その時には
fib_p1に代入されている $F_{i-1}$ が $x_{i+1}$ の 2 つ前の計算結果に、fibに代入されている $F_{i}$ が $x_{i+1}$ の 1 つ前の計算結果になる。そのため、次の繰り返し処理が正しく行えるようにfib_p2とfib_p1の値を更新する
1 def fib_by_f(n):
2 if n == 0:
3 return 0
4 elif n == 1:
5 return 1
6
7 fib_p2 = 0
8 fib_p1 = 1
9 for i in range(2, n + 1):
10 fib = fib_p1 + fib_p2
11 fib_p2 = fib_p1
12 fib_p1 = fib
13 return fib
行番号のないプログラム
def fib_by_f(n):
if n == 0:
return 0
elif n == 1:
return 1
fib_p2 = 0
fib_p1 = 1
for i in range(2, n + 1):
fib = fib_p1 + fib_p2
fib_p2 = fib_p1
fib_p1 = fib
return fib
上記の実行後に、下記のプログラムで $F_0$ ~ $F_{9}$ までを計算すると、実行結果のように、正しい計算が行われることが確認できます。
for i in range(10):
print(f"fib({i}) = {fib_by_f(i)}")
実行結果
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
さらなる最適化が行えない理由
残念ながら $F_n$ を計算する fib_by_f では、合計を計算する場合のように、fib_p1 と fib_p2 を削除することはできません。
1 for i in range(2, n + 1):
2 fib = fib_p2 + fib_p1
3 fib_p2 = fib_p1
4 fib_p1 = fib
実際に先程の合計の計算の最適化で行ったように、上記のプログラムに対して、下記のような最適化を意図した処理を行うと、正しい計算を行うことができなくなります。その理由について少し考えてみて下さい。
- 3、4 行目が行われた後で、次の繰り返し処理で 2 行目の処理が行われるので、3、4 行目の式を 2 行目の式に適用する
- 3、4 行目の処理を削除する
下記はそのように修正したプログラムです。下記のプログラムでは、fib に対する代入処理のみ が行われているので、繰り返し処理の中では fib の値しか変化しません。そのため、fib_p1 の値が更新されないまま 繰り返し処理の計算が行われてしまうようになるため、正しい計算が行われなくなります。
for i in range(2, n + 1):
fib = fib_p1 + fib
上記では fib_p1 が更新されない点が問題なので、下記のプログラムのように、元のプログラム 3 行目の fib_p2 = fib_p1 の部分だけを 2 行目の式に反映し、3 行目だけを削除すればよいのではないかと考えた人がいるかもしれませんが、そのようなプログラムも正しく動作しません。下記のプログラムは、そのように修正したプログラムです。下記のプログラムでは、fib に fib_p1 を 2 回足し算するというおかしなプログラムになっています。
for i in range(2, n + 1):
fib = fib_p1 + fib_p1
fib_p1 = fib
このように、過去の複数の計算結果 を使って計算を行う漸化式を for 文で記述する場合、下記のような処理を記述する必要があります。
- （1 つ前から、最も古い過去の記録までの）必要な数だけ過去の計算結果を記録 する
- 繰り返しの処理を行うたびに、それらの記録を 一つずつずらして更新 する
処理が独立していない繰り返し処理を、for 文でボトムアップな方法で記述する場合は以下のようになる。下記の性質から、前者の場合は、for 文で記述するのに向いている 繰り返し処理だということができる。
- 1 つ前の処理の結果のみを利用 して繰り返し処理を行う場合は、1 つ前の処理の結果 を記録する変数を 1 つだけ用意 して、繰り返しの処理のたびに、その変数の値を更新すればよいので、繰り返し処理を 簡潔に記述しやすい
- 2 つ以上前の処理の結果を利用 して繰り返し処理を行う場合は、必要な数だけ過去の結果を記録し、繰り返しの処理を行うたびにそれらの記録を一つずつずらして更新する必要があるので、少し記述が面倒である
2 つ以上前の処理の結果を利用 して繰り返し処理を行う場合は、再帰呼び出し によって、より簡潔に記述 することができます。ただし、再帰呼び出しにはいくつかの欠点があるので、その点に注意する必要があります。その方法や注意点については次回の記事で説明します。
while 文による繰り返し処理
while 文は、while 条件式: のように記述することからわかるように、特定の条件が満たされる間 繰り返すような、繰り返し処理を行うのに向いています。
前回の記事で説明したように、for 文は while 文で書き直すことができるので、列挙することができるような繰り返し処理を while 文で記述することは可能ですが、そのような処理は for 文で記述したほうが簡潔に記述できるので良いでしょう。
それ以外の点は、基本的に for 文で説明した内容とほぼ同じです。例えば、漸化式で表現されるような計算を while 文を使って記述することができます。
具体例として、1 から n までの合計が 100 を超えるような最小の n を求める処理は、下記のプログラムで計算することができます。
- 2、5 行目：for 文と異なり、n を 0 から 1 ずつ繰り返しのたびに増やす処理は自分で記述する必要がある
- 3 行目：合計が 100 以下の場合に繰り返す
- 4 行目：合計を計算する処理は for 文の場合と同じ
-
7 行目：合計が 100 を超えた場合に、5 行目で
nに 1 が余分に足されているので、結果はn - 1を表示する必要がある点に注意すること
1 total = 0
2 n = 0
3 while total <= 100:
4 total += n
5 n += 1
6
7 print(n - 1)
行番号のないプログラム
total = 0
n = 0
while total < 100:
total += n
n += 1
print(n - 1)
実行結果
14
for 文や while 文に向いていない繰り返し処理
for 文や while 文で記述するのに あまり向いていない繰り返し処理 としては、繰り返しのたびに 次に行う繰り返しの処理の数が増えていく ようなものが挙げられます。
そのような繰り返し処理の例はすでに紹介済で、具体的には Mbtree クラスの create_tree_by_bf メソッドで ゲーム木を作成する処理 や、calc_node_height メソッドで ゲーム木のノードの表示の高さを計算する処理 が挙げられます。
例えば、ゲーム木を作成する処理は、以下のような繰り返し処理を行う必要があります。
- ルートノードを作成する
- ルートノードの子ノードをすべて作成する
- 作成したすべての子ノードに対してその子ノードをすべて作成する
- 上記の処理を作成する子ノードが存在しなくなるまで繰り返す
このような繰り返しの処理と、0 から 10 までの合計を計算する 繰り返し処理の違い を現実の世界で例えると、以下のようになります。
- 0 から 10 までの合計を計算する繰り返し処理は、本を最初のページから最後のページまで順番に読む作業に似ている。ページをめくった時に、現れるのは次のページという ただ 1 つのページ であり、最初のページから最後のページまで、直線的 に繰り返し処理を行うことができる
- ゲーム木を作成する処理は、ウェブサイトの全てのページを読む作業に似ている。ウェブサイトのトップページを読んだ後は、そのページのリンクすべて開き、それぞれのページを読む必要がある。そして、その開いた全てのページのリンクをすべて開き、それぞれのページを読むという作業を繰り返す必要がある。ページを読んだ後に現れるのは 複数のページ であり、繰り返しを行うたびに、次の繰り返しの対象 が 分岐して増えていく
このような 分岐する繰り返しの処理 を for や while 文で記述するアルゴリズムの一つが 幅優先アルゴリズム です。幅優先アルゴリズムでは、繰り返しを行うたびに、次の繰り返しの対象をすべて記録する という作業が必要になります。例えば、ゲーム木を作成する create_tree_by_bf では、下記のような繰り返し処理を行いました。
- ゲーム開始時の局面を表すノードを、ルートノードとするゲーム木を作成 する
- 子ノードを作成する処理を行う ノードの深さ d を 0 に設定 する
- 深さ d のノードが存在しない場合は、ゲーム木が完成しているので処理を終了する
- 深さ d のノードが存在する場合は、それらの全てのノードに対して子ノードを作成する
- 深さ d に 1 を足して 手順 3 に戻る
create_tree_by_bf では、上記の処理を行うために、nodelist_by_depth という属性に、次の深さのノードの一覧を記録する という処理を記述しています。
もう一つのアルゴリズムが下記の 深さ優先アルゴリズム ですが、こちらのアルゴリズムも手順 3-2 で 親ノードに戻る という処理が必要なため、親ノードを記録する必要 があります。
- ゲーム開始時の局面を表すノードを、ルートノードとするゲーム木を作成する
- 子ノードを作成する 処理を行う ノードを N と表記 し、N を ルートノードで初期化 する
-
N にまだ 作成していない子ノードが存在するか を判定する
- 作成していない子ノードが 存在する場合 は、その子ノードを作成 し、作成した子ノードを N として手順 3 に戻る
- 作成していない子ノードが 存在しない場合 は、親ノードが存在するか を判定する
- 親ノードが 存在する場合 は、親ノードを N として手順 3 に戻る
- 親ノードが 存在しない場合 は、ゲーム木が完成しているので 処理を終了する
for 文や while 文 による繰り返し処理は、繰り返しの処理で 必要となるデータをすべて自分で管理する 必要がありますが、再帰呼び出し による繰り返し処理では、1 回分の繰り返し処理で必要なデータだけを管理すればよい という点で、プログラムを 簡潔に記述できる という利点がありますが、その反面 いくつかの欠点があるので使用の際には注意が必要 です。それらについては次回の記事で説明することにします。
今回の記事のまとめ
今回の記事では、for 文と while 文による繰り返し処理の性質と使い分けについて説明しました。また、独立ではない繰り返し処理を表す漸化式について説明しました。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
次回の記事
-
反復可能オブジェクトの中には、無限にデータを取り出すことができるようなものもありますが、一般的にはそうではないので、ここでは列挙できるものとして考えることにします ↩
-
逆順にした場合は、
self.BOARD_SIZE - 1から-1より大きな値になるまで、-1ずつ減らすという処理を行う必要がある点に注意して下さい ↩ -
n には 1 以上の整数のみが入るような場合や、負の値が入る場合もありますが、そのような場合は必ずそのことが明記されます ↩
-
$x_n = n$ のような、それ以前の値が式に現れないような式は、漸化式ではありません ↩
-
Windows のタスクマネージャーは、Ctrl + Shift + Esc キーで開くことができます ↩