Pythonで二次元配列の初期化では「参照渡し」に気をつけないといけない

問題

先日、プログラミングコンテストで、バグチックな変な問題に足元をすくわれました。

それは、初期化した二次元配列の一部の値を更新したら、ほかの値も更新されるというものです。

以下のようなコードです。

# /usr/bin/python3
# coding: utf8

INF = 100010001001

if __name__ == '__main__':
    H, W = 4, 4
    # 二次元配列を準備
    memo = [[INF]*W]*H

    # (0,0)を0で更新
    memo[0][0] = 0

    print(*memo, sep="\n")
    # n行0列がすべて0で更新されてしまっている
    # [0, 100010001001, 100010001001, 100010001001]
    # [0, 100010001001, 100010001001, 100010001001]
    # [0, 100010001001, 100010001001, 100010001001]
    # [0, 100010001001, 100010001001, 100010001001]

原因

どうも、参照渡し系に起因する問題みたいでした。

for文と使って丁寧に初期化すると問題は起きず、ワンライナーで書くと問題が発現します。

    # 手寧な初期化
    memo = []
    for _ in range(H):
        memo.append([INF] * W)
    memo[0][0] = 0
    print(*memo, sep="\n")
    # (0,0)だけが0になってる
    # [0, 100010001001, 100010001001, 100010001001]
    # [100010001001, 100010001001, 100010001001, 100010001001]
    # [100010001001, 100010001001, 100010001001, 100010001001]
    # [100010001001, 100010001001, 100010001001, 100010001001]

    # 繰り返し演算字を使ったワンライナー
    memo_oneliner = [[INF]*W]*H
    memo_oneliner[0][0] = 0
    print(*memo_oneliner, sep="\n")
    # 0列すべて0
    # [0, 100010001001, 100010001001, 100010001001]
    # [0, 100010001001, 100010001001, 100010001001]
    # [0, 100010001001, 100010001001, 100010001001]
    # [0, 100010001001, 100010001001, 100010001001]

参照値(識別値)についてみてみます。

    # 手寧な初期化
    memo = []
    for _ in range(H):
        memo.append([INF] * W)
    for row in memo:
        print(id(row))
    # 識別値は全行で異なる
    # 140091744609096
    # 140091744586440
    # 140091744917000
    # 140091744586952

    # 繰り返し演算字を使ったワンライナー
    memo_oneliner = [[INF]*W]*H
    for row in memo_oneliner:
        print(id(row))
    # 識別値が全行で一致
    # 140091744586504
    # 140091744586504
    # 140091744586504
    # 140091744586504

繰り返し演算子を使うワンライナーのほうでは、全行で識別値が一致しています。

どうもPythonでは、繰り返し演算子を使う場合、新しいオブジェクト(この場合はlistオブジェクト)が都度作成されるわけでなく、 一つ作ったオブジェクトを使いまわすみたいですね。

イメージとしては

    # memo = [[INF]*W]*H のイメージ
    row = [INF]*W
    memo = []
    for _ in range(H):
        memo.append(row)

    # 検証
    memo[0][0] = 0
    print(*memo, sep="\n")
    # [0, 100010001001, 100010001001, 100010001001]
    # [0, 100010001001, 100010001001, 100010001001]
    # [0, 100010001001, 100010001001, 100010001001]
    # [0, 100010001001, 100010001001, 100010001001]
    for row in memo:
        print(id(row))
    # 140503221013320
    # 140503221013320
    # 140503221013320
    # 140503221013320

という感じです。

解決策

多次元配列を一意の値で初期化する場合、丁寧に初期化するのがよさそうです。

そのための、多次元配列初期化関数でも用意しておくのもいいかもしれません。

これでQOLがちょっぴり上がった。