Kurumi writes

---

先日LeetCodeを解いているとき、２次元配列のつくり方が違うという理由で30分ほど無駄なデバッグをしてしまいました。（解いていた問題はこちら：https://leetcode.com/problems/palindrome-partitioning）

同じ間違いをしないよう、Pythonの（2次元）配列の生成について調べた結果を書いていきます。

---

Pythonで２次元配列をつくる２つの方法

1. ２重のfor loop [推奨]

私が知る限り、こちらが最も一般的な方法です。

コード：

li = [[0 for i in range(5)] for j in range(5)]
print(li)

出力：

[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

高さ５、横幅５の２次元配列が生成されていると確認できます。

2. ２重の掛け算 [ここで私は引っかかった！]

コード：

li = [[0] * 5] * 5
print(li)

出力：

[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

同様に高さ５、横幅５の2次元配列が生成されました。しかし、この方法で生成された２次元配列が大きな問題を生むことになります。

問題！li[i][X] を変更すると・・・

「2. ２重の掛け算」で生成した２次元配列では、１つの要素の値を変更した際に他の要素の値も同時に変化してしまうことに気がつきました。実演します：

コード：

li = [[0] * 5] * 5
li[0][0] = 1
print(li)

出力：

[[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]

一般化すると、「li[i][X] の値を更新した際に li[i + 1][X]の値も更新される」と言うことができそうです。

原因：li[i][X] と li[i + 1][X]が同じメモリアドレスを指している！？

「1. ２重のfor loop」で生成した二次元配列は、それぞれの要素が異なるメモリアドレスを指しています。一方で、「2. ２重の掛け算」で生成した二次元配列は、li[i][X] と li[i + 1][X] が同じメモリアドレスを指しています。　これが問題を生み出していました。

Python3の組み込み関数 id() を使用し、実際にメモリアドレスを確認してみます。

厳密にはid()はメモリアドレスではなく「識別子」を返します。今回の目的は同一・異なるメモリアドレスを参照しているかどうかを明らかにすることであるためにid()を使用しています。id()で同じ値が返るならば同一のメモリアドレスを参照している、また反対ならそうではないと言えるためです。参照：https://docs.python.org/ja/3/library/functions.html#id

Demo

# 二次元配列を２重ループと掛け算の方法で生成
double_loop = [[0 for i in range(5)] for j in range(5)]
multiply = [[0] * 5] * 5

assert(hex(id(double_loop[0][0]) != hex(id(double_loop[1][0]))))
assert(hex(id(multiply[0][0])) == hex(id(multiply[1][0])))

double_loopでは、同じ列の要素でも、異なるメモリアドレスを参照しています。
しかし、multuplyでは、同じ列の要素は同一のメモリアドレスを参照しています。これが、「li[i][X] の値を更新した際に li[i + 1][X]の値も更新される」という問題の原因です。