海象运算符不赋变量？

Question

使用walrus运算符，我实现了合并排序：

def mergesort(array):
if len(array) == 1:
output = array
else:
pivot = len(array) // 2
left = mergesort(array[pivot:])
right = mergesort(array[:pivot])
output = []
while (l := len(left)) or (r := len(right)):
if l and r and left[0] < right[0]:
output.append(left.pop(0))
elif r:
output.append(right.pop(0))
else:
output.append(left.pop(0))

return output
mergesort([66, 93, 85, 46, 56, 88, 56, 75, 55, 99, 87])

但这会返回错误UnboundLocalError: local variable 'r' referenced before assignment:

---------------------------------------------------------------------------
UnboundLocalError                         Traceback (most recent call last)
/tmp/ipykernel_134/1678992391.py in <module>
----> 1 mergesort(array)
/tmp/ipykernel_134/4030760045.py in mergesort(array)
5     else:
6         pivot = len(array) // 2
----> 7         left = mergesort(array[pivot:])
8         right = mergesort(array[:pivot])
9         
...
/tmp/ipykernel_134/4030760045.py in mergesort(array)
10         output = []
11         while (l := len(left)) or (r := len(right)):
---> 12             if l and r and left[0] < right[0]:
13                 output.append(left.pop(0))
14             elif r:
UnboundLocalError: local variable 'r' referenced before assignment

为什么r不包含在我的for循环中，而l包含在？

Answer 1

布尔ORor是惰性的，所以当l为真时，(r := len(right))甚至不会被执行。

在这种情况下，您可以使用非懒惰的按位OR|，尽管这有点滥用。

或者只使用列表的真值，而不是它们的长度：

while left or right:
if left and right and left[0] < right[0]:
output.append(left.pop(0))
elif right:
output.append(right.pop(0))
else:
output.append(left.pop(0))

Btw最好使用<=而不是<，这样它就可以像合并排序一样稳定

附录：享受懒惰的乐趣：

while left or right:
which = (left or right)[0] <= (right or left)[0] and left or right
output.append(which.pop(0))

另一个，注意，我切换到while ... and ...，并在循环后附加剩余的非空的：

while left and right:
which = left if left[0] <= right[0] else right
output.append(which.pop(0))
output += left or right

或者回到你的风格：

while left and right:
if left[0] <= right[0]:
output.append(left.pop(0))
else:
output.append(right.pop(0))
output.extend(left or right)

Answer 2

1. Python获取len(left)表达式并将其求值为True
2. 这意味着它可以立即进入while循环，而不必检查第二条语句len(right)，因为Python是惰性的
3. 但是，这意味着r没有被实例化，因为它没有被求值

不幸的是，在表达式周围加上额外的括号毫无作用。

例如while ( (l:=len(left)) or (r:=len(right)) ):不起作用。

---

解决这一问题的一个选项是使用+而不是or，因为它们具有相同的逻辑含义，但+需要计算表达式的右侧。

例如

def mergesort(array):
if len(array) == 1:
output = array
else:
pivot = len(array) // 2
left = mergesort(array[pivot:])
right = mergesort(array[:pivot])
output = []
while (l:=len(left)) + (r:=len(right)):
if l and r and left[0] < right[0]:
output.append(left.pop(0))
elif r:
output.append(right.pop(0))
else:
output.append(left.pop(0))

return output

顺便说一句，如果你对while X and Y有同样的问题，其中X=0，你可以使用上面类似的技巧，但不是用+替换or，而是从0 * n == 0开始用*替换and。即while X * Y