从列表/队列中删除一些项目的快速方法 [英] Fast way to remove a few items from a list/queue

问题描述

这是类似的

This is a follow up to a similar question which asked the best way to write

for item in somelist:
    if determine(item):
         code_to_remove_item

似乎达成了共识，例如

somelist[:] = [x for x in somelist if not determine(x)]

但是，我认为如果您仅删除一些项目，则大多数项目都将被复制到同一对象中，这可能很慢.在 answer 中找到另一个相关问题，有人建议:

However, I think if you are only removing a few items, most of the items are being copied into the same object, and perhaps that is slow. In an answer to another related question, someone suggests:

for item in reversed(somelist):
    if determine(item):
        somelist.remove(item)

但是，这里的list.remove将搜索列表长度为O(N)的项目.可能我们的局限在于列表以数组而不是链接列表的形式表示，因此删除项目将需要移动列表后的所有内容.但是，建议此处，将collections.dequeue表示为双向链表.然后应该可以在迭代时删除O(1).我们实际上将如何完成?

However, here the list.remove will search for the item, which is O(N) in the length of the list. May be we are limited in that the list is represented as an array, rather than a linked list, so removing items will need to move everything after it. However, it is suggested here that collections.dequeue is represented as a doubly linked list. It should then be possible to remove in O(1) while iterating. How would we actually accomplish this?

更新: 我还使用以下代码进行了一些时间测试:

Update: I did some time testing as well, with the following code:

import timeit
setup = """
import random
random.seed(1)
b = [(random.random(),random.random()) for i in xrange(1000)]
c = []
def tokeep(x):
        return (x[1]>.45) and (x[1]<.5)
"""
listcomp = """
c[:] = [x for x in b if tokeep(x)]
"""
filt = """
c = filter(tokeep, b)
"""
print "list comp = ", timeit.timeit(listcomp,setup, number = 10000)
print "filtering = ", timeit.timeit(filt,setup, number = 10000)

并得到:

list comp =  4.01255393028
filtering =  3.59962391853

推荐答案

列表理解是渐近最优的解决方案:

The list comprehension is the asymptotically optimal solution:

somelist = [x for x in somelist if not determine(x)]

它仅使列表通过一遍，因此运行时间为O(n).由于您需要在每个对象上调用define()，因此任何算法都至少需要O(n)个操作.列表理解确实需要进行一些复制，但是它只是复制对对象的引用，而不是复制对象本身.

It only makes one pass over the list, so runs in O(n) time. Since you need to call determine() on each object, any algorithm will require at least O(n) operations. The list comprehension does have to do some copying, but it's only copying references to the objects not copying the objects themselves.

在Python中从列表中删除项目为O(n)，因此在循环内具有remove，pop或del的所有内容均为O(n ** 2).

Removing items from a list in Python is O(n), so anything with a remove, pop, or del inside the loop will be O(n**2).

此外，在CPython列表中，理解要比for循环快.

Also, in CPython list comprehensions are faster than for loops.

这篇关于从列表/队列中删除一些项目的快速方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！