英文:
remove element by value in list Python fastest
问题
The fastest way to remove an element from a list by its value is by using the list.remove("element_to_be_removed") method. To optimize it, you can consider using list comprehensions or the filter function in Python.
英文:
what is the fastest way to remove an element from a list by its value?
I believe list.remove("element_to_be_removed") is the naive way. How can we optimize it?
答案1
得分: 4
在列表中按值查找元素的时间复杂度为O(n)，一旦找到它，删除它的时间复杂度也是O(n)。这是无法减少的，因为它与列表的构建方式有关。
在集合中查找和/或删除元素的时间复杂度为O(1)。
将列表转换为集合的时间复杂度为O(n)。如果你有一个列表，并且需要删除一个项目，将其转换为集合，然后再删除一个项目并不能使时间复杂度达到O(1)，因为集合转换本身是一个O(n)的操作。你最好使用list.remove()。
如果你有一个包含唯一项的列表，并且预计以无序方式需要从中删除多个项（例如，最终要逐个删除每个项），你可以通过将整个列表转换为集合（一次，时间复杂度为O(n)）然后之后逐个删除元素（每个项的时间复杂度为O(1)，因此总体时间复杂度为O(n)）将其从O(n^2)的操作变为O(n)的操作。
理想的解决方案（如果可能的话）是预期你将如何使用这个项目集合，并从一开始就将其创建为集合，如果集合的功能更适合你要做的事情的话。
英文:
Finding an element in a list by value is O(n), as is removing it once you have found it. There is no way to reduce this; it's inherent in how lists are built.
Finding and/or removing an element in a set is O(1).
Converting a list into a set is O(n). If you have a list and you need to remove one item, converting it to a set and then removing one item doesn't get you to O(1), because the set conversion itself is an O(n) operation. You're better off using list.remove().
If you have a list of unique items, and you anticipate needing to remove many items from it in an unordered way (say, you're going to eventually remove each item one by one), you can change that from an O(n^2) operation to an O(n) operation by converting the entire list into a set (once, in O(n)) and then removing the elements one by one after that (in O(1) per item, hence O(n) overall).
The ideal solution (if possible) is to anticipate the ways in which you'll need to use this collection of items and make it a set from the beginning if the functionality of a set is a better fit for what you're doing.
答案2
得分: 0
A list is unordered, so finding an element by its value must be done by exhaustive search (best case O(1), worst O(n)).
删除也需要O(n)的操作，但更精确地说，它需要与删除元素后面的元素数量相等的移动次数（加上列表缩小时的偶发减半）。因此，最坏情况是O(n)，最好情况是O(1)，与搜索相对称。
因此，如果你反向搜索键，删除的最佳情况是O(1)，而不是O(n)，尽管平均情况下这没有任何区别。
最后的提示：如果你有理由相信删除更频繁发生在一侧而不是另一侧，最好将列表组织成使该侧位于右侧（如果需要，进行反向存储），然后进行反向搜索。
英文:
A list is unordered, so finding an element by its value must be done by exhaustive search (best case O(1), worst O(n)).
Deletion also takes O(n) operations, but more precisely, it takes the number of shifts equal to the number of elements that follow the deleted one. (Plus occasional halving when the list shrinks a lot). So we have worst case O(n), best O(1), symmetrically with the search.
So if you perform the search for the key backward, the best case of removal is O(1) instead of O(n), though on average this makes absolutely no difference.
Last hint: if you have some reason to believe that the removals occur more often on a side than on the other, you'd better organize your list so that this side comes to the right (store backward if needed) and perform backward searches.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论