CODEWITHSUNDEEP
pythonfor-loop
beoliver
beoliver

Reputation: 5759

appending a list that you are iterating over with a for loop

somebody mentioned that the function (in this case a method) below is no good as it modifies a list while iterating over it. Why is this, as it works exactly as I intended. I was actually quite pleased with it... Is there a better way of writing it.

Data structures, function and output as follows:

nodes = { ('foo','bar',1),
          ('foo','baz',1),
          ('baz','gad',0),
          ('boo','moo',1),
          ('goo','loo',0),
          ('bar','far',1),
          ('far','aaa',0) }

class Graph(dict):

    def __missing__(self, key):
        self[key] = set()
        return self[key]

    def add_node_pairs(self, node_pairs):
        for pair in node_pairs:
            nodeA, nodeB, weight = pair
            self[nodeA].add((weight, nodeB))
            self[nodeB].add((weight, nodeA)) 

    def find_paths(self, keys):      
        paths = [(key,) for key in keys if key in self]
        for path in paths:
            *oldkeys, key = path
            for weight, next_key in self[key]:
                if next_key not in oldkeys:
                    paths.append( path + (weight,next_key) )

        paths.sort()
        return paths

graph = Graph()
graph.add_node_pairs(nodes)
print(graph)
print( graph.find_paths(['foo']))

graph:

{ 'goo': {(0, 'loo')}, 
  'foo': {(1, 'bar'), (1, 'baz')}, 
  'aaa': {(0, 'far')}, 
  'far': {(1, 'bar'), (0, 'aaa')}, 
  'baz': {(0, 'gad'), (1, 'foo')}, 
  'loo': {(0, 'goo')}, 
  'moo': {(1, 'boo')}, 
  'boo': {(1, 'moo')}, 
  'bar': {(1, 'far'), (1, 'foo')}, 
  'gad': {(0, 'baz')} }

find_paths ('foo'):

[ ('foo',), 
  ('foo', 1, 'bar'), 
  ('foo', 1, 'bar', 1, 'far'), 
  ('foo', 1, 'bar', 1, 'far', 0, 'aaa'), 
  ('foo', 1, 'baz'), 
  ('foo', 1, 'baz', 0, 'gad') ]

Upvotes: 1

Views: 158

Answers (2)

Samy Arous
Samy Arous

Reputation: 6814

Consider the three following examples:

l = [1]
for x in l:
    if x < 10 # avoid infinite loop
         l.append(x+1)
    print x

This code is correct and is similar to the one you are using. The output is as expected 1..10. Appending an item on a for loop is ok (or inserting an item after the current iterator position).

Now try the same example but with an insert instead:

l = [1]
for x in l:
    if x < 10 # avoid infinite loop
         l.insert(0,x+1)
    print x

This time, you'll end up with a infinite loop. The reason is that the for loop will always check the next item and since we are inserting x at the beginning, the checked item will always be equal to 1. Inserting an item prior to the current iterator position is usually bad.

Finally check this example:

l = [1,2,3,4,5]
for x in l:
     print x
     l.remove(x)

The output of this function will be 1,3,5 different from the expected output: 1,2,3,4,5. Therefor, removing items before the current iterator is also bad.

To simplify things, let's just say that changing the content of a list while looping should be avoided, unless you know exactly what you are doing and what effects it could cause on the output.

Upvotes: 4

Ned Batchelder
Ned Batchelder

Reputation: 375484

Appending to a list you are iterating over is safe. If your code reviewer won't accept that, or it still feels squishy to you, you can use a two-phase approach:

paths = [blah blah]
next_paths = []
while paths:
    for path in paths:
        if something_or_other:
            next_paths.append(blah)
    paths = next_paths
    next_paths = []

Upvotes: 2

Related Questions