0

I'm implementing a DFS algorithm and I want to create a list of dictionaries. But I found that if I use [dict()] * n, I got unexpected result.

I'm not sure what is the difference between "[dict()] * n" and a "for loop with .append(dict())".

Any hint is appreciated.

def DFS1(nums, level, target, dp):
    if level == len(nums):
        if target == 0:
            return 1
        else:
            return 0

    if target in dp[level]:
        return dp[level][target]

    cnt1 = DFS1(nums, level + 1, target + nums[level], dp)
    cnt2 = DFS1(nums, level + 1, target - nums[level], dp)
    dp[level][target] = cnt1 + cnt2
    return cnt1 + cnt2

test code is: 

nums = [1,1,1,1,1]
n = len(nums)
target = -3
#dp = [dict()] * n   #<== This does not work as expected
dp = []
for i in range(0, n):
    dp.append(dict())

resCnt = DFS1(nums, 0, target, dp)
print(resCnt)
CodingNow
  • 998
  • 1
  • 11
  • 23
  • 2
    Thats this behaviour https://stackoverflow.com/questions/240178/list-of-lists-changes-reflected-across-sublists-unexpectedly – user1767754 Dec 26 '17 at 00:58

1 Answers1

2

What basically happens is that you are creating references:

x = [dict()] * 10
print x
>[{}, {}, {}, {}, {}, {}, {}, {}, {}, {}]  #looks fine

x[0]['x'] = 3                              #all references share same memory
print x
[{'x': 3}, {'x': 3}, {'x': 3}, {'x': 3}, {'x': 3}, {'x': 3}, {'x': 3}, {'x': 3}, {'x': 3}, {'x': 3}]

Visually following happens:

enter image description here

To avoid referencing, you have to explicitly tell python to create new dictionaries every time:

x = [{} for x in range(10)]
print x
>[{}, {}, {}, {}, {}, {}, {}, {}, {}, {}]
x[0]['x'] = 3
print x
>[{'x': 3}, {}, {}, {}, {}, {}, {}, {}, {}, {}]

Visual Representation: Every bucket has it's own copy of the dict:

enter image description here

user1767754
  • 23,311
  • 18
  • 141
  • 164