CODEWITHSUNDEEP
pythonlistiteration
WesDec
WesDec

Reputation: 2158

Adding element to list while iterating

I know that it is not allowed to remove elements while iterating a list, but is it allowed to add elements to a python list while iterating. Here is an example:

for a in myarr:
    if somecond(a):
        myarr.append(newObj())

I have tried this in my code and it seems to work fine, however I don't know if it's because I am just lucky and that it will break at some point in the future?

I prefer not to copy the list since myarr is huge, and therefore it would be too slow. Also I need to check the appended objects with somecond().

At some point somecond(a) will be false, so there can not be an infinite loop.

Each object in myarr has a size, and each time somecond(a) is true and a new object is appended to the list, the new object will have a size smaller than a. somecond() has an epsilon for how small objects can be and if they are too small it will return "false".

Upvotes: 87

Views: 165633

Answers (12)

Nokib Sorkar
Nokib Sorkar

Reputation: 83

Assuming you are adding at the last of this list arr, You can try this method I often use,

arr = [...The list I want to work with]
current_length = len(arr)
i = 0
while i < current_length:
    current_element = arr[i]
    do_something(arr[i])
    # Time to insert
    insert_count = 1 # How many Items you are adding add the last
    arr.append(item_to_be inserted)
    # IMPORTANT!!!!  increase the current limit and indexer
    i += 1
    current_length += insert_count

This is just boilerplate and if you run this, your program will freeze because of infinite loop. DO NOT FORGET TO TERMINATE THE LOOP unless you need so.

Upvotes: 1

wheaties
wheaties

Reputation: 35970

You could use the islice from itertools to create an iterator over a smaller portion of the list. Then you can append entries to the list without impacting the items you're iterating over:

islice(myarr, 0, len(myarr)-1)

Even better, you don't even have to iterate over all the elements. You can increment a step size.

Upvotes: 12

Akshay Hazari
Akshay Hazari

Reputation: 3267

Alternate solution :

reduce(lambda x,newObj : x +[newObj] if somecond else x,myarr,myarr)

Upvotes: 1

cizixs
cizixs

Reputation: 13981

In short: If you'are absolutely sure all new objects fail somecond() check, then your code works fine, it just wastes some time iterating the newly added objects.

Before giving a proper answer, you have to understand why it considers a bad idea to change list/dict while iterating. When using for statement, Python tries to be clever, and returns a dynamically calculated item each time. Take list as example, python remembers a index, and each time it returns l[index] to you. If you are changing l, the result l[index] can be messy.

NOTE: Here is a stackoverflow question to demonstrate this.

The worst case for adding element while iterating is infinite loop, try(or not if you can read a bug) the following in a python REPL:

import random

l = [0]
for item in l:
    l.append(random.randint(1, 1000))
    print item

It will print numbers non-stop until memory is used up, or killed by system/user.

Understand the internal reason, let's discuss the solutions. Here are a few:

1. make a copy of origin list

Iterating the origin list, and modify the copied one.

result = l[:]
for item in l:
    if somecond(item):
        result.append(Obj())

2. control when the loop ends

Instead of handling control to python, you decides how to iterate the list:

length = len(l)
for index in range(length):
    if somecond(l[index]):
        l.append(Obj())

Before iterating, calculate the list length, and only loop length times.

3. store added objects in a new list

Instead of modifying the origin list, store new object in a new list and concatenate them afterward.

added = [Obj() for item in l if somecond(item)]
l.extend(added)

Upvotes: 10

Johnny
Johnny

Reputation: 685

Why don't you just do it the idiomatic C way? This ought to be bullet-proof, but it won't be fast. I'm pretty sure indexing into a list in Python walks the linked list, so this is a "Shlemiel the Painter" algorithm. But I tend not to worry about optimization until it becomes clear that a particular section of code is really a problem. First make it work; then worry about making it fast, if necessary.

If you want to iterate over all the elements:

i = 0  
while i < len(some_list):  
  more_elements = do_something_with(some_list[i])  
  some_list.extend(more_elements)  
  i += 1

If you only want to iterate over the elements that were originally in the list:

i = 0  
original_len = len(some_list)  
while i < original_len:  
  more_elements = do_something_with(some_list[i])  
  some_list.extend(more_elements)  
  i += 1

Upvotes: 66

HelloGoodbye
HelloGoodbye

Reputation: 3902

You can use an index and a while loop instead of a for loop if you want the loop to also loop over the elements that is added to the list during the loop:

i = 0
while i < len(myarr):
    a = myarr[i];
    i = i + 1;
    if somecond(a):
        myarr.append(newObj())

Upvotes: 3

RemcoGerlich
RemcoGerlich

Reputation: 31250

I had a similar problem today. I had a list of items that needed checking; if the objects passed the check, they were added to a result list. If they didn't pass, I changed them a bit and if they might still work (size > 0 after the change), I'd add them on to the back of the list for rechecking.

I went for a solution like

items = [...what I want to check...]
result = []
while items:
    recheck_items = []
    for item in items:
        if check(item):
            result.append(item)
        else:
            item = change(item)  # Note that this always lowers the integer size(),
                                 # so no danger of an infinite loop
            if item.size() > 0:
                recheck_items.append(item)
    items = recheck_items  # Let the loop restart with these, if any

My list is effectively a queue, should probably have used some sort of queue. But my lists are small (like 10 items) and this works too.

Upvotes: 3

Mike DeSimone
Mike DeSimone

Reputation: 42805

Expanding S.Lott's answer so that new items are processed as well:

todo = myarr
done = []
while todo:
    added = []
    for a in todo:
        if somecond(a):
            added.append(newObj())
    done.extend(todo)
    todo = added

The final list is in done.

Upvotes: 2

eumiro
eumiro

Reputation: 212835

Access your list elements directly by i. Then you can append to your list:

for i in xrange(len(myarr)):
    if somecond(a[i]):
        myarr.append(newObj())

Upvotes: 4

S.Lott
S.Lott

Reputation: 391818

You can do this.

bonus_rows = []
for a in myarr:
  if somecond(a):
      bonus_rows.append(newObj())
myarr.extend( bonus_rows )

Upvotes: 5

Rohan Monga
Rohan Monga

Reputation: 1777

well, according to http://docs.python.org/tutorial/controlflow.html

It is not safe to modify the sequence being iterated over in the loop (this can only happen for mutable sequence types, such as lists). If you need to modify the list you are iterating over (for example, to duplicate selected items) you must iterate over a copy.

Upvotes: 28

shahjapan
shahjapan

Reputation: 14335

make copy of your original list, iterate over it, see the modified code below

for a in myarr[:]:
      if somecond(a):
          myarr.append(newObj())

Upvotes: 4

Related Questions