Pythonのマルチターゲット代入の評価順序
竸プロでPython使ってたら変なミスしたので書いた
ARC065のD問題 - "連結 / Connectivity"をコンテスト中解いてたときのミス
D: 連結 / Connectivity - AtCoder Regular Contest 065 | AtCoder
解法は数分読んだら方針ついたので、UnionFindを2つ使って実装して提出。
その結果WAくらった。サンプルケースだけ通っている状態(死)。
Submission #1018502 - AtCoder Regular Contest 065 | AtCoder
ぱっと見て実装何もミスってないし、何かケース見落としているのかなーって考えても思いつかなかった(実際解法としては合ってて見落としはなかった)ので諦めって感じだった。
その後、以下のように4行目を修正して提出したらACだった。
Submission #1022086 - AtCoder Regular Contest 065 | AtCoder
原因はマルチターゲット代入の式(root関数内の"x = parent[x] = root(parent[x])")の評価順序だった。
C++的な考え方で書いてたのがダメだった。
今回は、改めてマルチターゲット代入*1について調べてみた。
マルチターゲット代入とは
以下のように、同じ値を複数の変数に代入する代入文である。
a = b = c = 10
C++における多重代入*2と言われる書き方とほぼ同じものである。
ただし、C++では"(a = (b = (c = (10))))"と評価されるが、Pythonでは言語リファレンスに書いてある以下の構文に基づいて"(a = b = c =) (10)"みたいな感じで解析され、右辺の評価値が左辺の変数それぞれに直接代入されるように評価される。
assignment_stmt ::= (target_list "=")+ (expression_list | yield_expression)
マルチターゲット代入の評価順序
マルチターゲット代入の評価順序についても言語リファレンスに書いてある。
6. 単純文 (simple statement) — Python 2.7.x ドキュメント
7. 単純文 (simple statement) — Python 3.5.2 ドキュメント
代入文は式のリスト (これは単一の式でも、カンマで区切られた式リストでもよく、後者はタプルになることを思い出してください) を評価し、得られた単一の結果オブジェクトをターゲット (target) のリストに対して左から右へと代入してゆきます。
つまり、"a = b = c = 10"であれば"a = 10; b = 10; c = 10"と評価される。
そのため、C++的な考え方で"x = a[x] = 4"と書くと、"a[x] = 4; x = 4"ではなく"x = 4; a[x] = 4"と評価されて意図しない処理が行われることになる。
実際に評価順序を見るために以下のPythonコードを書いた。
"A[a] = b"の処理を行う__setitem__メソッドを定義したクラスで処理する。
class A: def __setitem__(self, a, b): print("__setitem__(%d, %d)" % (a, b)) a = A() print("a[1] = a[2] = a[3] = 4") a[1] = a[2] = a[3] = 4 print("x = a[x] = 4") x = 1 x = a[x] = 4 print("a[x] = x = 4") x = 1 a[x] = x = 4
実行してみる。
$ python assign.py a[1] = a[2] = a[3] = 4 __setitem__(1, 4) __setitem__(2, 4) __setitem__(3, 4) x = a[x] = 4 __setitem__(4, 4) a[x] = x = 4 __setitem__(1, 4)
Python3で実行しても同様の結果が得られる。
この結果から、"a[1] = a[2] = a[3] = 4"では"a[1] = 4; a[2] = 4; a[3] = 4"という評価が行われ、"x = a[x] = 4"では"x = 4; a[x] = 4"という評価が行われていることが分かる。