Элегантный способ удалить элементы из последовательности в Python? [Дубликат]

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

for name in names:
    if name[-5:] == 'Smith':
        names.remove(name)

Я обычно заканчиваю тем, что делаю что-то вроде этого:

toremove = []
for name in names:
    if name[-5:] == 'Smith':
        toremove.append(name)
for name in toremove:
    names.remove(name)
del toremove

Это неэффективно, довольно некрасиво и возможно глючит (как он обрабатывает несколько записей «Джона Смита»?). У кого-нибудь есть более элегантное решение или хотя бы более эффективное?

Как насчет того, который работает со словарями?

20.08.2008 17:41:24
Ваш код удаляет несколько Smiths или вы его редактировали?
systemovich 20.07.2010 12:24:30
14 ОТВЕТОВ
РЕШЕНИЕ

Два простых способа выполнить только фильтрацию:

  1. Использование filter:

    names = filter(lambda name: name[-5:] != "Smith", names)

  2. Использование списочных представлений:

    names = [name for name in names if name[-5:] != "Smith"]

Обратите внимание, что в обоих случаях сохраняются значения, для которых оценивается функция предиката True, поэтому вам необходимо изменить логику (т.е. вы говорите: «оставьте людей, у которых нет фамилии Смит», вместо «удалите людей с фамилией» Смит ").

Редактировать Забавно ... два человека по отдельности разместили оба ответа, которые я предложил, когда я публиковал свой.

56
10.04.2012 05:32:20
not name.endswith("Smith")выглядит намного лучше :-)
Jochen Ritzel 7.12.2009 04:13:47
конечно, если вам нравится удобочитаемость или что-то.
John 7.12.2009 22:31:09
Может кто-нибудь объяснить [-5:]мне. Что произойдет, если вы хотите проверить весь список?
Sevenearths 14.09.2011 15:45:49
@ Sevenearths: «[-5:]» принимает последние пять символов имени, так как мы хотим знать, заканчивается ли имя на «Смит». Как предположил Йохен, выражение «имя [: - 5]! =« Смит »» можно было бы написать более наглядно, как «не имя.endswith (« Смит »)».
Edward Loper 14.11.2011 14:57:43
Не забудьте упомянуть увеличение производительности, используя name.endswith("Smith")вместо[-5:]
notbad.jpeg 3.07.2014 01:24:11

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

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

редактировать: кто-то понимает, что он просил «эффективность» ... все эти предложенные методы просто повторяются по списку, который совпадает с тем, что он предлагал.

-2
21.08.2008 20:33:22
Для некоторых проблем переключение на другую структуру данных на самом деле не вариант, в частности, если вы не знаете условия фильтра до тех пор, пока не будет создан набор элементов. Например, если вы выполняете какой-либо поиск и хотите сократить свое пространство поиска, вы, как правило, заранее не будете знать подходящее условие отсечения для сокращения.
Edward Loper 9.01.2011 14:44:26
names = filter(lambda x: x[-5:] != "Smith", names);
2
20.08.2008 17:48:56

фильтр будет здорово для этого. Простой пример:

names = ['mike', 'dave', 'jim']
filter(lambda x: x != 'mike', names)
['dave', 'jim']

Редактировать: понимание списка Кори тоже потрясающе.

3
20.08.2008 17:49:10

Использование понимания списка

list = [x for x in list if x[-5:] != "smith"]
10
20.08.2008 17:49:29
Кажется, на самом деле не работает для целых чисел. temprevengelist = "0-12354-6876" temprevengelist = temprevengelist.split ('-') list = [x для x в temprevengelist, если x [-5:]! = 6876]
Fahim Akhter 28.01.2010 07:48:53
@FahimAkhter: Это потому, что вы сравниваете целое число со строкой: в Python 6876(int) и "6876"(строка) являются двумя разными значениями и не равны. Попробуйте заменить x[-5:] != 6876на x[-5:] != "6876"илиint(x[-5:]) != 6876
Edward Loper 20.04.2012 19:33:11

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

names = ['Jones', 'Vai', 'Smith', 'Perez']

item = 0
while item <> len(names):
    name = names [item]
    if name=='Smith':
        names.remove(name)
    else:
        item += 1

print names

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

2
20.08.2008 18:20:33
Я думаю, что names.remove (name) может быть операцией O (n), что сделает алгоритм O (n ^ 2).
postfuturist 4.10.2008 03:28:27
Я лично написал бы свое выражение while как item <len (names), на всякий случай, если я испортил логику внутри цикла. (хотя это не похоже на то, что вы делали)
Miquella 8.10.2008 00:31:51
Вероятно, более эффективно использовать del names [item] или names.pop (item), чем names.remove (name). Скорее всего, это будет O (n), хотя я не знаю, как это работает.
rjmunro 5.11.2008 13:11:18

Фильтр и списки подходят для вашего примера, но у них есть пара проблем:

  • Они делают копию вашего списка и возвращают новый, и это будет неэффективно, если исходный список действительно большой
  • Они могут быть действительно громоздкими, когда критерии выбора предметов (в вашем случае, если имя [-5:] == 'Смит') более сложны или имеют несколько условий.

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

names = ['Jones', 'Vai', 'Smith', 'Perez', 'Smith']

toremove = []
for pos, name in enumerate(names):
    if name[-5:] == 'Smith':
        toremove.append(pos)
for pos in sorted(toremove, reverse=True):
    del(names[pos])

print names

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

1
10.10.2008 18:11:15
Это не работает должным образом, если у вас есть более одной записи «Смит», потому что дополнительные экземпляры для удаления были перемещены из-за удаления более ранних экземпляров. И по той же причине этот алгоритм вызывает исключение, если в конец списка добавляется вторая запись «Смит».
Miquella 8.10.2008 00:37:46
@Miquella: вы правы, мой оригинальный пост не удался для нескольких Smiths, я исправил это, делая удаление в обратном порядке. Спасибо.
Ricardo Reyes 10.10.2008 18:12:03

Есть моменты, когда фильтрация (с использованием фильтра или понимания списка) не работает. Это происходит, когда какой-то другой объект содержит ссылку на изменяемый список, и вам нужно изменить список на месте.

for name in names[:]:
    if name[-5:] == 'Smith':
        names.remove(name)

Единственное отличие от исходного кода - использование names[:]вместо namesцикла for. Таким образом, код перебирает (мелкую) копию списка, и удаления работают, как и ожидалось. Поскольку копирование списка мелкое, оно довольно быстрое.

4
5.10.2008 11:48:45

Чтобы ответить на ваш вопрос о работе со словарями, вы должны отметить, что Python 3.0 будет включать в себя dict-понимания :

>>> {i : chr(65+i) for i in range(4)}

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

>>> dict([(i, chr(65+i)) for i in range(4)])

Или как более прямой ответ:

dict([(key, name) for key, name in some_dictionary.iteritems if name[-5:] != 'Smith'])
2
8.10.2008 00:17:06
вам не нужно помещать ()выражения-генераторы, если они не являются единственным аргументом и []заставляют выражение-генератор материализовать список, что делает его dict([(k,v) for k,v in d.items()])намного медленнее, чемdict(((k,v) for k,v in d.items()))
Dan D. 4.03.2011 10:40:38

Вы также можете перебирать список по списку:

for name in reversed(names):
    if name[-5:] == 'Smith':
        names.remove(name)

Преимущество в том, что он не создает новый список (например, filterили понимание списка) и использует итератор вместо копии списка (например [:]).

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

37
8.10.2008 01:24:09
Это действительно инновационное и Pythonic решение. Я люблю это!
richo 7.12.2009 04:13:11
Работает ли это, если в списке есть дубликаты (которые соответствуют предикату)?
Jon-Eric 4.09.2012 16:58:06
@ Джон-Эрик: да, это работает. Если есть дубликат, то первый удаляется, список сжимается, и reversed()результаты совпадают nameво второй раз. Это алгоритм O (n ** 2) в отличие от принятого ответа, который использует алгоритм O (n).
jfs 23.05.2014 21:18:15

В случае набора.

toRemove = set([])  
for item in mySet:  
    if item is unwelcome:  
        toRemove.add(item)  
mySets = mySet - toRemove 
1
7.12.2009 04:08:57

Очевидный ответ - тот, который дал Джон и пара других людей, а именно:

>>> names = [name for name in names if name[-5:] != "Smith"]       # <-- slower

Но это имеет недостаток в том, что он создает новый объект списка, а не повторно использует исходный объект. Я провел некоторые профилирования и эксперименты, и самый эффективный метод, который я придумал:

>>> names[:] = (name for name in names if name[-5:] != "Smith")    # <-- faster

Присвоение «names [:]» в основном означает «заменить содержимое списка имен следующим значением». Он отличается от простого присвоения имен тем, что не создает новый объект списка. Правая часть назначения - это выражение генератора (обратите внимание на использование скобок, а не квадратных скобок). Это заставит Python перебирать весь список.

Некоторое быстрое профилирование предполагает, что это примерно на 30% быстрее, чем подход с использованием списков, и примерно на 40% быстрее, чем подход с фильтрами.

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

28
9.01.2011 14:41:40
Действительно интересное открытие производительности. Не могли бы вы рассказать о своей среде профилирования и методах оценки?
Drake Guan 2.03.2012 01:39:34
Могу поспорить, что вы могли бы сделать это еще быстрее, используя not name.endswith('Smith')вместо создания среза каждую итерацию. В любом случае, это ценная информация, которую я, вероятно, никогда не нашел, если бы не ваш ответ, спасибо.
notbad.jpeg 3.07.2014 01:27:44
это names[:]предложение было особенно полезно для использования с os.walkфильтром dirnames для обхода
wowest 18.06.2015 02:49:23

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

def filter_inplace(func, original_list):
  """ Filters the original_list in-place.

  Removes elements from the original_list for which func() returns False.

  Algrithm's computational complexity is O(N), where N is the size
  of the original_list.
  """

  # Compact the list in-place.
  new_list_size = 0
  for item in original_list:
    if func(item):
      original_list[new_list_size] = item
      new_list_size += 1

  # Remove trailing items from the list.
  tail_size = len(original_list) - new_list_size
  while tail_size:
    original_list.pop()
    tail_size -= 1


a = [1, 2, 3, 4, 5, 6, 7]

# Remove even numbers from a in-place.
filter_inplace(lambda x: x & 1, a)

# Prints [1, 3, 5, 7]
print a

Изменить: На самом деле, решение на https://stackoverflow.com/a/4639748/274937 превосходит решение шахты. Он более питоничен и работает быстрее. Итак, вот новая реализация filter_inplace ():

def filter_inplace(func, original_list):
  """ Filters the original_list inplace.

  Removes elements from the original_list for which function returns False.

  Algrithm's computational complexity is O(N), where N is the size
  of the original_list.
  """
  original_list[:] = [item for item in original_list if func(item)]
2
23.05.2017 11:54:44
удалить конечные элементы:del original_list[new_list_size:]
jfs 3.03.2013 06:23:45

Вот моя filter_inplaceреализация, которую можно использовать для фильтрации элементов из списка на месте, я придумал это самостоятельно, прежде чем найти эту страницу. Это тот же алгоритм, который опубликовал PabloG, только что он стал более универсальным, так что вы можете использовать его для фильтрации списков на месте, он также может быть удален из списка, comparisonFuncесли установлено обратное True; своего рода обратный фильтр, если хотите.

def filter_inplace(conditionFunc, list, reversed=False):
    index = 0
    while index < len(list):
        item = list[index]

        shouldRemove = not conditionFunc(item)
        if reversed: shouldRemove = not shouldRemove

        if shouldRemove:
            list.remove(item)
        else:
            index += 1
1
15.03.2013 14:12:56