Самый эффективный способ удалить несколько элементов в нескольких списках в Python?
У меня есть несколько списков предметов. Дубликатов нет, каждый элемент появляется не более одного раза в списке (и обычно только один раз во всех списках). У меня также есть список элементов, которые нужно удалить из этого набора данных. Как это сделать наиболее чистым и эффективным способом?
Я читал, что в python создание нового объекта часто проще и быстрее, чем фильтрация существующего. Но я не заметил этого в своих основных тестах:
data = [[i*j for j in range(1, 1000)] for i in range(1, 1000)]
kill = [1456, 1368, 2200, 36, 850, 9585, 59588, 60325, 9520, 9592, 210, 3]
# Method 1 : 0.1990 seconds
for j in kill:
for i in data:
if j in i:
i.remove(j)
# Method 2 : 0.1920 seconds
for i in data:
for j in kill:
if j in i:
i.remove(j)
# Method 3 : 0.2790 seconds
data = [[j for j in i if j not in kill] for i in data]
Какой метод лучше всего использовать в Python?
Первые два на самом деле не работают правильно, если (как в вашем примере) дублирование значений невозможно в data. Если дублирование значений находятся невозможно, вы должны просто использовать набор и пересекать его, что будет быстрее, короче и понятнее, чем любые другие версии.
И используйте timeit для синхронизации фрагментов кода
На самом деле, поскольку вы не повторяете копию data в обратном порядке, первые два неверны, даже дубликаты без: вы пропускаете значения len(kill) в data и никогда их не тестируете. Так что вы получите правильный ответ только в том случае, если никогда не бывает двух подряд убиваемых.
Ответы 1
https://wiki.python.org/moin/TimeComplexity
remove - это O (n), потому что он сначала выполняет линейный поиск по списку, а затем, если он его находит, каждый элемент после удаленного объекта сдвигается в памяти на одну позицию влево. Из-за этого remove - довольно дорогая операция.
Следовательно, удалите элементы M из списка длиной N, чтобы получить O(N*M)
in в списках также является O(n), потому что нам нужно просмотреть весь список по порядку. Следовательно, создание нового списка с фильтром также является O(N*M). Однако in на наборах - это O(1) из-за хеширования, что делает наш фильтр O(N)
Следовательно, лучшее решение (я просто буду использовать плоский список для простоты, а не вложенный)
def remove_kill_from_data(data, kill):
s = set(kill)
return [i for i in data if i not in kill]
Если вы не заботитесь о сохранении порядка, это будет еще быстрее (из-за того, что выполняется на уровне C, это все еще O(N))
def remove_kill_from_data_unordered(data, kill):
s = set(kill)
d = set(data)
return d - s
Применение к вашему списку списков
kill_set = set(kill)
[remove_kill_from_data(d, kill_set) for d in data]
Некоторые тайминги (сначала каждый копирует статический data)
%timeit method1(data, kill)
210 ms ± 769 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit method2(data, kill)
208 ms ± 2.89 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit method3(data, kill)
272 ms ± 1.28 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit method4(data, kill) # using remove_kill_from_data
69.6 ms ± 1.33 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit method5(data, kill) # using remove_kill_from_data_unordered
59.5 ms ± 3.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
remove по-прежнему будет линейным со связанными списками, потому что он должен искать элемент по значению, чтобы удалить его. (Это также означает, что in, за которым следует remove, делает примерно в два раза больше работы, чем index, за которым следует del, конечно.) Но на самом деле все это не имеет значения, потому что версия remove работает неправильно. Даже если бы это было быстрее, быстрее получить неправильный ответ не поможет.
@abarnert Это правда, в худшем случае (элемент находится в конце или его нет вообще) так же плохо, как и со списком массивов. Хотя в лучшем случае (элемент находится в начале) намного лучше. И да, но пример OPs имеет только уникальные записи. method5 также имеет эту проблему, поскольку он удаляет дубликаты.
Кроме того, вы должны продемонстрировать производительность и простоту, которых он добился бы, просто используя в первую очередь лучшую структуру данных (список наборов), если это соответствует его реальной проблеме.
Конечно, но лучший случай редко имеет значение, если у вас нет веских оснований полагать, что лучший вариант будет часто появляться. Средний случай остается линейным. Единственный способ обойти это - наложить сортировку, хешируемость или какое-либо другое ограничение и использовать структуру данных, которая использует это ограничение (например, набор).
Сделайте хотя бы
killнабором.