Python: create a function to modify a list by reference not value

Question

Hey all-

I'm doing some performance-critical Python work and want to create a function that removes a few elements from a list if they meet certain criteria. I'd rather not create any copies of the list because it's filled with a lot of really large objects.

Functionality I want to implement:

def listCleanup(listOfElements):
    i = 0
    for element in listOfElements:
        if(element.meetsCriteria()):
            del(listOfElements[i])
        i += 1
    return listOfElements

myList = range(10000)
myList = listCleanup(listOfElements)

I'm not familiar with the low-level workings of Python. Is myList being passed by value or by reference?

How can I make this faster?

Is it possible to somehow extend the list class and implement listCleanup() within that?

myList = range(10000)
myList.listCleanup()

Thanks-

Jonathan

Answer 1

In Python, lists are always passed by reference.

The size of the objects in the list doesn't affect the lists performance, because the lists only stores references to the objects. However, the number of items in the list does affect the performance of some operations - such as removing an element, which is O(n).

As written, listCleanup is worst-case O(n**2), since you have the O(n) del operation within a loop that is potentially O(n) itself.

If the order of the elements doesn't matter, you may be able to use the built-in set type instead of a list. The set has O(1) deletions and insertions. However, you will have to ensure that your objects are immutable and hashable.

Otherwise, you're better off recreating the list. That's O(n), and your algorithm needs to be at least O(n) since you need to examine every element. You can filter the list in one line like this:

listOfElements[:] = [el for el in listOfElements if el.MeetsCriteria()]

Answer 2

Python passes everything the same way, but calling it "by value" or "by reference" will not clear everything up, since Python's semantics are different than the languages for which those terms usually apply. If I was to describe it, I would say that all passing was by value, and that the value was an object reference. (This is why I didn't want to say it!)

If you want to filter out some stuff from a list, you build a new list

foo = range(100000)
new_foo = []
for item in foo:
    if item % 3 != 0: # Things divisble by 3 don't get through
        new_foo.append(item)

or, using the list comprehension syntax

 new_foo = [item for item in foo if item % 3 != 0]

Python will not copy the objects in the list, but rather both foo and new_foo will reference the same objects. (Python never implicitly copies any objects.)

---

You have suggested you have performance concerns about this operation. Using repeated del statements from the old list will result in not code that is less idiomatic and more confusing to deal with, but it will introduce quadratic performance because the whole list must be reshuffled each time.

To address performance:

• Get it up and running. You can't figure out what your performance is like unless you have code working. This will also tell you whether it is speed or space that you must optimize for; you mention concerns about both in your code, but oftentimes optimization involves getting one at the cost of the other.

• Profile. You can use the stdlib tools for performance in time. There are various third-party memory profilers that can be somewhat useful but aren't quite as nice to work with.

• Measure. Time or reprofile memory when you make a change to see if a change makes an improvement and if so what that improvement is.

• To make your code more memory-sensitive, you will often want a paradigm shift in how you store your data, not microoptimizastions like not building a second list to do filtering. (The same is true for time, really: changing to a better algorithm will almost always give the best speedup. However, it's harder to generalize about speed optimizations).

  Some common paradigm shifts to optimize memory consumption in Python include

  1. Using Generators. Generators are lazy iterables: they don't load a whole list into memory at once, they figure out what their next items are on the fly. To use generators, the snippets above would look like

     foo = xrange(100000) # Like generators, xrange is lazy
     def filter_divisible_by_three(iterable):
         for item in foo:
             if item % 3 != 0:
                 yield item
     
     
     new_foo = filter_divisible_by_three(foo)
     

     or, using the generator expression syntax,

     new_foo = (item for item in foo if item % 3 != 0)
     

  2. Using numpy for homogenous sequences, especially ones that are numerical-mathy. This can also speed up code that does lots of vector operations.

  3. Storing data to disk, such as in a database.

Answer 3

Just to be clear:

def listCleanup(listOfElements):
    i = 0
    for element in listOfElements:
        if(element.meetsCriteria()):
            del(listOfElements[i])
        i += 1
    return listOfElements

myList = range(10000)
myList = listCleanup(listOfElements)

is the same as

def listCleanup(listOfElements):
    i = 0
    for element in listOfElements:
        if(element.meetsCriteria()):
            del(listOfElements[i])
        i += 1

myList = range(10000)
listCleanup(listOfElements)

?

Answer 4

Looks like premature optimization. You should try to get a better understanding of how python works before trying to optimize.

In this particular case you don't need to worry about object size. Copying a list is using list comprehension or slice will only perform surface copy (copy references to objects even if the term does not really apply well to python). But the number of items in the list may matter because del is O(n). There may be other solutions, like replacing an item with None or a conventional Null object, or using another data structure like a set or a dictionary where cost of deleting item is much lower.

Answer 5

modifying your data structure as you're iterating over it is like shooting yourself in the foot... iteration fails. you might as well take others' advice and just make a new list:

myList = [element for element in listOfElements if not element.meetsCriteria()]

the old list -- if there are no other references to it -- will be deallocated and the memory reclaimed. better yet, don't even make a copy of the list. change the above to a generator expression for a more memory-friendly version:

myList = (element for element in listOfElements if not element.meetsCriteria())

all Python object access is by reference. objects are created and variables are just references to those objects. however, if someone wanted to ask the purist question, "what type of call semantics does Python use, call-by-reference or call-by-value?" the answer will have to be, "Neither... and both." the reason is because calling conventions are less important to Python than object type.

if an object is mutable, it can be modified regardless of what scope you're in... as long as you have a valid object reference, the object can be changed. if the object is immutable, then that object cannot be changed no matter where you are or what reference you have.

Answer 6

Deleting list elements in-situ is possible, but not by going forwards through the list. Your code just plain doesn't work -- as the list shrinks, you can miss out examining elements. You need to go backwards, so that the shrinking part is behind you, with rather horrid code. Before I show you that, there are some preliminary considerations:

First, how did that rubbish get into the list? Prevention is better than cure.

Second, how many elements in the list, and what percentage are likely to need deletion? The higher the percentage, the greater the likelihood that it's better to create a new list.

OK, if you still want to do it in-situ, contemplate this:

def list_cleanup_fail(alist, is_bad):
    i = 0
    for element in alist:
        print "i=%d alist=%r alist[i]=%d element=%d" % (i, alist, alist[i], element)
        if is_bad(element):
            del alist[i]
        i += 1

def list_cleanup_ok(alist, is_bad):
    for i in xrange(len(alist) - 1, -1, -1):
        print "i=%d alist=%r alist[i]=%d" % (i, alist, alist[i])
        if is_bad(alist[i]):
            del alist[i]

def is_not_mult_of_3(x):
    return x % 3 != 0

for func in (list_cleanup_fail, list_cleanup_ok):
    print
    print func.__name__
    mylist = range(11)
    func(mylist, is_not_mult_of_3)
    print "result", mylist

and here is the output:

list_cleanup_fail
i=0 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=0 element=0
i=1 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=1 element=1
i=2 alist=[0, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=3 element=3
i=3 alist=[0, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=4 element=4
i=4 alist=[0, 2, 3, 5, 6, 7, 8, 9, 10] alist[i]=6 element=6
i=5 alist=[0, 2, 3, 5, 6, 7, 8, 9, 10] alist[i]=7 element=7
i=6 alist=[0, 2, 3, 5, 6, 8, 9, 10] alist[i]=9 element=9
i=7 alist=[0, 2, 3, 5, 6, 8, 9, 10] alist[i]=10 element=10
result [0, 2, 3, 5, 6, 8, 9]

list_cleanup_ok
i=10 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=10
i=9 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] alist[i]=9
i=8 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] alist[i]=8
i=7 alist=[0, 1, 2, 3, 4, 5, 6, 7, 9] alist[i]=7
i=6 alist=[0, 1, 2, 3, 4, 5, 6, 9] alist[i]=6
i=5 alist=[0, 1, 2, 3, 4, 5, 6, 9] alist[i]=5
i=4 alist=[0, 1, 2, 3, 4, 6, 9] alist[i]=4
i=3 alist=[0, 1, 2, 3, 6, 9] alist[i]=3
i=2 alist=[0, 1, 2, 3, 6, 9] alist[i]=2
i=1 alist=[0, 1, 3, 6, 9] alist[i]=1
i=0 alist=[0, 3, 6, 9] alist[i]=0
result [0, 3, 6, 9]

Answer 7

I don't think anyone mentioned actually using filter. Since a lot of the answers came from well respected people, I'm sure that I'm the one that's missing something. Could someone explain what would be wrong with this:

new_list = filter(lambda o: o.meetsCriteria(), myList)