Alex Rivera | Logout

Python: Memory usage and optimization when modifying lists

Asked 2010-04-13T15:54:08.230
20

The problem

My concern is the following: I am storing a relativity large dataset in a classical python list and in order to process the data I must iterate over the list several times, perform some operations on the elements, and often pop an item out of the list.

It seems that deleting one item out of a Python list costs O(N) since Python has to copy all the items above the element at hand down one place. Furthermore, since the number of items to delete is approximately proportional to the number of elements in the list this results in an O(N^2) algorithm.

I am hoping to find a solution that is cost effective (time and memory-wise). I have studied what I could find on the internet and have summarized my different options below. Which one is the best candidate ?

Keeping a local index:

while processingdata:
    index = 0
    while index < len(somelist):
        item = somelist[index]
        dosomestuff(item)
        if somecondition(item):
            del somelist[index]
        else:
            index += 1

This is the original solution I came up with. Not only is this not very elegant, but I am hoping there is better way to do it that remains time and memory efficient.

Walking the list backwards:

while processingdata:
    for i in xrange(len(somelist) - 1, -1, -1):
        dosomestuff(item)
        if somecondition(somelist, i):
            somelist.pop(i)

This avoids incrementing an index variable but ultimately has the same cost as the original version. It also breaks the logic of dosomestuff(item) that wishes to process them in the same order as they appear in the original list.

Making a new list:

while processingdata:
    for i, item in enumerate(somelist):
        dosomestuff(item)
    newlist = []
    for item in somelist:
        if somecondition(item):
            newlist.append(item)
    somelist = newlist
    gc
python optimization memory list iteration
Edit
Report

1 Answer

6

Without knowing the specifics of what you're doing with this list, it's hard to know exactly what would be best in this case. If your processing stage depends on the current index of the list element, this won't work, but if not, it appears you've left off the most Pythonic (and in many ways, easiest) approach: generators.

If all you're doing is iterating over each element, processing it in some way, then either including that element in the list or not, use a generator. Then you never need to store the entire iterable in memory.

def process_and_generate_data(source_iterable):
    for item in source_iterable:
        dosomestuff(item)
        if not somecondition(item):
            yield item

You would need to have a processing loop that dealt with persisting the processed iterable (writing it back to a file, or whatever), or if you have multiple processing stages you'd prefer to separate into different generators you could have your processing loop pass one generator to the next.

answered 2010-04-13T16:15:56.713

Your Answer