Pythonで〇×ゲームのAIを一から作成する　その9　list の仕組み

# 目次と前回の記事

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

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

# 前回のおさらい

前回の記事では Python の代入文で行われる処理について説明し、最後に プログラム A と プログラム B の 3 行目は、見た目は似ているが __異なる処理__ を行っているということを説明しました。

__プログラム A__
```python
a = 5
b = a
a = 2
print(a)
print(b)
```
実行結果
```
2
5
```

プログラム B
```python
a = [1, 2, 3]
b = a
a[0] = 2
print(a)
print(b)
```
実行結果
```
[2, 2, 3]
[2, 3, 3]
```


今回の記事ではプログラム B の 3 行目で行われる処理について説明し、プログラム B で一見すると奇妙な処理を行われる理由について説明します。

# Python の list の仕組み
前回までの図では、list を管理するオブジェクトを下図のように表記していました。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ef2964f0-4f59-8a7f-52cc-63e02bf7d3d8.png" width="140">

図の list には 3 つの要素があり、それぞれの要素に `1`、`2`、`3` という 3 つの数値型のデータが代入されています。図ではそれらの数値型のデータが、オブジェクトが管理するデータの中に __直接__ 記録されているように表記されています。

しかし、実際には list を管理するオブジェクトは、list の要素に代入されたデータを上図のように __直接管理してはいません__。その理由の一つは、list の要素が __任意のデータ型__ を __代入__ できるというものです。実際に、初期化されたゲーム盤のデータは、`[[" ", " ", " "], [" ", " ", " "], [" ", " ", " "]]` のように、list の要素に、__他の list を__ 入れ子で代入しています。このような複雑なデータを 1 つのオブジェクトで管理することは不可能ではありませんが、__扱いづらく__、__非効率__ です。

そこで、list の要素は __変数と全く同じ仕組み__ でデータを扱います。そのため、list の要素は、__変数と同様__ に「代入文で値を代入できる」、「式の中で記述することで代入された値を利用できる」という性質を持っています。

:::note
以前の記事で、『本記事では「__複合データ型__」という用語を、「Python の 任意のデータ型 を、__複数組み合わせて__ データを表現するデータ型」という意味で定義する』という説明をしました。Python では、list などの __複合データ型__ は、データの内部に、list の要素のような、__変数と同じ性質を持つもの__ を使って複数のデータを管理します。
:::

具体的には、Python の list の各要素には、変数と同様に「代入されたデータを管理するオブジェクトの id」が格納されます。下図は、このことを `[1, 2, 3]` という list を例にして図示したものです。

Python では、__すべてのデータ__ は、__オブジェクトで管理される__ ので、list のような __複合データ型__ のデータは、__複数のオブジェクトが管理するデータから構成__ されます。また、複合データ型を構成するオブジェクトは、list のインデックスのような __識別子を用いて参照__ します。

上記で説明したように、list の要素は __変数と同じ性質を持つ__ ので、下図では list の各 __要素を__ 変数と同じ __直方体で表記__ し、list の要素の __インデックス__ を __直方体の上__ に表記します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c15b4778-b9fa-892f-0a68-751715466f97.png" width="300">

Python では、上図のような `[1, 2, 3]` という複合データ型の list を管理するオブジェクトは、以下のような手順で作成されます。

1. list の要素として記述されている `1`、`2`、`3` を管理する 3 つのオブジェクトを新しく作成する
2. list を管理するオブジェクトを新しく作成し、そのオブジェクトが管理するデータの中に、変数と同じ性質を持つ list の 3 つの要素を作成し、それぞれの要素のインデックスを 0、1、2 とする
3. 3 つの要素に、それぞれの要素に代入するデータを管理する「オブジェクトの id」を格納する

list を管理するオブジェクトは、list の要素に代入されたデータを __直接格納していない__ ため、list から特定の __インデックスの要素の値__ を取り出して利用する際には、以下のような処理が行われます。

1. list を管理するオブジェクトのデータの中から、__インデックスが参照__ する要素を探す
2. 探し出した要素が格納する オブジェクトの id を取り出す
3. 取り出した __オブジェクトの id が 参照__ するオブジェクトを探す
4. 探し出したオブジェクトが管理するデータを取り出す

list の要素に代入されたデータを取り出して利用するためには、以下の表のように異なる __2 つの識別子__ を使った参照が行われます。ただし、オブジェクトの id に関する処理は __Python が自動的に行う__ ので、プログラムに記述する必要があるのは、__インデックス__ だけです。

| 識別子 | 参照先 |
|:--|:--|
| list の要素のインデックス  | list の要素  |
| list の要素が格納するオブジェクトの id  | 要素の値を管理するオブジェクト  |

:::note warn
list の性質をまとめると、以下のようになります。

* list を管理するオブジェクトのデータには、__list の要素__ が格納される
* list の要素は、__変数と同じ性質を持つ__ ため、要素に代入された __データ__ を __直接格納しない__
* 従って list を管理するオブジェクトは、list の __要素に代入されたデータ__ を __直接管理しない__
* list の要素は、「__インデックス__」 という __識別子__ を使って __参照__ される
* list の要素に代入された値を管理するオブジェクトは、「__インデックス__」と「__要素が格納する id__」という __2 つの識別子__ を使って __参照__ される

また、複合データ型の性質をまとめると、以下のようになります。

* list のような __複合データ型__ のデータは、__複数のオブジェクトが管理するデータから構成__ される
* 複合データ型を構成するオブジェクトは、list のインデックスのような __識別子を用いて参照__ する
:::

## 単一データ型の定義

数値型や文字列型のデータは、1 つのオブジェクトが管理します。そのようなデータを表す Python の用語を調べてみたのですが、見つかりませんでした。そこで、本記事では、数値型や文字列型のデータのように、__1 つのオブジェクトが管理__ するデータ型のことを、複合データ型に対比して、__単一データ型__ と表記することにします。

なお、この単一データ型という用語は、__筆者が考えた用語__ なので、__一般的なプログラミング用語ではありません__。他の記事や文献では、__この用語は使われない__ 点に注意して下さい。

:::note
文字列型のデータは、複数の文字を扱うので、プログラム言語によっては複合データ型に分類される場合があります。本記事では以下のような理由から、Python の __文字列型__ のデータを __単一データ型に分類__ します。

* 本記事の定義では __複合データ型__ のデータは、__複数のオブジェクトが管理するデータ__ から構成される
* __Python の文字列型__ のデータは、__1 つのオブジェクトで管理__ される
:::

## list の代入処理

下図は、プログラム B の 1 行目の `a = [1, 2, 3]` を実行した場合の図です。その下の、これまでの `[1, 2, 3]` を表す不正確な図と見比べてみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/777a66f1-561a-65f5-8d46-fbe0cd8af252.png" width=300">

これまでの、`[1, 2, 3]` を表す __不正確な__ 図

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ef2964f0-4f59-8a7f-52cc-63e02bf7d3d8.png" width="140">

図からわかるように、`a` が格納するのは `[1, 2, 3]` という list を管理する、150 というオブジェクトの id __だけ__ であり、list の要素である `1`、`2`、`3` を管理するオブジェクトの id は、`a` を表す直方体には __一切格納されません__。

このことは、プログラムで単に `a` と記述しただけでは、`a` に代入された __list の要素__ に対する処理を __記述したことにはならない__ ということを意味します。

# list の要素への代入処理

プログラム B の 3 行目の `a[0] = 2` では、`a` に代入された list の __0 番の要素__ に `2` を代入しています。この処理は、以下のような手順で行われます。

1. `2` というリテラルが記述されているので、新しく `2` を管理するオブジェクトを作成する
2. `a` が参照するオブジェクトを探す
3. そのオブジェクトが管理する list の要素の中から、`[]` の中に記述された `0` 番のインデックスの要素を探す。__`a[0]`__ は __この要素__ の事を表す
4. 変数と、list の要素は __同じ性質を持つ__ ので、`a[0]` の要素に、手順 1 で作成したオブジェクトの id を格納する

下図は、上記の代入処理を図で表したものです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7abb4d00-e84a-c346-ef3a-742c75da5fa3.png" width="700">

図の右側の `150` というオブジェクトの id が入っている直方体が `a` を、図の右側の `369` というオブジェクトの id が入っている直方体が `a[0]` を表します。

上記の処理では、以下の 2 つが重要なポイントになります。

* この処理で `a` が格納するオブジェクトの id は __変化しない__
* 変化するのは  __`a[0]`__ という __要素__ が格納するオブジェクトの id だけである

これは、`a[0] = 2` が、`a` ではなく `a[0]` に対して代入を行っているからです。Python の代入文で行われる処理を正しく理解している人にとってはあたりまえのようなことかもしれませんが、正しく理解していない人や、いい加減に理解している人は `a = 2` と `a[0] = 2` を __混同しがち__ です。

:::note warn
`a` と `a[0]` は、どちらも __変数と同じ性質__ を持ちますが、上記の図からもわかるように、 __異なるものを表している__ ということを、__必ず理解__ して下さい。
:::

:::note
list は複数のデータを入れることができる __容器__ に、list の要素は容器の中に入れた __個別のデータ__ に例えることができます。そう考えると `a` と `a[0]` が __全く異なるものを表している__ ということが理解できるのではないでしょうか？
:::
 
そして、この違いを理解していないと、Python で良く使われる list などを利用したプログラムを記述する際に、プログラム B や、`board = [[" "] * 3] * 3` のような、__意図しない処理__ [^1]を行うプログラムを記述してしまう原因になってしまいます。さらに、間違った __理由がわからない__ せいで、正しいプログラムに __修正することができない__ という大変困った事態にもなるでしょう。

本記事で 3 回の記事に渡ってかなり詳しくこのことに関して説明しているのは、このことを正しく理解しないと正しいプログラムを作ることができない可能性が高いからです。初心者には難しいかもしれませんが、避けて通るわけにはいかないことなので、頑張って理解して下さい。

:::note
上図で、`a[0] = 2` の代入が行われた後で、`1` を管理する、id が `561` のオブジェクトが、どの変数や list の要素からも __参照されなくなった__（赤い矢印で結ばれていない）ことが気になった人はいないでしょうか？このオブジェクトのように、どこからも参照されなくなったオブジェクトは、Python のプログラムから __二度と利用することはできなくなります__。

Python がオブジェクトを記憶するためには、コンピューターの __メモリ__ が使われます。そのため、利用できないオブジェクトのデータを記憶すると、コンピューターのメモリの無駄遣いになってしまいます。そこで、このようなオブジェクトを Python が定期的に探しだして、__自動的にメモリから削除する__、ガーベジコレクティング[^2]という仕組みがあります。

なお、ガーベジコレクティングは __Python が自動的に行う__ ものなので、プログラムでその処理を __記述する必要はありません__。
:::

## プログラム B の 3 行目で `a` と `b` が同時に変化する理由

先程の図では、list の要素に値を代入する処理だけに集中して説明したかったので、プログラム B の 2 行目の `b = a` によって値が代入された `b` の存在を表記していませんでした。

下図は、先ほどのプログラム B の 3 行目の `a[0] = 2` 処理を表す図に、`b` を加えたものです。図の左側では、プログラム B の 2 行目の `b = a` を実行した結果、`a` と `b` が list を管理する __同一の__ オブジェクトを参照することで、同じデータを __共有__ しています。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7dfc34ac-1930-fc25-52ff-2fe8ea5618b5.png" width="700">

`a` と `b` は __同一の__ オブジェクトを参照しているので、`a[0]` と `b[0]` はどちらも図では id が `150` のオブジェクトが管理する「インデックスが `0` の要素」という __同一の要素__ を表します。`a[0] = 2` という処理を行うと、`b[0] = 2` という処理が同時に 2 つ行われるように __見える__ かもしれませんが、`a[0]` と `b[0]` は同一の要素を表すので、実際には __1 つの処理__ しか行われません。

また、図からわかるように `a` と `a[0]` は __異なる__ オブジェクトを __参照__ しています。従って、`a[0] = 2` を実行しても、`a`  が参照するオブジェクトが __変化することはありません__。従って、プログラム B の 3 行目を実行した後も、`a` と `b` は __同一の list を共有__ したままです。そのため、下記のプログラム B のように、`a` と `b` を表示すると、同じ list のデータが表示されます。

上記が、プログラム B が一見すると 3 行目の `a[0] = 2` によって、__`a` と `b` が同時に変更__ されてしまうという、奇妙な処理が行われてしまうように __見える原因__ です。プログラム B が行っている __処理の内容を正しく理解__ できれば、プログラム B の `a` と `b` は __同一のデータを共有__ しているため、同じデータが表示されることは奇妙でもなんでもなく、__あたりまえの処理__ が行われた結果であることがわかるのではないでしょうか。

プログラム B
```python
a = [1, 2, 3]
b = a
a[0] = 2
print(a)
print(b)
```
実行結果
```
[2, 2, 3]
[2, 2, 3]
```

:::note warn
プログラム B の 2 行目のように、list が代入された変数を他の変数に代入するという処理は、list を複製して代入する処理であると __勘違いされがちですが__、実際には __同じ list__ を複数の変数で __共有__ するという処理です。

Python では、list に限らず、__変数を他の変数に代入__ する処理では、データが __複製されることは無い__ ことを忘れないで下さい。
:::

# プログラム C との比較

前回の記事で紹介した、プログラム B の処理を、プログラム A の処理と同様の処理が行われるように修正した下記のプログラム C と、プログラム B を比較してみることにします。

プログラム C
```python
a = [1, 2, 3]
b = a
a = [4, 5, 6]
print(a)
print(b)
```
<details><summary><strong>プログラム B からの修正箇所</strong></summary>

```diff_python
a = [1, 2, 3]
b = a
- a[0] = 2
+ a = [4, 5, 6]
print(a)
print(b)
```
</details>

実行結果
```
[4, 5, 6]
[1, 2, 3]
```
下図は、プログラム C の 3 行目で行われる処理を図示したものです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e91e69d0-2c50-f7e4-e5bc-3d2ffa7c0602.png" width="700">

3 行目で `a = [4, 5, 6]` が実行されると、`[4, 5, 6]` を管理する __新しいオブジェクト__ が作成され、`a` がこの新しいオブジェクトを __参照する__ ようになります。結果として、`a` と `b` が __異なる__ list を管理するオブジェクトを参照するようになり、データの __共有が解除__ されるため、`a` と `b` を表示すると異なる内容が表示されます。

下図は、プログラム B の 2 行目で行われる処理を再掲したものです。上下の図を比べて行われている処理の違いを確認して下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7dfc34ac-1930-fc25-52ff-2fe8ea5618b5.png" width="700">

なお、図示はしませんが、下記のように、プログラム C の 4 行目に `a[0] = 2` という処理を付け加えて実行すると、実行結果から `a[0]` の要素の値のみが `2` に変更され、`b[0]` の要素の値は変化しません。これは、プログラム B と異なり、`a` と `b` には __異なる list__ が代入されているためです。

```python
a = [1, 2, 3]
b = a
a = [4, 5, 6]
a[0] = 2
print(a)
print(b)
```
<details><summary><strong>修正箇所</strong></summary>

```diff_python
a = [1, 2, 3]
b = a
a = [4, 5, 6]
+ a[0] = 2
print(a)
print(b)

```
</details>

実行結果
```
[2, 5, 6]
[1, 2, 3]
```

かなり長くなりましたが、以上が欠陥のあるゲーム盤の初期化を行うプログラムである、`board = [[" " * 3] * 3]` で行われる処理を理解するために必要な前提知識の説明です。

## プログラム A と B の処理のまとめ

:::note warn
プログラム A と B で行われる処理をまとめると以下のようになります。

* プログラム A、B の 2 行目で行われる `b = a` の処理は、いずれも、`a` に代入されたデータを `b` と __共有する処理__ である
* プログラム A の 3 行目では、`a` に 値を代入することで、`a` と `b` の __データの共有を解除__ したため、`a` と `b` が異なる値を持つようになる
* プログラム B の 3 行目では、`a` ではなく、`a` に代入された list の要素を表す `a[0]` に値を代入しているので、`a` と `b` のデータの __共有は解除されない__。そのため、`a` と `b` は同じデータを持つ
:::

:::note
プログラム A の 2 行目の `b = a` が、データの複製を行っているように見える原因の一つは、プログラム A の 1 行目で `a` に代入された __数値型のデータ__ が、__list__ のように、その __内部のデータの一部だけを変更__ するようなことが __できない__ からです。そのため、数値型のデータが代入された変数に対して、プログラム B のような処理を行う事は不可能です。プログラム B のような処理を行うためには、変数に、後から __データの一部を変更__ することができる、__list__ のようなデータを代入する必要があります。

具体的に、__どのようなデータ__ が代入された変数を別の変数に代入すると、データが複製されるように見えるかについての説明は後の記事で説明します。
:::

## 変数に list を代入する際の注意点と工夫

プログラム B からわかるように、__list__ が代入された変数を __直接他の変数に代入する__ という処理を行った場合、__同一の list の要素の値__ を __複数の変数__ から変更することができるようになります。このことを __意識せず__ にプログラムを記述すると、__バグの原因__ になってしまうため、__変数に list を代入__ した場合は、そのことを __意識しながら注意深く__ プログラムを記述する必要があります。

しかし、プログラムに記述された __変数の名前__ を見ただけでは、その中に __具体的にどのようなデータが代入されているかはわかりません__。そのため、プログラムに記述された __異なる変数__ に、__同じ list のデータが代入__ されているかどうかを __判断することが容易ではない__ 場合が良くあります。

例えば、プログラム B の場合、`a = [1, 2, 3]` と `b = a` という __記述の直後__ であれば、`a` と`b` に同一の list が代入されていることを比較的簡単に理解することができるでしょう。一方、そこから 100 行先のように __離れた場所__ に `a` と `b` に関するプログラムを記述する際に、`a` と `b` に同一の list が代入されていることをプログラミングの初心者が判断するのは簡単ではないでしょう。また、__他人が書いたプログラム__ を理解しようとした場合は、さらにそのことを判断することが困難になります。

:::note
現実の例で例えると、同じ部屋に A さんと B さんが __同居__ している場合のことを考えて下さい。これは、プログラミングの用語で言いかえると、A さんと B さんが同じ部屋を __参照__ しているということに相当します。その状況で、A さんが自分の住んでいる部屋の模様替えをすると、B さんは何もしていないのに自分の住んでいる部屋が模様替えされたように見えるでしょう。

もちろん、A さんと B さん本人や、A さんと B さんに __親しい人__ にとっては、模様替えが 1 回しか行われていないことは簡単にわかると思いますが、A さんと B さんのことを知ってはいるが __疎遠になっている人__ や、A さんと B さんのことを __知らない他人__ が、A さんと B さんから別々に部屋の模様替えをしたという話を聞いた場合は、模様替えが __別の部屋で 2 回__ 行われたと __勘違い__ する可能性が高いでしょう。

なお、この例えでは、「親しい人」が「記述の直後」、「疎遠な人」が「100 行先のように離れた場所」、「知らない他人」が「他人が書いたプログラム」に対応します。
:::

この問題に対する工夫として、変数に list が代入されているかどうかを __区別できるよう__ にプログラミングを行うという方法があります。具体的には、list が一般的に __複数__ のデータを扱うするために使われることを考慮し、list を代入する変数の名前に __英語で複数形の名詞__ を使います。例えば 3 人のテストの点数（score）を表す list を代入する変数には `scores` という複数形の名詞を使います。逆に、__1 つ__ のデータを表す数値型のデータを代入する場合は、`score` のように __単数形__ の名詞を使います[^3]。

もちろん、この方法だけでは異なる変数に同一の list が代入されているかどうかを見分けることはできませんが、この工夫によって変数に代入されているデータが list であるかどうかを __常に意識しながら__ プログラミングを行うことができるようになり、その結果エラーの原因となりやすい list を扱うプログラムの間違い減らすことが期待できます。そこで、本記事でも以後は必要に応じてこの工夫を行うことにします。

他にも、`score_list` のように、変数名の一部に list を含めたり、分かりづらい所にコメントを記述して説明するなど、様々な工夫が考えられるでしょう。

:::note
中に __複数__ のものを入れる「表」や「盤」の英単語である table や board のように、__単語そのものが複数のものを扱う__ という __意味を持つ__ 場合は、__1 つの表__ を表す list を代入する変数に `tables` のような複数形は使わないほうが良いでしょう。その理由は、`tables` という単語は、__複数の表__ という意味を持つので、複数の表のデータを扱う list を代入する変数の名前にしたほうが良いからです。
:::

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

以下のリンクから、本記事で入力して実行した JupyterLab のファイルを見ることができます。

https://github.com/ysgeso/marubatsu/blob/master/009/marubatsu.ipynb

# 次回の記事

https://qiita.com/ysgeso/items/59e51d983a32ac4bc5db

[^1]:実際には、プログラム B のような処理が必要になる場合があるので、意図してプログラム B のような処理を記述する場合もあります
[^2]:garbage collecting。英語で「ごみ収集」という意味
[^3]:プログラミングで、変数の名前に日本語を使うのが好まれない理由の一つに、日本語の名詞には複数形がないのでこのような工夫を行うことができないというものが挙げられます