Pythonで〇×ゲームのAIを一から作成する　その101　for 文と while 文による繰り返し処理の性質と使い分け

# 目次と前回の記事

https://qiita.com/ysgeso/items/2381dd4e3283cbed49a0

https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee

## これまでに作成したモジュール

以下のリンクから、これまでに作成したモジュールを見ることができます。

| リンク | 説明 |
|:--|:--|
| [marubatsu.py](https://github.com/ysgeso/marubatsu/blob/master/100/marubatsu.py)  | Marubatsu、Marubatsu_GUI クラスの定義|
| [ai.py](https://github.com/ysgeso/marubatsu/blob/master/100/ai.py)  |  AI に関する関数 |
|  [util.py](https://github.com/ysgeso/marubatsu/blob/master/100/util.py) |  ユーティリティ関数の定義。現在は `gui_play` のみ定義されている |
| [tree.py](https://github.com/ysgeso/marubatsu/blob/master/100/tree.py)  | ゲーム木に関する Node、Mbtree クラスの定義  |
| [gui.py](https://github.com/ysgeso/marubatsu/blob/master/100/gui.py)  |  GUI に関する処理を行う基底クラスとなる GUI クラスの定義  |

## ルールベースの AI の一覧

ルールベースの AI の一覧については、下記の記事を参照して下さい。

https://qiita.com/ysgeso/items/10d1d01192c014173e4b

# 繰り返し処理の使い分け

前回の記事で、単純な繰り返し処理であれば、while 文や for 文を使ったほうが良いということを説明しまたが、具体的にどのような処理が単純な処理であるかについて言及していませんでした。そこで、今回の記事では繰り返し処理の使い分けについて説明します。

なお、__繰り返し処理__ を行う際に、__どの方法を使えば良いか__ については、特定の性質を持っていることが、特定のアルゴリズムを利用すべきであるという風に、__完璧に分類できるわけではありません__。今回の記事の説明は、あくまで __一つの目安__ だと思ってください。

# for 文による繰り返し処理の性質

for 文は、[前回の記事](https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee#for-%E6%96%87%E3%81%A8-while-%E6%96%87%E3%81%AE%E4%BD%BF%E3%81%84%E5%88%86%E3%81%91)で説明したように、__あらかじめ繰り返しを行う回数が決まっている__ ような処理を __簡潔に記述できる__ という性質があります。

for 文は、`for 変数 in 反復可能オブジェクト:` のように記述することからわかるように、__列挙することができるデータ__[^1] に対する繰り返し処理を行うのに向いています。

具体的には、以下のような処理を行う際は、for 文が向いている可能性が高いでしょう。いずれもあらかじめ数が決められているものに対して繰り返し処理を行います。

* `range(10)` のように、繰り返しのたびに、数値が規則正しく増減する処理
* list の要素のように、あらかじめ決められているデータに対する繰り返し処理

そのような繰り返し処理は良く行われるので、for 文は繰り返し処理の中で最も良く使われるのではないかと思います。

:::note
[以前の記事](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E9%96%A2%E6%95%B0-enumerate)で紹介した組み込み関数 `enumerate` や、まだ説明していない組み込み関数 [`zip`](https://docs.python.org/ja/3/library/functions.html#zip) を利用することで、同じ数の要素を持つ、複数の列挙可能なデータに対して、まとめて繰り返し処理を行うこともできます。

なお、`zip` については、今後の記事で紹介します。
:::

## 繰り返しの処理の独立性と処理の順番

あらかじめ数が決められているデータに対する繰り返し処理を行う際に、そのデータに対して、__どのような順番__ で繰り返しを行うかが __重要な場合__ と、__そうでない場合__ があります。

繰り返しの処理の順番が重要かどうかは、__処理の独立性__ によって決まります。

### 処理が独立な場合は順番は重要ではない

繰り返しの __処理が独立__ しているとは、__ある回で行われる繰り返し処理__ が、__別の回__ で行われる繰り返し処理に __全く影響を与えない__ ということを表します。

具体例として、〇×ゲームの __ゲーム盤__ のそれぞれのマスを __画像で描画__ する繰り返し処理は __独立しています__。例えば __(0, 0) のマスを描画__ する際に、__他のマスの描画処理__ は __全く影響しません__。そのような場合は、どのような順番でマスを描画しても結果は変わりません。

:::note warn
__for 文__ は、繰り返しの処理が処理が __独立している場合に向いています__。
:::

例えば、Marubatsu_GUI クラスの `draw_board` でゲーム盤のマスを描画するプログラムは下記のようになっています。

```python
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` を実行すると、ゲーム盤が正しく表示されることを確認してみて下さい。

```python
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)
```

<details><summary><strong>修正箇所</strong></summary>

```diff_python
# ゲーム盤のマークを描画する
-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)
```
</details>

また、下記のプログラムのように、for 文の入れ子の順番を変えても正しく動作します。

```python
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)
```

<details><summary><strong>修正箇所</strong></summary>

```diff_python
# ゲーム盤のマークを描画する
-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)
```
</details>


### 処理が独立でない場合

繰り返し処理が __独立でない__ 場合は、__一般的__ には __順番が重要__ になります。順番が重要になる理由について少し考えてみて下さい。

その理由を箇条書きにすると以下のようになります。

* 独立ではないということは、__A 回目__ で行われた繰り返し処理の結果が、__A より後の__ 回で行われた __B 回目__ の繰り返し処理の結果に __影響を与える__ ということを意味する
* B 回目で行われていた処理を A 回目より先に行ってしまうと、__B 回目__ の処理が __A 回目の処理の影響を受けなくなってしまう__
* その結果、__B 回目の処理の結果__ が、入れ替える前から __変化してしまう可能性が生じる__

例えば、〇× ゲームの __ゲーム盤を文字列で表示__ する場合は、繰り返しの処理は __独立していません__。画像で描画する場合は独立しているのに、文字列で表示する場合は独立していない理由について少し考えてみて下さい。

〇× ゲームのゲーム盤を文字列で表示する場合は、`Marubatsu` クラスのインスタンスを `print` で表示します。その際に呼び出される `Marubatsu` クラスの [__`__str__`__](https://qiita.com/ysgeso/items/ed1eb1cacf9a3e7dfa29#__str__-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89) メソッドは下記のように定義されています。なおターン数などの表示の部分は省略しました。

```python
 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 つの文字列を結合するという処理は、下記のプログラムのように、__結合の順番によって結果が変化__ します。

```python
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 までの整数の合計を計算する繰り返し処理です。

```python
1  total = 0
2  for i in range(10):
3      total += i
4
5  print(total)
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
total = 0
for i in range(10):
    total += i

print(total)
```
</details>

実行結果

```
45
```

上記のプログラムは、繰り返し処理の 3 行目で `total` という変数に `i` を加算しているので、先程の文字列でゲーム盤を表示する場合と同様に、繰り返しの処理は __独立していません__。しかし、この場合は下記のプログラムのように、順番を変えて、9 から 0 の順番で合計を計算しても __正しい計算が行われます__。その理由について少し考えてみて下さい。

```python
total = 0
for i in range(9, -1, -1):
    total += i

print(total)
```

<details><summary><strong>修正箇所</strong></summary>

```diff_python
total = 0
-for i in range(10):
+for i in range(9, -1, -1):
    total += i

print(total)
```
</details>


実行結果

```
45
```

順番を変えても正しい計算が行われる理由は、__足し算__ という計算が、__順番を変えても答えが変わらない__ という性質を持っているからです。例えば 0 に 1、2、3 という 3 つの整数を加算する場合に、下記のように順番を変えても同じ答えになります。

```python
print(0 + 1 + 2 + 3)
print(0 + 2 + 3 + 1)
```

実行結果

```
6
6
```

足し算のように、順番を入れ替えても計算結果が変わらないような性質の事を __交換法則__ と呼びます。足し算や掛け算は交換法則を持ちますが、引き算や割り算は下記のように、交換法則を持ちません。また、Python の __文字列の結合__ も __交換法則を持ちません__。

$1 - 0 ≠ 0 - 1$
$2 ÷ 1 ≠ 1 ÷ 2$

繰り返し処理の中で独立していない __すべての処理__ が、__交換法則を持つ場合__ は、順番を変更しても構わないという事です。ただし、独立していない処理が交換法則を持つかどうかが簡単にはわからないような場合が多いので、独立していない場合は、__基本的には順番通りに処理を行ったほうが良い__ でしょう。

:::note
0 から 9 までの合計の計算の場合は、3、1、6、7、2、8、0、4、9、5 のように、0 から 9 までの整数が 1 回ずつ出現さえすれば、どのような順番で合計を計算しても計算結果は変わりません。ただし、そのような計算を行うプログラムを記述するのは面倒なので、特に理由がない限りはそのような計算は行わないほうが良いでしょう。
:::

## for 文によるボトムアップな繰り返し処理の記述

__独立ではない繰り返し処理__ で計算を行う際に、実際に __計算を行うことができる順番__ で計算を行うアルゴリズムの事を、__ボトムアップ__（bottom up）な処理と呼びます。

:::note
一般用語としてのボトムアップは、会社などで複数の部署が協力して仕事を行う際に、実際の作業を行う現場の意見をもとに意思決定を行うというやり方のこと表します。下から上に意見を伝えるので下意上達も呼ばれます。

逆に、経営陣などの上層部が意思を決定して、部下に伝えるというやり方のことをトップダウンや、上意下達と呼びます。

なお、プログラミング用語としてのボトムアップやトップダウンの意味と、一般用語としての意味は若干異なる点に注意して下さい。
:::

__for 文__ や __while 文__ は、__ボトムアップな繰り返し処理を記述するのに向いており__、__トップダウン__ な繰り返し処理の記述は次回の記事で説明しますが、__再帰呼び出しが向いています__。

:::note
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$ などが良く使われます。

:::note
$x_n$、$n$ は 0 以上の整数

のように、__添え字__ によって __番号が付けられた__、__順番に並んだ数__ のことを __数列__ と呼びます。また、数列の __それぞれの数値__ の事を __項（こう）__ と呼びます。

数列には、端が存在するものと存在しないものがあります。例えば、自然数は 1 から始まるので片側に端がある数列ですが、整数は端がない数列です。

__漸化式で表現__ される $x_n$ は、並び方に __規則性がある__ 数列の一種ですが、__サイコロの出目を記録__ した数列のように、__式で表現できない規則性のない数列__ もあります。
:::

:::note
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$

:::note
漸化式の $n$ を時間と考えると、漸化式は過去のデータを元に現在のデータを計算する式だと考えることもできます。そのため、世の中の現象を、漸化式を使ってうまく表現できる場合がよくあります。

例えば、時速 10 km/h で走る車の $t$ 時間後の走行距離を $x_t$ とすると、$x_t$ は、1 時間ごとに 10 増えるので下記の漸化式で表現することができます。

$x_t = x_{t - 1} + 10$、$x_0 = 0$
:::

:::note
漸化式を、__過去のデータを利用しない形の式__ で表現しなおしたものを __一般項__ と呼びます。例えば上記の、$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$ を求める必要があります。
:::

:::note
漸化式よりも一般項のほうがわかりやすいと思うかもしれませんが、そうとは言い切れません。例えば、下記は 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 ずつ増やしながら下記の手順で計算を行います。

1. $x_0 = 0$
2. $x_1 = x_0 + 1 = 0 + 1 = 1$
3. $x_2 = x_1 + 2 = 1 + 2 = 3$
4. $x_3 = x_2 + 3 = 3 + 3 = 6$
5. $x_4 = x_3 + 4 = 6 + 4 = 10$
6. $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]` を表示する

```python
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])
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
x = []
x.append(0)
for n in range(1, 6):
    x.append(x[n - 1] + n)
    
print(x)
print(x[5])
```
</details>

実行結果

```
[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$ を表す式をそのまま記述するようにする

```python
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])
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
x = {}
x[0] = 0
for n in range(1, 6):
    x[n] = x[n - 1] + n
    
print(x)
print(x[5])
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
-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])
```
</details>

実行結果

```
{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 憶までの合計を計算するプログラムです。なお、計算結果の表示は重要ではないので省略しました。

```python
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 ものメモリが消費されていることが確認できました

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/243cf9cf-18d2-0f51-9fce-da2359da76b6.png" width="500">

このように、メモリを多く消費しすぎると __パソコン全体の処理速度が著しく遅くなる__ 場合が生じます。そのため、__大量のデータを計算__ する場合は、プログラムが __無駄なメモリを消費しないように気を付ける__ 必要があります。

なお、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` を代入して更新する

```python
prevx = 0
for n in range(1, 6):
    x = prevx + n
    prevx = x
    
print(x)
```

実行結果

```
15
```

上記のプログラムを実行すると、実行結果のように、0 から 5 までの整数の合計が正しく表示されます。

### さらなる最適化

先程のプログラムは、下記のプログラムのように __`prevx` を削除__ することができます。また、下記の __`x` を `total` に置き換える__ と、__これまでに記述してきた__ 0 から 特定の整数までの合計を計算する __プログラムと同様__ になります。

```python
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` は不要である

```python
for n in range(1, 6):
    x = prevx + n
    prevx = x
```

タスクマネージャーの画像は省略しますが、下記のプログラムを実行して 1 憶までの整数の合計を計算しても、Python の __メモリの消費はほとんど増えません__。

また、先程のプログラムは 1 億個のデータを list に記録する必要があったので、筆者のパソコンでは処理時間が約 30 秒ほどかかりましたが、下記のプログラムではそのような処理を行う必要がないので、処理時間は約 11 秒でした。このように __メモリの消費の最適化__ を行うことで、__処理時間を短くする__ ことができました。

```python
x = 0
for n in range(1, 100000001):
    x += n
    
print(x)
```

実行結果

```
5000000050000000
```


:::note
`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 のリンクを下記に示します。

https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0

### 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]` を計算する式が異なる 

```python
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}$ までを計算すると、実行結果のように、正しい計算が行われることが確認できます。

```python
for i in range(10):
    print(f"fib({i}) = {fib_by_f(i)}")
```

実行結果

```python
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` の値を更新する
```python
 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
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
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
```
</details>

上記の実行後に、下記のプログラムで $F_0$ ~ $F_{9}$ までを計算すると、実行結果のように、正しい計算が行われることが確認できます。

```python
for i in range(10):
    print(f"fib({i}) = {fib_by_f(i)}")
```

実行結果

```python
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` を削除することはできません__。

```python
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` の値が更新されないまま__ 繰り返し処理の計算が行われてしまうようになるため、正しい計算が行われなくなります。

```python
    for i in range(2, n + 1):
        fib = fib_p1 + fib
```

上記では `fib_p1` が更新されない点が問題なので、下記のプログラムのように、元のプログラム 3 行目の `fib_p2 = fib_p1` の部分だけを 2 行目の式に反映し、3 行目だけを削除すればよいのではないかと考えた人がいるかもしれませんが、そのようなプログラムも正しく動作しません。下記のプログラムは、そのように修正したプログラムです。下記のプログラムでは、`fib` に `fib_p1` を 2 回足し算するというおかしなプログラムになっています。

```python
    for i in range(2, n + 1):
        fib = fib_p1 + fib_p1
        fib_p1 = fib
```

このように、__過去の複数の計算結果__ を使って計算を行う漸化式を for 文で記述する場合、下記のような処理を記述する必要があります。

* （1 つ前から、最も古い過去の記録までの）__必要な数だけ過去の計算結果を記録__ する
* 繰り返しの処理を行うたびに、それらの記録を __一つずつずらして更新__ する

:::note warn
処理が独立していない繰り返し処理を、for 文でボトムアップな方法で記述する場合は以下のようになる。下記の性質から、__前者の場合は、for 文で記述するのに向いている__ 繰り返し処理だということができる。

* __1 つ前の処理の結果のみを利用__ して繰り返し処理を行う場合は、__1 つ前の処理の結果__ を記録する変数を __1 つだけ用意__ して、繰り返しの処理のたびに、その変数の値を更新すればよいので、繰り返し処理を __簡潔に記述しやすい__
* __2 つ以上前の処理の結果を利用__ して繰り返し処理を行う場合は、必要な数だけ過去の結果を記録し、繰り返しの処理を行うたびにそれらの記録を一つずつずらして更新する必要があるので、__少し記述が面倒である__
:::

__2 つ以上前の処理の結果を利用__ して繰り返し処理を行う場合は、__再帰呼び出し__ によって、__より簡潔に記述__ することができます。ただし、再帰呼び出しにはいくつかの欠点があるので、その点に注意する必要があります。その方法や注意点については次回の記事で説明します。

# while 文による繰り返し処理

while 文は、`while 条件式:` のように記述することからわかるように、__特定の条件が満たされる間__ 繰り返すような、繰り返し処理を行うのに向いています。

[前回の記事](https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee#%E4%BB%A5%E5%BE%8C%E3%81%AE%E8%AA%AC%E6%98%8E%E3%81%AE%E8%A1%A8%E8%A8%98%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)で説明したように、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` を表示する必要がある点に注意すること 

```python
1  total = 0
2  n = 0
3  while total <= 100:
4      total += n
5      n += 1
6
7  print(n - 1)
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
total = 0
n = 0
while total < 100:
    total += n
    n += 1

print(n - 1)
```
</details>

実行結果

```
14
```

# for 文や while 文に向いていない繰り返し処理

for 文や while 文で記述するのに __あまり向いていない繰り返し処理__ としては、繰り返しのたびに __次に行う繰り返しの処理の数が増えていく__ ようなものが挙げられます。

そのような繰り返し処理の例はすでに紹介済で、具体的には Mbtree クラスの `create_tree_by_bf` メソッドで __ゲーム木を作成する処理__ や、`calc_node_height` メソッドで __ゲーム木のノードの表示の高さを計算する処理__ が挙げられます。

例えば、ゲーム木を作成する処理は、以下のような繰り返し処理を行う必要があります。

* ルートノードを作成する
* ルートノードの子ノードをすべて作成する
* 作成したすべての子ノードに対してその子ノードをすべて作成する
* 上記の処理を作成する子ノードが存在しなくなるまで繰り返す

このような繰り返しの処理と、0 から 10 までの合計を計算する __繰り返し処理の違い__ を現実の世界で例えると、以下のようになります。

* 0 から 10 までの合計を計算する繰り返し処理は、本を最初のページから最後のページまで順番に読む作業に似ている。ページをめくった時に、現れるのは次のページという __ただ 1 つのページ__ であり、最初のページから最後のページまで、__直線的__ に繰り返し処理を行うことができる
* ゲーム木を作成する処理は、ウェブサイトの全てのページを読む作業に似ている。ウェブサイトのトップページを読んだ後は、そのページのリンクすべて開き、それぞれのページを読む必要がある。そして、その開いた全てのページのリンクをすべて開き、それぞれのページを読むという作業を繰り返す必要がある。ページを読んだ後に現れるのは __複数のページ__ であり、繰り返しを行うたびに、__次の繰り返しの対象__ が __分岐して増えていく__

このような __分岐する繰り返しの処理__ を for や while 文で記述するアルゴリズムの一つが __幅優先アルゴリズム__ です。幅優先アルゴリズムでは、繰り返しを行うたびに、__次の繰り返しの対象をすべて記録する__ という作業が必要になります。例えば、ゲーム木を作成する `create_tree_by_bf` では、下記のような繰り返し処理を行いました。

1. ゲーム開始時の局面を表すノードを、ルートノードとするゲーム木を作成 する
2. 子ノードを作成する処理を行う ノードの深さ d を 0 に設定 する
3. 深さ d のノードが存在しない場合は、ゲーム木が完成しているので処理を終了する
4. 深さ d のノードが存在する場合は、それらの全てのノードに対して子ノードを作成する
5. 深さ d に 1 を足して 手順 3 に戻る

`create_tree_by_bf` では、上記の処理を行うために、__`nodelist_by_depth`__ という属性に、__次の深さのノードの一覧を記録する__ という処理を記述しています。

もう一つのアルゴリズムが下記の __[深さ優先アルゴリズム](https://qiita.com/ysgeso/items/db7cfe4a1f14d9cb9368#%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%82%88%E3%82%8B%E3%82%B2%E3%83%BC%E3%83%A0%E6%9C%A8%E3%81%AE%E4%BD%9C%E6%88%90)__ ですが、こちらのアルゴリズムも手順 3-2 で __親ノードに戻る__ という処理が必要なため、__親ノードを記録する必要__ があります。

1. ゲーム開始時の局面を表すノードを、ルートノードとするゲーム木を作成する
2. __子ノードを作成する__ 処理を行う __ノードを N と表記__ し、__N を ルートノードで初期化__ する
3. __N__ にまだ __作成していない子ノードが存在するか__ を判定する
    1. 作成していない子ノードが __存在する場合__ は、__その子ノードを作成__ し、__作成した子ノードを N として手順 3 に戻る__
    2. 作成していない子ノードが __存在しない場合__ は、__親ノードが存在するか__ を判定する
        1. 親ノードが __存在する場合__ は、__親ノードを N として手順 3 に戻る__
        2. 親ノードが __存在しない場合__ は、ゲーム木が完成しているので __処理を終了する__

__for 文や while 文__ による繰り返し処理は、繰り返しの処理で __必要となるデータをすべて自分で管理する__ 必要がありますが、__再帰呼び出し__ による繰り返し処理では、__1 回分の繰り返し処理で必要なデータだけを管理すればよい__ という点で、プログラムを __簡潔に記述できる__ という利点がありますが、その反面 __いくつかの欠点があるので使用の際には注意が必要__ です。それらについては次回の記事で説明することにします。

# 今回の記事のまとめ

今回の記事では、for 文と while 文による繰り返し処理の性質と使い分けについて説明しました。また、独立ではない繰り返し処理を表す漸化式について説明しました。

# 本記事で入力したプログラム

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/101/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |

# 次回の記事

https://qiita.com/ysgeso/items/8432194829a4c6cc95f0

[^1]:反復可能オブジェクトの中には、無限にデータを取り出すことができるようなものもありますが、一般的にはそうではないので、ここでは列挙できるものとして考えることにします
[^2]:逆順にした場合は、`self.BOARD_SIZE - 1` から `-1` より大きな値になるまで、`-1` ずつ減らすという処理を行う必要がある点に注意して下さい 
[^3]:n には 1 以上の整数のみが入るような場合や、負の値が入る場合もありますが、そのような場合は必ずそのことが明記されます
[^4]:$x_n = n$ のような、それ以前の値が式に現れないような式は、漸化式ではありません
[^5]:Windows のタスクマネージャーは、Ctrl + Shift + Esc キーで開くことができます