Производительность Python: удалить элемент из списка

Пробовал некоторые bogo-бенчмарки в IPython.

import random
# Don't know how to generate your words, use integers as substitute.
words = [random.randint(0, 25) for i in xrange(370000)]
badlist = range(7)
badtuple = tuple(badlist)
badset = set(badlist)
# List comprehension
%timeit [w for w in words if w not in badlist]
10 loops, best of 3: 59.2 ms per loop
%timeit [w for w in words if w not in badtuple]
10 loops, best of 3: 64.7 ms per loop
%timeit [w for w in words if w not in badset]
10 loops, best of 3: 30.3 ms per loop
# Filter
%timeit filter(lambda w: w not in badlist, words)
10 loops, best of 3: 85.6 ms per loop
%timeit filter(lambda w: w not in badtuple, words)
10 loops, best of 3: 92.1 ms per loop
%timeit filter(lambda w: w not in badset, words)
10 loops, best of 3: 50.8 ms per loop

Вывод: Возможно, лучше всего использовать понимание списка с not in <set> в качестве условия фильтра.

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

Некоторая идея о том, почему понимание списка + «не в наборе», вероятно, является оптимальным.

1. filter против понимания списка: filter на самом деле вызывает callable-вызов, а callable-вызов в Python имеет свои собственные накладные расходы (создание фрейма стека и т. д.). Кроме того, filter пытается быть умным и возвращает правильный тип, что увеличивает накладные расходы. (на самом деле это ничтожно мало). Вместо этого проверка условия включения в список (предложение if ...) имеет меньшие накладные расходы, чем вызов. Это просто вычисление выражений без всех наворотов стека вызовов Python.
2. Тест на членство в наборе - O (1) в среднем и O (n) в худшем случае, но членство в списке / кортеже всегда O (n).

Вы можете использовать понимание списка, что-то вроде:

words = [word for word in words if word not in ["a", "y", "Y", "q", "Q", "p", "P", "uh"]]

понимание списка дает намного лучшую производительность.

Изменить (благодаря результатам Конг Ма):

Похоже, что наилучшая производительность достигается при использовании set в качестве последовательности фильтров, поэтому вам нужно что-то вроде:

words = [word for word in words if word not in set(("a", "y", "Y", "q", "Q", "P", "uh"))]

«но время от времени я получаю эти отдельные символы».

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

Я столкнулся с той же проблемой, сначала мое решение использует pypy

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

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

bad_list = ["a", "y", "Y", "q", "Q", "p", "P", "uh"]

# here is the generator "comprehension"
good_word_stream = (word for word in open("lexicon") if word not in bad_list)

# ... and use the output for something
print [len(word) for word in good_word_stream]

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

Что касается производительности, list.remove - это операция O (n), поэтому ваш код - O (N ^ 2).

Понимание списков происходит намного быстрее, так как занимает больше места — создайте новый список/или генератор в Python 3, используйте небольшой черный список для фильтрации окончательных результатов. Хотя я не уверен, будет ли он создавать ["a", "y", "Y", "q", "Q", "p", "P", "uh"] каждый раз, в удаленном ответе Конг Ма упоминалось о создании этого небольшого набора (да, набор, a in set() - это операция O (1)!), Что может быть полезно для производительности.

И понимание списка примерно на 25% медленнее, чем map или list(map(something)) в моем предыдущем тесте, я не могу доказать это прямо сейчас, но вы, возможно, захотите пройти тест.

Pypy/Cython был бы окончательным решением, если бы все, что вы можете сделать в Python, было сделано, а производительность все еще не соответствовала производственным требованиям.