Python: Delete all list indices meeting a certain condition

Question

to get right down to it, I'm trying to iterate through a list of coordinate pairs in python and delete all cases where one of the coordinates is negative. For example:

in the array:

map = [[-1, 2], [5, -3], [2, 3], [1, -1], [7, 1]]

I want to remove all the pairs in which either coordinate is < 0, leaving:

map = [[2, 3], [7, 1]]

My problem is that python lists cannot have any gaps, so if I loop like this:

i = 0
for pair in map:
        for coord in pair:
            if coord < 0:
                del map[i]
    i += 1

All the indices shift when the element is deleted, messing up the iteration and causing all sorts of problems. I've tried storing the indices of the bad elements in another list and then looping through and deleting those elements, but I have the same problem: once one is gone, the whole list shifts and indices are no longer accurate.

Is there something I'm missing?

Thanks.

Using map as a variable name isn't recommended, as there is a [function](http://docs.python.org/library/functions.html#map) with that name already. — GreenMatt, Aug 23 '11 at 15:36

jterrace · Answer 1 · 2013-11-12T00:29:57.813

3

You can use list comprehension for this:

>>> mymap = [[-1, 2], [5, -3], [2, 3], [1, -1], [7, 1]]
>>> mymap = [m for m in mymap if m[0] > 0 and m[1] > 0]
>>> mymap
[[2, 3], [7, 1]]

edited Nov 12 '13 at 00:29

answered Aug 23 '11 at 15:21

jterrace

64,866
22
157
202

2

Note that this does only work if no other references to map exist. – blubb Aug 23 '11 at 15:22
1

you could even chain the comparisons, `m[0] > 0 < m[1]`, which is cool but potentially confusing – agf Aug 23 '11 at 15:38
List comprehension is the Pythonic way (also `itertools.ifilter/ifilterfalse`), just as @blubb, @unutbu mentioned, don't shadow the builtin `map()` function by using it as the variable name here. – smci Nov 11 '13 at 23:45

unutbu · Accepted Answer · 2011-08-23T15:29:05.643

If the list is not large, then the easiest way is to create a new list:

In [7]: old_map = [[-1, 2], [5, -3], [2, 3], [1, -1], [7, 1]]

In [8]: new_map=[[x,y] for x,y in a_map if not (x<0 or y<0)]

In [9]: new_map
Out[9]: [[2, 3], [7, 1]]

You can follow this up with old_map = new_map if you want to discard the other pairs.

If the list is so large creating a new list of comparable size is a problem, then you can delete elements from a list in-place -- the trick is to delete them from the tail-end first:

the_map = [[-1, 2], [5, -3], [2, 3], [1, -1], [7, 1]]
for i in range(len(the_map)-1,-1,-1):
    pair=the_map[i]
    for coord in pair:
        if coord < 0:
            del the_map[i]

print(the_map)

yields

[[2, 3], [7, 1]]

PS. map is such a useful built-in Python function. It is best not to name a variable map since this overrides the built-in.

Thanks, both of you, I kept trying to find a way to freeze the list or insert placeholder indices that I completely missed the other solutions. Thanks! — Will, Aug 23 '11 at 15:29

score 1 · Answer 3 · answered Aug 23 '11 at 15:27

1

If you do not have any other references to the map list, a list comprehension works best:

map = [[a,b] for (a,b) in map if a > 0 and b > 0]

If you do have other references and need to actually remove elements from the list referenced by map, you have to iterate over a copy of map:

for coord in map[:]:
    if coord[0] < 0 or coord[1] < 0:
        map.remove(coord)

answered Aug 23 '11 at 15:27

blubb

9,510
3
40
82

Aargh. Remove-by-value `list.remove()` is O(n), also it only removes the first element with that value, so this will be buggy as well as O(n^2). Better to use `enumerate` and `del l[i]`, or else `itertools.ifilter`. – smci Nov 11 '13 at 23:53
See also [Difference between del, remove and pop on lists](http://stackoverflow.com/questions/11520492/difference-between-del-remove-and-pop-on-lists) – smci Nov 11 '13 at 23:54
@smci It isn't buggy: when an element ``coord`` that doesn't respect the condition is encountered during the iteration in ``map[:]``, there may be several identical elements in ``map[:]`` at this moment, but the fact is that the element is removed from ``map``, not ``map[:]`` that is a different list from ``map`` (see the identities of them to be convinced of that). Then, all the preceding identical elements, the ones that are positioned in ``map[:]`` before this element to remove, have already been removed from ``map`` and then the encountered element to remove is really the first in ``map`` – eyquem Nov 12 '13 at 13:01
@eyquem: this is terrible for two reasons: it's O(n^2) for no good reason, when we could simply do `enumerate(...), del l[i]`. No reason at all to use `.remove()` – smci Nov 13 '13 at 15:45
Second thing: using `remove()` is buggy if the predicate has other args or is not deterministic (uses random). Then it is not guaranteed that an element in `map` is the first occurrence of itself. – smci Nov 13 '13 at 15:52

score 0 · Answer 4 · answered Nov 12 '13 at 00:03

itertools.ifilter()/ifilterfalse() exist to do exactly this: filter an iterable by a predicate (not in-place, obviously). Better still, avoid creating and allocating the entire filtered list object if at all possible, just iterate over it:

import itertools

l = [(4,-5), (-8,2), (-2,-3), (4,7)]

# Option 1: create a new filtered list
l_filtered = list( itertools.ifilter(lambda p: p[0]>0 and p[1]>0, l) )

# Option 2:
for p in itertools.ifilter(lambda p: p[0]>0 and p[1]>0, l):
    ... <subsequent code on your filtered list>

David Heffernan · Answer 5 · 2011-08-23T16:45:02.377

0

If you wish to do this in place, without creating a new list, simply use a for loop with index running from len(map)-1 down to 0.

for index in range(len(map)-1,-1,-1):
    if hasNegativeCoord(map[index]):
        del(map[index])

Not very Pythonic, I admit.

edited Aug 23 '11 at 16:45

answered Aug 23 '11 at 15:31

David Heffernan

601,492
42
1,072
1,490

``for index in range(len(li)-1,-1,-1)`` would be better and would avoid this grblblpff instruction ``index -= 1``. - What the hell this algorithm has being not Pythonic ?? – eyquem Aug 23 '11 at 16:41

score 0 · Answer 6 · answered Aug 23 '11 at 16:25

0

Personally, I prefer in-place modification:

li = [[-1, 2], [5, -3], [2, 3], [1, -1], [7, 1]]
print li,'\n'


N = len(li)
for i,(a,b) in enumerate(li[::-1], start=1):
    if a<0 or b<0:
        del li[N-i]
print li

->

[[-1, 2], [5, -3], [2, 3], [1, -1], [7, 1]] 

[[2, 3], [7, 1]]

answered Aug 23 '11 at 16:25

eyquem

26,771
7
38
46

Why? It's more bloated, less idiomatic and worse performance. Deletion inside an iterator is a pain to parallelize. – smci Nov 11 '13 at 23:46

score 0 · Answer 7 · answered Aug 24 '11 at 01:30

If the list is small enough, it's more efficient to make a copy containing just the elements you need, as detailed in the other answers.

However, if the list is too large, or for some other reason you need to remove the elements from the list object in place, I've found the following little helper function quite useful:

def filter_in_place(func, target, invert=False):
    "remove all elements of target where func(elem) is false"
    pos = len(target)-1
    while pos >= 0:
        if (not func(target[pos])) ^ invert:
            del target[pos]
        pos -= 1

In your example, this could be applied as follows:

 >>> data = [[-1, 2], [5, -3], [2, 3], [1, -1], [7, 1]]
 >>> def is_good(elem):
         return elem[0] >= 0 and elem[1] >= 0
 >>> filter_in_place(is_good, data)
 >>> data
 [[2, 3], [7, 1]]

(This is just a list-oriented version of filter_in_place, one which supports all base Python datatypes is a bit more complex).

`itertools.ifilter()/ifilterfalse()` already exist for filtering a copy based on a predication function. I wonder how the performance compares to filter-in-place. — smci, Nov 11 '13 at 23:48

score -2 · Answer 8 · answered Aug 23 '11 at 17:15

-2

You probably want del pair instead.

answered Aug 23 '11 at 17:15

Aswin

658
6
2

Python: Delete all list indices meeting a certain condition

8 Answers8

Linked