CODEWITHSUNDEEP
pythonlistdeque
Sjieke
Sjieke

Reputation: 412

Python deque scope?

I am learning Python and have been trying to make a deque. However, I get incorrect output and I am not sure why. My code is as follows:

p = [2, 1], [1, 1]
init_q= deque()

init_q.append(p)
for i in range(len(p)):
    for j in range(len(p[i])):
        temp = p[i][j]
        p[i][j] = 0
        init_q.append(p)
        p[i][j] = temp

while init_q:
    print init_q.pop()

In this code I take in a list, I then want to create a queue with 5 list, 4 of which have a 0 in them at different locations, the result I want is:

([2, 1], [1, 1])
([0, 1], [1, 1])
([2, 0], [1, 1])
([2, 1], [0, 1])
([2, 1], [1, 0])

However, the result I get is:

([2, 1], [1, 1])
([2, 1], [1, 1])
([2, 1], [1, 1])
([2, 1], [1, 1])
([2, 1], [1, 1])

Upvotes: 6

Views: 779

Answers (3)

siddharthlatest
siddharthlatest

Reputation: 2257

I created a visualization on Python Tutor by simplifying your code. Fiddle around and you can easily see what's happening.

A single line change to your code can fix this.

init_q.append(map(list, p))    # Initialize a new list from p's element lists

Here's the visualization by using the above change.

Upvotes: 3

abarnert
abarnert

Reputation: 366003

Following up my comment to Ned Batchelder's answer, here's how you could do the same thing immutably:

for i in range(len(p)):
    for j in range(len(p[i])):
        temprow = [0 if y==j else p[i][y] for y in range(len(p[i]))]
        temp = [temprow if x==i else p[x] for x in range(len(p))]
        init_q.append(temp)

In this case, I think the result is a lot less readable than his suggestion:

        temp = copy.deepcopy(p)
        temp[i][j] = 0
        init_q.append(temp)

As I said, sometimes it makes things simpler, sometimes less simple… But the point is that it's easier to reason about. You don't have to worry about whether multiple lists in init_q—or, worse, sub-lists within those lists—are sharing identity.

Whether the tradeoff is worth it is really a case-by-case decision, and probably different for each programmer. In this case, I wouldn't use the immutable solution, and I doubt many other (Python) programmers would. But it's worth knowing how to write it.

You also might consider writing this as a 3D list, instead of a deque of 2D lists, and then feeding it into the deque. It's obviously equivalent, but conceptually it may be simpler to think of this way:

init_q.append(p)
q = [copy.deepcopy(p) for i in range(len(p)) for j in range(len(p[i]))]
for i in range(len(p)):
    for j in range(len(p[i])):
        q[i*len(p[i])+j][i][j] = 0
init_q.extend(q)

PS, if you're doing a lot of this kind of thing, you may want to take a look at numpy. If this is your whole problem, it's not going to do you any good… but if you do anything more complicated with multi-dimensional arrays, it will.

Upvotes: 1

Ned Batchelder
Ned Batchelder

Reputation: 375912

You are putting an object in the deque, then changing the object. In fact, you always put the same object into the deque, so all the deque has are references to one object p.

Upvotes: 4

Related Questions