Removal of element from list while traversing causes the next element to be skipped

bearophileHUGS at lycos.com bearophileHUGS at lycos.com
Wed Jan 30 14:17:41 CET 2008


If you don't want to reinvent the wheel all the time you can use this
one:

def inplacefilter(pred, alist):
    """inplacefilter(pred, alist): filters the given list like
filter(),
    but works inplace, minimizing the used memory. It returns None.

    >>> pr = lambda x: x > 2
    >>> l = []
    >>> inplacefilter(pr, l)
    >>> l
    []
    >>> l = [1,2,2]
    >>> inplacefilter(pr, l)
    >>> l
    []
    >>> l = [3]
    >>> inplacefilter(pr, l)
    >>> l
    [3]
    >>> l = [1,2,3,1,5,1,6,0]
    >>> r = filter(pr, l) # normal filter
    >>> r
    [3, 5, 6]
    >>> inplacefilter(pr, l)
    >>> r == l
    True
    """
    slow = 0
    for fast, item in enumerate(alist):
        if pred(item):
            if slow != fast:
                alist[slow] = alist[fast]
            slow += 1
    del alist[slow:]


If you use Psyco you can replace the enumerate() with a manually
incremented counter to speed up the code a bit, like this (untested):

def inplacefilter(pred, alist):
    slow = 0
    fast = 0
    for item in alist:
        if pred(item):
            if slow != fast:
                alist[slow] = alist[fast]
            slow += 1
        fast += 1
    del alist[slow:]

Bye,
bearophile



More information about the Python-list mailing list