Элегантный способ удаления элементов из последовательности в 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

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

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

Ответ 1

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

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

names = filter(lambda name: name[-5:] != "Smith", names)
Использование списков:

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

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

Изменить Смешно... два человека индивидуально отправили оба ответа, которые я предлагал, когда я отправлял мои сообщения.

Ответ 2

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

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

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

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

Ответ 3

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

>>> 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 * и использовал его для удаления точек поиска из луча поиска.)

Ответ 4

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

list = [x for x in list if x[-5:] != "smith"]

Ответ 5

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

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

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

Ответ 6

Фильтр

был бы потрясающим для этого. Простой пример:

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

Изменить: Корическое понимание списка также удивительно.

Ответ 7

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

Ответ 8

Оба решения, фильтр и понимание требуют создания нового списка. Я не знаю достаточного количества внутренних компонентов 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

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

Ответ 9

Чтобы ответить на вопрос о работе со словарями, вы должны заметить, что 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'])

Ответ 10

Если список должен быть отфильтрован на месте, а размер списка довольно велик, то алгоритмы, упомянутые в предыдущих ответах, которые основаны на 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 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

Изменить: На самом деле решение в fooobar.com/questions/107029/... превосходит мое решение. Он более питонов и работает быстрее. Итак, вот новая реализация 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 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)]

Ответ 11

В вашем примере понимаются фильтры и списки, но у них есть несколько проблем:

Они делают копию вашего списка и возвращают новый, и это будет неэффективно, если исходный список действительно большой.
Они могут быть очень громоздкими, когда критерии выбора элементов (в вашем случае, если имя [-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

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

Ответ 12

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

toRemove = set([])  
for item in mySet:  
    if item is unwelcome:  
        toRemove.add(item)  
mySets = mySet - toRemove

Ответ 13

Вот моя реализация 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

Ответ 14

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

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

edit: кто-то понимает, что он попросил "эффективности"... все эти предложенные методы просто перебирают список, что то же, что и он предложил.