CODEWITHSUNDEEP
pythondictionaryreferencetreedereference
user1850980
user1850980

Reputation: 1021

Python: Changing Values in a Dictionary Tree Structure

I have a tree structure in Python where each node is a list [dict,int]. The dict points to the children. The leaves are plain ints, no lists to save memory. Now I want to scale the integer value in each node by a constant factor. I have written the following recursive function that takes the root node and the factor:

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

I have the impression that the leave nodes are not changed because of some of these Python reference/dereference issues. Is this true?

Upvotes: 0

Views: 1189

Answers (3)

Ned Batchelder
Ned Batchelder

Reputation: 375484

This statement doesn't do what you think:

node *= factor

This only multiplies the local variable node, it won't modify the dict value you originally passed in. Ints are immutable, so there is no way to pass one into a function and have the function modify it in-place.

This article has details on how names and values work in Python: Facts and Myths about Names and Values in Python.

BTW: the best way to check a type is (if you must) is:

if not isinstance(node, list):

Upvotes: 1

user1850980
user1850980

Reputation: 1021

Since I am not going to change my data structure, I had to do the following (in my opinion this is one of these cases where Python sucks):

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);

And then change the root int separately before calling the recursion. Fortunately, in this case there might be the extra benefit that this should be faster because there is no function call for leave nodes...

Upvotes: 0

mhawke
mhawke

Reputation: 87054

This snippet explains why the leaf nodes (type int) are not updated:

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]

So you can see that n is not changed because only the local variable x is updated in function f(x). However, the list l is updated because it is mutable.

Any easy way to fix this is to wrap your leaf nodes in a list (or other mutable type) and store (and update) the leaf value. Then you can write scale() like this:

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)

Upvotes: 1

Related Questions