Python在unpacking上的一個小陷阱

01-29

在Python中，交換兩個變數的值很方便：

a, b = b, an

同樣的，對於列表也簡單直接：

a[i], a[j] = a[j], a[i]n

至此都很trivial。但是請看下面這個交換：

j = 0nm = [1, 3, 5] nj, m[j] = m[j], 99n

結果違背了（我的）直覺：

print(j) # 1nprint(m) # [1, 99, 5]n

並非如我預期的m[0]被寫為99，而是m[1]被寫了。如果我們交換該語句兩邊對應的順序：

m[j], j = 99, m[j]nnprint(j) # 1nprint(m) # [99, 3, 5] # different resultn

個人認為這是個略坑爹的結果：unpacking左右邊子表達式的順序是影響結果的，尤其是子表達式間有依賴的時候（比如這裡m[j]是依賴j的）。究其原因，我們可以編譯位元組碼看看：

>>> import disn>>> dis.dis("j, m[j] = m[j], 99")n 1 0 LOAD_NAME 0 (m)n 3 LOAD_NAME 1 (j)n 6 BINARY_SUBSCRn 7 LOAD_CONST 0 (99)n 10 ROT_TWOn 11 STORE_NAME 1 (j)n 14 LOAD_NAME 0 (m)n 17 LOAD_NAME 1 (j)n 20 STORE_SUBSCRn 21 LOAD_CONST 1 (None)n 24 RETURN_VALUEn

第11位置的STORE_NAME和第17位置的LOAD_NAME指令表明，在執行unpacking綁定時，j的值是實時存取的，所以m[j]載入的是剛被改寫的新的j值，而且子表達式的綁定順序是從左至右。

相比之下，等號右側的整個結構值則不是實時的，在執行unpacking之前已入棧預存起來。

（註：第10位置的ROT_TWO用於顛倒等號右側已入棧元素的順序，從第11位置開始，每次STORE會彈出一個棧頂元素。這樣就實現了等號左右側同時對應的從左至右的綁定順序。若右側元素超出三個，則ROT_TWO會被更通用的UNPACK_SEQUENCE替換掉。）

雖然本文這種情形不太常見，但是在實現一些演算法題細節的時候，偷懶可能會被坑。所以童鞋們以後在遇到

i, a[i] = 1, 2n# not equivalent tona[i], i = 2, 1n

的情形時要稍加註意，以免掉坑難以查錯。

==========================================

@王贇 Maigo 問是什麼情況下遇到這個問題的，其實是來源於一道代碼題：

給定兩個長度為 $N$ 的數組 $a$ 和 $m$ ， $a$ 是由一組巨大元素構成的未排序數組， $m$ 是由 $a$ 中元素的索引構成的數組，且 $m$ 中元素順序是按索引 $a$ 元素排序的結果。
即： $a_{m_0} le a_{m_1} le ... le a_{m_{N-1}}$ 。
現在欲對 $a$ 進行inplace排序，求O(N)時間和O(1)空間的方法。

解法為：

def sort_with(a, m):n for p in range(len(a)):n j = pn while m[j] > p:n a[j], a[m[j]] = a[m[j]], a[j]n j, m[j] = m[j], -1 # WRONGn

標記WRONG的這一行試圖做這個：

$j^{text{(new)}} := {m_{j^{text{(old)}}}}; quadnm_{j^{text{(old)}}} := -1$

實際效果卻是：

$j^{text{(new)}} := {m_{j^{text{(old)}}}}; quadnm_{j^{text{(new)}}} := -1$

從而暴露了本文所提這個問題。嚴格正確的寫法應該拆開幾個賦值語句：

def sort_with(a, m):n for p in range(len(a)):n j = pn while m[j] > p:n a[j], a[m[j]] = a[m[j]], a[j]n j_old = jn j = m[j_old]n m[j_old] = -1n

還有一個「恰好正確」的寫法，可以把三行並作一行（不建議這樣寫）：

def sort_with(a, m):n for p in range(len(a)):n j = pn while m[j] > p:n a[j], a[m[j]] = a[m[j]], a[j]n m[j], j = -1, m[j] # coincidentally correctn

這個特性也暴露了mutability和unpacking蘊含語義不太明確的問題，故以此文為記。

====================================

關於unpacking，這裡再給一個略tricky的例子：

a = 1nb = 5na, (b, a) = 9, (a, b)nnprint(a)nprint(b)n

問輸出結果是多少？

事實上，Python將右側先整體求值並緩存結果，然後遍歷左側進行綁定。即第三行代碼相當於：

a = 9nb = 1 # (a == 1) value before evaluating RHSna = 5 # (b == 5) value before evaluating RHSn

我們可以看dis的結果：

>>> dis.dis(a, (b, a) = 9, (a, b))n 1 0 LOAD_CONST 0 (9)n 3 LOAD_NAME 0 (a)n 6 LOAD_NAME 1 (b)n 9 BUILD_TUPLE 2n 12 ROT_TWOn 13 STORE_NAME 0 (a)n 16 UNPACK_SEQUENCE 2n 19 STORE_NAME 1 (b)n 22 STORE_NAME 0 (a)n 25 LOAD_CONST 1 (None)n 28 RETURN_VALUEn

前四個指令即構造等號右側的結構，第六個指令開始遍歷左側進行綁定。這裡第16位置的UNPACK_SEQUENCE指令右側的2是指令參數，表示接下需要兩次STORE（或遞歸的UNPACK_SEQUENCE）。本指令會把棧內的元素全部彈出到另一個臨時棧，再從臨時棧取。

比如這裡右手邊入棧的那個tuple是(a, b)，入棧後是a的舊值在棧里，b的舊值在棧頂，通過UNPACK到臨時棧反序後，接下來的STORE則先取出的是a的舊值，後b的舊值。

希望對感興趣的童鞋有所幫助~