Python：修改字典树结构中的值

Question

我在Python中有一个树形结构，每个节点都是一个列表，里面包含一个字典和一个整数。这个字典指向子节点。树的叶子节点就是普通的整数，没有列表，这样可以节省内存。现在我想把每个节点的整数值按一个固定的比例进行缩放。我写了一个递归函数，它接收根节点和这个比例：

def scale(node,factor):
    if type(node) != list:
        node *= factor;
    else:
        node[1] *= factor;
        for key in node[0]:
            scale(node[0][key],factor);

我感觉叶子节点没有被改变，这可能是因为Python中的一些引用和解引用的问题。这是真的吗？

Answer 1

因为我不打算改变我的数据结构，所以我不得不这样做（在我看来，这是Python不太好的一种情况）：

def scale(node,factor):
    for key in node[0]:
        if type(node[0][key]) != list:
            node[0][key] *= factor;
        else:
            node[0][key][1] *= factor;
            scale(node[0][key],factor);

然后在调用递归之前，单独修改根节点的整数。幸运的是，在这种情况下，可能还有一个额外的好处，那就是这样做可能会更快，因为对于叶子节点没有函数调用……

Answer 2

这段代码解释了为什么叶子节点（类型为int）没有被更新：

def f(x):
    print "got x", x
    x *= 10
    print "set x to", x

>>> n = 123
>>> f(n)
got x 123
set x to 1230
>>> n
123

>>> l=[1]
>>> f(l)
got x [1]
set x to [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
>>> l
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

你可以看到，n没有改变，因为在函数f(x)中，只有局部变量x被更新了。然而，列表l是可以改变的，所以它被更新了。

一个简单的解决办法是把你的叶子节点放在一个list（或其他可变类型）中，并存储（和更新）叶子值。这样你就可以像下面这样写scale()：

def scale(node,factor):
    if len(node) == 1:   # leaf node is a list containing a single int
        node[0] *= factor;
    else:
        node[1] *= factor;
        for key in node[0]:
            scale(node[0][key],factor)

Answer 3

这个语句并不是你想的那样：

node *= factor

这只是对本地变量 node 进行了乘法运算，并不会改变你最开始传入的字典里的值。整数是不可变的，这意味着你不能把一个整数传给函数，然后让这个函数直接修改它。

这篇文章详细讲解了在Python中名字和数值是如何运作的：关于Python中名字和数值的事实与误区。

顺便说一下：检查类型的最好方法是（如果你真的需要的话）：

if not isinstance(node, list):