Как удалить элементы из списка во время итерации? - PullRequest
853 голосов
/ 30 июля 2009

Я перебираю список кортежей в Python и пытаюсь удалить их, если они соответствуют определенным критериям.

for tup in somelist:
    if determine(tup):
         code_to_remove_tup

Что я должен использовать вместо code_to_remove_tup? Я не могу понять, как удалить этот предмет таким образом.

Ответы [ 26 ]

722 голосов
/ 30 июля 2009

Вы можете использовать понимание списка, чтобы создать новый список, содержащий только те элементы, которые вы не хотите удалять:

somelist = [x for x in somelist if not determine(x)]

Или, назначив фрагменту somelist[:], вы можете изменить существующий список, чтобы он содержал только те элементы, которые вам нужны:

somelist[:] = [x for x in somelist if not determine(x)]

Этот подход может быть полезен, если есть другие ссылки на somelist, которые должны отражать изменения.

Вместо понимания вы также можете использовать itertools. В Python 2:

from itertools import ifilterfalse
somelist[:] = ifilterfalse(determine, somelist)

Или в Python 3:

from itertools import filterfalse
somelist[:] = filterfalse(determine, somelist)
536 голосов
/ 30 июля 2009

Ответы, предлагающие составления списков, почти верны - за исключением того, что они создают совершенно новый список и затем дают ему то же имя, что и старый список, они НЕ изменяют старый список на месте. Это отличается от того, что вы делаете при выборочном удалении, как в @ предложении Леннарта - это быстрее, но если к вашему списку обращаются по нескольким ссылкам, тот факт, что вы просто повторно устанавливаете одну из ссылок и НЕ изменение самого объекта списка может привести к тонким, катастрофическим ошибкам.

К счастью, чрезвычайно легко получить как скорость понимания списка, так и требуемую семантику изменения на месте - просто код:

somelist[:] = [tup for tup in somelist if determine(tup)]

Обратите внимание на небольшую разницу с другими ответами: этот НЕ назначается пустому имени - он присваивает фрагменту списка, который просто является целым списком, тем самым заменяя список содержимое внутри тот же объект списка Python , а не просто повторная установка одной ссылки (из предыдущего объекта списка в новый объект списка), как и другие ответы.

245 голосов
/ 30 июля 2009

Вам необходимо взять копию списка и сначала выполнить итерацию по нему, иначе итерация не удастся, что может привести к неожиданным результатам.

Например (зависит от типа списка):

for tup in somelist[:]:
    etc....

Пример:

>>> somelist = range(10)
>>> for x in somelist:
...     somelist.remove(x)
>>> somelist
[1, 3, 5, 7, 9]

>>> somelist = range(10)
>>> for x in somelist[:]:
...     somelist.remove(x)
>>> somelist
[]
107 голосов
/ 30 июля 2009
for i in range(len(somelist) - 1, -1, -1):
    if some_condition(somelist, i):
        del somelist[i]

Тебе нужно идти задом наперед, иначе это похоже на спиливание ветки дерева, на котором ты сидишь:

Пользователи Python 2: замените range на xrange, чтобы избежать создания жестко закодированного списка

46 голосов
/ 30 июля 2009

Лучшим подходом для такого примера будет понимание списка

somelist = [tup for tup in somelist if determine(tup)]

В тех случаях, когда вы делаете что-то более сложное, чем вызов функции determine, я предпочитаюсоздание нового списка и просто добавление к нему, как я иду.Например,

newlist = []
for tup in somelist:
    # lots of code here, possibly setting things up for calling determine
    if determine(tup):
        newlist.append(tup)
somelist = newlist

Копирование списка с использованием remove может сделать ваш код немного чище, как описано в одном из ответов ниже.Вам определенно не следует делать это для очень больших списков, поскольку это включает в себя сначала копирование всего списка, а также выполнение операции O(n) remove для каждого удаляемого элемента, что делает этот алгоритм O(n^2).

for tup in somelist[:]:
    # lots of code here, possibly setting things up for calling determine
    if determine(tup):
        newlist.append(tup)
42 голосов

Официальное руководство по Python 2 4.2. "для заявлений"

https://docs.python.org/2/tutorial/controlflow.html#for-statements

Эта часть документов проясняет, что:

  • вам нужно сделать копию итеративного списка, чтобы изменить его
  • один из способов сделать это с помощью обозначения среза [:]

Если вам нужно изменить последовательность, которую вы повторяете во время цикла (например, для дублирования выбранных элементов), рекомендуется сначала сделать копию. Итерация по последовательности неявно делает копию. Обозначение среза делает это особенно удобным:

>>> words = ['cat', 'window', 'defenestrate']
>>> for w in words[:]:  # Loop over a slice copy of the entire list.
...     if len(w) > 6:
...         words.insert(0, w)
...
>>> words
['defenestrate', 'cat', 'window', 'defenestrate']

Документация по Python 2 7.3. «За заявление»

https://docs.python.org/2/reference/compound_stmts.html#for

Эта часть документов еще раз говорит о том, что вам нужно сделать копию, и приводит фактический пример удаления:

Примечание: есть тонкость, когда последовательность модифицируется циклом (это может происходить только для изменяемых последовательностей, то есть списков). Внутренний счетчик используется для отслеживания того, какой элемент используется следующим, и он увеличивается на каждой итерации. Когда этот счетчик достигнет длины последовательности, цикл завершается. Это означает, что если набор удаляет текущий (или предыдущий) элемент из последовательности, следующий элемент будет пропущен (поскольку он получает индекс текущего элемента, который уже был обработан). Аналогично, если набор вставляет элемент в последовательность перед текущим элементом, текущий элемент будет обработан снова в следующий раз в цикле. Это может привести к неприятным ошибкам, которых можно избежать, сделав временную копию с использованием фрагмента всей последовательности, например,

for x in a[:]:
    if x < 0: a.remove(x)

Однако я не согласен с этой реализацией, поскольку .remove() должен выполнить итерацию всего списка , чтобы найти значение.

Вместо этого либо:

  • начать новый массив с нуля и .append() вернуться в конец: https://stackoverflow.com/a/1207460/895245

    Этот эффективный по времени, но менее компактный, поскольку он сохраняет копию массива во время итерации.

  • используйте del с индексом: https://stackoverflow.com/a/1207485/895245

    Это более экономно, так как распределяет копию массива, но менее эффективно по времени, поскольку списки CPython реализованы с динамическими массивами .

    Это означает, что удаление предмета требует сдвига всех следующих предметов назад на один, что равно O (N).

Как правило, вы просто хотите использовать более быстрый вариант .append() по умолчанию, если только память не представляет большой проблемы.

Может ли Python сделать это лучше?

Похоже, что этот конкретный Python API мог бы быть улучшен. Сравните его, например, с его Java-аналогом ListIterator , который ясно дает понять, что вы не можете изменять итерируемый список, кроме самого итератора, и дает вам эффективные способы сделать это без копирования списка.

Возможно, основное обоснование заключается в том, что списки Python предполагаются с поддержкой динамического массива, и поэтому любой тип удаления будет в любом случае неэффективным по времени, в то время как у Java есть более приятная иерархия интерфейса с ArrayList и LinkedList реализации ListIterator.

Кажется, что нет явного связанного типа списка в stdlib Python: Python Linked List

36 голосов
/ 30 июля 2009

Для тех, кто любит функциональное программирование:

somelist[:] = filter(lambda tup: not determine(tup), somelist)

или

from itertools import ifilterfalse
somelist[:] = list(ifilterfalse(determine, somelist))
10 голосов
/ 19 марта 2016

Может быть целесообразно просто создать новый список, если текущий элемент списка соответствует желаемым критериям.

так:

for item in originalList:
   if (item != badValue):
        newList.append(item)

и во избежание необходимости перекодировать весь проект с новым именем списков:

originalList[:] = newList

примечание, из документации Python:

copy.copy (х) Вернуть мелкую копию x.

copy.deepcopy (х) Вернуть глубокую копию х.

10 голосов
/ 13 марта 2017

Мне нужно было сделать это с огромным списком, и дублирование списка казалось дорогим, тем более что в моем случае количество удалений было бы небольшим по сравнению с оставшимися элементами. Я выбрал этот низкоуровневый подход.

array = [lots of stuff]
arraySize = len(array)
i = 0
while i < arraySize:
    if someTest(array[i]):
        del array[i]
        arraySize -= 1
    else:
        i += 1

Чего я не знаю, так это того, насколько эффективна пара удалений по сравнению с копированием большого списка. Пожалуйста, прокомментируйте, если у вас есть понимание.

8 голосов
/ 21 октября 2016

Этот ответ был первоначально написан в ответ на вопрос, который был помечен как дубликат: Удаление координат из списка на python

В вашем коде есть две проблемы:

1) При использовании remove () вы пытаетесь удалить целые числа, тогда как вам нужно удалить кортеж.

2) Цикл for пропустит элементы в вашем списке.

Давайте рассмотрим, что произойдет, когда мы выполним ваш код:

>>> L1 = [(1,2), (5,6), (-1,-2), (1,-2)]
>>> for (a,b) in L1:
...   if a < 0 or b < 0:
...     L1.remove(a,b)
... 
Traceback (most recent call last):
  File "<stdin>", line 3, in <module>
TypeError: remove() takes exactly one argument (2 given)

Первая проблема заключается в том, что вы передаете оба «a» и «b» в remove (), но remove () принимает только один аргумент. Итак, как мы можем заставить remove () правильно работать с вашим списком? Нам нужно выяснить, что представляет собой каждый элемент вашего списка. В этом случае каждый из них является кортежем. Чтобы увидеть это, давайте перейдем к одному элементу списка (индексация начинается с 0):

>>> L1[1]
(5, 6)
>>> type(L1[1])
<type 'tuple'>

Aha! Каждый элемент L1 на самом деле является кортежем. Так вот что мы должны передать, чтобы удалить (). Кортежи в python очень просты, они просто создаются путем заключения значений в скобки. «a, b» не является кортежем, но «(a, b)» является кортежем. Поэтому мы модифицируем ваш код и запускаем его снова:

# The remove line now includes an extra "()" to make a tuple out of "a,b"
L1.remove((a,b))

Этот код выполняется без ошибок, но давайте посмотрим на список, который он выводит:

L1 is now: [(1, 2), (5, 6), (1, -2)]

Почему (1, -2) все еще в вашем списке? Оказывается, изменение списка при использовании цикла для его перебора - очень плохая идея без особой тщательности. Причина того, что (1, -2) остается в списке, заключается в том, что местоположения каждого элемента в списке менялись между итерациями цикла for. Давайте посмотрим, что произойдет, если мы добавим приведенный выше код в более длинный список:

L1 = [(1,2),(5,6),(-1,-2),(1,-2),(3,4),(5,7),(-4,4),(2,1),(-3,-3),(5,-1),(0,6)]
### Outputs:
L1 is now: [(1, 2), (5, 6), (1, -2), (3, 4), (5, 7), (2, 1), (5, -1), (0, 6)]

Как вы можете сделать из этого результата, каждый раз, когда условный оператор оценивается как true и элемент списка удаляется, следующая итерация цикла будет пропускать оценку следующего элемента в списке, поскольку его значения теперь расположены в разные индексы.

Наиболее интуитивным решением является копирование списка, затем итерация по исходному списку и изменение только копии. Вы можете попробовать сделать это так:

L2 = L1
for (a,b) in L1:
    if a < 0 or b < 0 :
        L2.remove((a,b))
# Now, remove the original copy of L1 and replace with L2
print L2 is L1
del L1
L1 = L2; del L2
print ("L1 is now: ", L1)

Однако вывод будет идентичен предыдущему:

'L1 is now: ', [(1, 2), (5, 6), (1, -2), (3, 4), (5, 7), (2, 1), (5, -1), (0, 6)]

Это потому, что когда мы создавали L2, python фактически не создавал новый объект. Вместо этого он просто ссылался на L2 на тот же объект, что и L1. Мы можем проверить это с помощью «is», которое отличается от просто «равно» (==).

>>> L2=L1
>>> L1 is L2
True

Мы можем сделать истинную копию, используя copy.copy (). Тогда все работает как положено:

import copy
L1 = [(1,2), (5,6),(-1,-2), (1,-2),(3,4),(5,7),(-4,4),(2,1),(-3,-3),(5,-1),(0,6)]
L2 = copy.copy(L1)
for (a,b) in L1:
    if a < 0 or b < 0 :
        L2.remove((a,b))
# Now, remove the original copy of L1 and replace with L2
del L1
L1 = L2; del L2
>>> L1 is now: [(1, 2), (5, 6), (3, 4), (5, 7), (2, 1), (0, 6)]

Наконец, есть одно более чистое решение, чем создание совершенно новой копии L1. Функция реверсирования ():

L1 = [(1,2), (5,6),(-1,-2), (1,-2),(3,4),(5,7),(-4,4),(2,1),(-3,-3),(5,-1),(0,6)]
for (a,b) in reversed(L1):
    if a < 0 or b < 0 :
        L1.remove((a,b))
print ("L1 is now: ", L1)
>>> L1 is now: [(1, 2), (5, 6), (3, 4), (5, 7), (2, 1), (0, 6)]

К сожалению, я не могу адекватно описать, как работает reversed (). Он возвращает объект 'listreverseiterator', когда ему передается список. В практических целях вы можете думать об этом как о создании обращенной копии аргумента. Это решение, которое я рекомендую.

...