Удалить элемент по значению в списке Python быстрее всего
как быстрее всего удалить элемент из списка по его значению?
Я считаю, что list.remove("element_to_be_removed") это наивный способ. Как мы можем его оптимизировать?
Я сомневаюсь, что есть способ сделать это в какой-либо значительной степени. По своей природе списки, идентифицирующие элемент в списке, имеют значение O(n), и вы действительно не сможете обойти это.
могу ли я сначала преобразовать свой список в набор, а затем выполнить удаление из этого набора, чтобы ускорить удаление? P.S. Я знаю, что в моем списке будут/должны быть только уникальные записи, поэтому преобразование в набор не будет проблемой. @Сэмуайз
Ответы 2
Поиск элемента в списке по значению — это O(n), как и его удаление после того, как вы его нашли. Нет никакого способа уменьшить это; это присуще тому, как строятся списки.
Поиск и/или удаление элемента в наборе — O(1).
Преобразование списка в набор — O(n). Если у вас есть список и вам нужно удалить один элемент, преобразование его в набор, а затем удаление одного элемента не приведет вас к O (1), потому что само преобразование множества является операцией O (n). Лучше использовать list.remove().
Если у вас есть список уникальных элементов, и вы ожидаете, что вам нужно будет удалить из него множество элементов неупорядоченным образом (скажем, вы собираетесь в конечном итоге удалить каждый элемент один за другим), вы можете изменить это с O(n^ 2) операция до операции O (n) путем преобразования всего списка в набор (один раз, за O (n)) и последующего удаления элементов один за другим после этого (за O (1) на элемент, следовательно, O (n ) общий).
Идеальное решение (если возможно) состоит в том, чтобы заранее предусмотреть способы использования этой коллекции элементов и сделать ее набором с самого начала, если функциональность набора лучше подходит для того, что вы делаете.
Также, используя понимание списка, мы можем удалить элемент за O(n).
Не совсем так — вы можете использовать понимание списка, чтобы создать новый список, исключающий элемент, который вы хотите удалить. Изменение существующего списка для соответствия новому списку - еще один шаг (но это также O (n), поэтому это не меняет общее время большого O).
Список неупорядочен, поэтому поиск элемента по его значению должен выполняться путем полного перебора (в лучшем случае O (1), в худшем случае O (n)).
Удаление также требует O(n) операций, но, точнее, требует количества сдвигов, равного количеству элементов, следующих за удаляемым. (Плюс случайное деление пополам, когда список сильно сокращается). Таким образом, у нас есть худший случай O (n), лучший O (1), симметрично с поиском.
Таким образом, если вы выполняете поиск ключа в обратном направлении, лучшим случаем удаления будет O(1) вместо O(n), хотя в среднем это не имеет абсолютно никакого значения.
Последняя подсказка: если у вас есть основания полагать, что удаления происходят чаще на одной стороне, чем на другой, вам лучше организовать свой список так, чтобы эта сторона была справа (при необходимости сохранить назад) и выполнить поиск в обратном направлении.
Способ оптимизации заключается в том, чтобы не использовать список, а использовать набор, словарь или что-то еще, что позволяет выполнять поиск и удаление за O(1).