从列表/队列中快速删除几个项目的方法

Question

这是对一个类似的问题的后续，该问题询问了编写最佳方式

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

看起来大家的共识是某种形式的

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

然而，如果你只是删除几个项目，大多数项目被复制到同一个对象中，可能会很慢。在另一个相关的question的answer中，有人建议：

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

然而，在这里，list.remove将搜索该项，其时间复杂度为O(N)，其中N是列表的长度。也许我们受限于该列表表示为数组，而不是链表，因此删除项目需要移动其后的所有内容。然而，建议在这里使用collections.dequeue来表示双向链表。然后在迭代时可以以O(1)的时间复杂度删除。我们应该如何实现这一点？

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

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

- highBandWidth

---

如果没有特定的性能目标，并且这不是您程序中唯一的瓶颈，那么在这方面过度纠结是毫无意义的。这些操作的“timeit”测量值是什么？ - S.Lott

我使用 timeit 重新测试了您的代码，而不是使用 cProfile。我能够复制您的结果。filter 是最快的。我需要深入挖掘并弄清楚为什么 cProfile 显示 filter 是最快的。我删除了我的答案，因为基于 cProfile vs. timeit 之间的差异只会增加未来知识寻求者的困惑 ;) 唯一可以确定的结论是 list.remove 很糟糕。 - Praveen Gollakota

如果你想要将苹果和苹果进行比较，你应该让列表推导式使用“c = ...”或让过滤器使用“c[:] = ...”。 - Daniel Stutzbach

@Daniel Stutzbach：c = [x for x in b if tokeep(x)]花费的时间相同，这很奇怪。 - jfs

我在 Python 3.4.1 中运行了相同的测试，得到了以下结果：列表推导式 = 3.207311153242804，过滤 = 0.0023201516740933847。 - nakedfanatic

@nakedfanatic：filter()在Python 3中返回一个迭代器。调用结果上的list()，以获取项目。 - jfs

Answer 1

列表推导式是渐近最优的解决方案：

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

它只对列表进行一次遍历，因此在O(n)时间内运行。由于您需要在每个对象上调用determine()，因此任何算法都需要至少O(n)个操作。列表推导式确实需要进行一些复制，但它只是复制对象的引用而不是对象本身。

从Python列表中删除项目的时间复杂度为O(n)，因此在循环内部有remove、pop或del的任何操作都将是O(n ** 2)。

此外，在CPython中，列表推导式比for循环更快。

- Daniel Stutzbach

---

你说得对，这是渐进最快的。我仍然想知道是否有一种方法可以消除复制的线性开销。 - highBandWidth

这句话的意思是，这个复制操作很适合缓存，并且非常快。你最好着手让 determine() 这个函数更快。 - Daniel Stutzbach

我对这段代码感到非常困惑...为什么不是：somelist = [x for x in somelist if not determine(x)] - Garrett Berg

@Garrett Berg：确实。somelist[:] = 触发 list_ass_slice() 执行了很多工作。 - jfs

有点烦人的是为什么默认的 remove 或 pop 没有这样实现。 - krenerd

@krenerd 默认的 remove 和 pop 会改变列表，而列表推导式则创建一个新的列表。 - Elias Hasle

Answer 2

由于list.remove等价于del list[list.index(x)]，因此您可以这样做：

for idx, item in enumerate(somelist):
    if determine(item):
        del somelist[idx]

但是：在迭代列表时，您不应该修改它。这迟早会伤害你。首先使用filter或列表推导式，然后再进行优化。

- Cat Plus Plus

---

这就是我提到的第二个代码片段所做的事情，使用reversed解决了安全问题。但是删除或del somelist[idx]仍然是O(N)，不是吗？ - highBandWidth

@highBandWidth：reversed并不能解决“安全性”问题。除了制作实际副本之外，没有任何方法可以解决这个问题。 - S.Lott

@S.Lott -- 是这样吗？我本以为这会确保所有的del副作用发生在已经遍历过的列表部分。(当然，仍然不应该那样做--它的规模扩展性很差。) - senderle

@senderle：（1）试一下。（2）尽量避免假设这种事情。测量比“本来以为”更有价值和有用。 - S.Lott

@S.Lott，我完全同意您的观点，所以我会重新表述一下：我之前尝试过它，似乎是有效的。也许有一个测试用例我错过了。 - senderle

Answer 3

一个双端队列被优化用于头和尾的移除，而不是在中间进行任意的移除。移除本身很快，但你仍然需要遍历列表到移除点。如果你正在迭代整个长度，那么使用filter或一个解释的唯一区别在于复制的开销，最坏情况下是常数倍数; 它仍然是O(n)操作。此外，请注意列表中的对象没有被复制 - 只有对它们的引用。所以这不是太大的负担。

可能可以像这样避免复制，但我没有特别的理由相信这比直接使用列表解析更快 - 它可能不是：

write_i = 0
for read_i in range(len(L)):
    L[write_i] = L[read_i]
    if L[read_i] not in ['a', 'c']:
         write_i += 1
del L[write_i:]

- senderle

Answer 4

如果你需要在O(1)时间内删除项目，可以使用HashMaps。

- Kevin

---

你说得对，我可能不得不退而求其次，但哈希表有些过度了，因为我不需要针对随机项进行O(1)删除，只需要在迭代该项时进行O(1)删除即可，这对于链表是可能的。 - highBandWidth

你能指向下一个项目吗？例如，如果你有像这样的东西：item1，item2，item3，并且你必须删除item2，你可以这样做：item1->next=item3。我希望现在我理解正确了。 - Kevin

Answer 5

我尝试解决这个问题。我的解决方案速度较慢，但需要更少的内存开销（即不创建新数组）。在某些情况下，它甚至可能更快！ 此代码自首次发布以来已经被编辑过 我在使用timeit时遇到了问题，可能我做错了什么。

import timeit
setup = """

import random
random.seed(1)
global b
setup_b = [(random.random(), random.random()) for i in xrange(1000)]
c = []
def tokeep(x):
        return (x[1]>.45) and (x[1]<.5)


# define and call to turn into psyco bytecode (if using psyco)
b = setup_b[:]
def listcomp():
   c[:] = [x for x in b if tokeep(x)]
listcomp()

b = setup_b[:]
def filt():
   c = filter(tokeep, b)
filt()

b = setup_b[:]
def forfilt():
   marked = (i for i, x in enumerate(b) if tokeep(x))
   shift = 0
   for n in marked:
      del b[n - shift]
      shift += 1
forfilt()

b = setup_b[:]
def forfiltCheating():
   marked = (i for i, x in enumerate(b) if (x[1] > .45) and (x[1] < .5))

   shift = 0
   for n in marked:
      del b[n - shift]
      shift += 1
forfiltCheating()

"""

listcomp = """
b = setup_b[:]

listcomp()
"""

filt = """
b = setup_b[:]

filt()
"""

forfilt = """
b = setup_b[:]

forfilt()
"""

forfiltCheating = '''
b = setup_b[:]

forfiltCheating()
'''

psycosetup = '''

import psyco
psyco.full()


'''

print "list comp = ", timeit.timeit(listcomp, setup, number = 10000)
print "filtering = ", timeit.timeit(filt, setup, number = 10000)
print 'forfilter = ', timeit.timeit(forfilt, setup, number = 10000)
print 'forfiltCheating = ', timeit.timeit(forfiltCheating, setup, number = 10000)


print '\nnow with psyco \n'
print "list comp = ", timeit.timeit(listcomp, psycosetup + setup, number = 10000)
print "filtering = ", timeit.timeit(filt, psycosetup + setup, number = 10000)
print 'forfilter = ', timeit.timeit(forfilt, psycosetup + setup, number = 10000)
print 'forfiltCheating = ', timeit.timeit(forfiltCheating, psycosetup + setup, number = 10000)

这里是结果

list comp =  6.56407690048
filtering =  5.64738512039
forfilter =  7.31555104256
forfiltCheating =  4.8994679451

now with psyco 

list comp =  8.0485959053
filtering =  7.79016900063
forfilter =  9.00477004051
forfiltCheating =  4.90830993652

我一定是在使用psyco时做错了什么，因为它实际上运行得更慢了。

- Garrett Berg

---

你正在执行设置步骤（创建b数组），并计时。我只计时实际的过滤/删除步骤。forfilter和forfiltCheating之间有什么区别？ - highBandWidth

哦，我明白了，在“作弊”中，您使用文字而不是函数对象，这似乎更快！ - highBandWidth

显然，timeit模块不会重新运行初始化步骤。由于我正在更改数组本身，因此必须将其包含在计时中。我以前从未使用过timit，我只是想获得一些结果。 - Garrett Berg

Answer 6

列表推导式不会复制元素

我花了一段时间才弄明白这个问题。请看下面的示例代码，尝试使用不同的方法进行实验。

代码

您可以指定列表元素复制所需的时间以及评估所需的时间。对于列表推导式来说，复制时间是无关紧要的，事实证明如此。

import time
import timeit
import numpy as np

def ObjectFactory(time_eval, time_copy):
    """
    Creates a class

    Parameters
    ----------
    time_eval : float
        time to evaluate (True or False, i.e. keep in list or not) an object
    time_copy : float
        time to (shallow-) copy an object. Used by list comprehension.

    Returns
    -------
    New class with defined copy-evaluate performance

    """
    class Object:

        def __init__(self, id_, keep):
            self.id_ = id_
            self._keep = keep

        def __repr__(self):
            return f"Object({self.id_}, {self.keep})"

        @property
        def keep(self):
            time.sleep(time_eval)
            return self._keep

        def __copy__(self):  # list comprehension does not copy the object
            time.sleep(time_copy)
            return self.__class__(self.id_, self._keep)

    return Object

def remove_items_from_list_list_comprehension(lst):
    return [el for el in lst if el.keep]

def remove_items_from_list_new_list(lst):
    new_list = []
    for el in lst:
        if el.keep:
            new_list += [el]
    return new_list

def remove_items_from_list_new_list_by_ind(lst):
    new_list_inds = []
    for ee in range(len(lst)):
        if lst[ee].keep:
            new_list_inds += [ee]
    return [lst[ee] for ee in new_list_inds]

def remove_items_from_list_del_elements(lst):
    """WARNING: Modifies lst"""
    new_list_inds = []
    for ee in range(len(lst)):
        if lst[ee].keep:
            new_list_inds += [ee]
    for ind in new_list_inds[::-1]:
        if not lst[ind].keep:
            del lst[ind]

if __name__ == "__main__":
    ClassSlowCopy = ObjectFactory(time_eval=0, time_copy=0.1)
    ClassSlowEval = ObjectFactory(time_eval=1e-8, time_copy=0)

    keep_ratio = .8
    n_runs_timeit = int(1e2)
    n_elements_list = int(1e2)

    lsts_to_tests = dict(
        list_slow_copy_remove_many = [ClassSlowCopy(ii, np.random.rand() > keep_ratio) for ii in range(n_elements_list)],
        list_slow_copy_keep_many = [ClassSlowCopy(ii, np.random.rand() > keep_ratio) for ii in range(n_elements_list)],
        list_slow_eval_remove_many = [ClassSlowEval(ii, np.random.rand() > keep_ratio) for ii in range(n_elements_list)],
        list_slow_eval_keep_many = [ClassSlowEval(ii, np.random.rand() > keep_ratio) for ii in range(n_elements_list)],
    )

    for lbl, lst in lsts_to_tests.items():
        print()
        for fct in [
            remove_items_from_list_list_comprehension,
            remove_items_from_list_new_list,
            remove_items_from_list_new_list_by_ind,
            remove_items_from_list_del_elements,
        ]:

            lst_loc = lst.copy()
            t = timeit.timeit(lambda: fct(lst_loc), number=n_runs_timeit)
            print(f"{fct.__name__}, {lbl}: {t=}")

输出

remove_items_from_list_list_comprehension, list_slow_copy_remove_many: t=0.0064229519994114526
remove_items_from_list_new_list, list_slow_copy_remove_many: t=0.006507338999654166
remove_items_from_list_new_list_by_ind, list_slow_copy_remove_many: t=0.006562008995388169
remove_items_from_list_del_elements, list_slow_copy_remove_many: t=0.0076057760015828535

remove_items_from_list_list_comprehension, list_slow_copy_keep_many: t=0.006243691001145635
remove_items_from_list_new_list, list_slow_copy_keep_many: t=0.007145451003452763
remove_items_from_list_new_list_by_ind, list_slow_copy_keep_many: t=0.007032064997474663
remove_items_from_list_del_elements, list_slow_copy_keep_many: t=0.007690364996960852

remove_items_from_list_list_comprehension, list_slow_eval_remove_many: t=1.2495998149970546
remove_items_from_list_new_list, list_slow_eval_remove_many: t=1.1657221479981672
remove_items_from_list_new_list_by_ind, list_slow_eval_remove_many: t=1.2621939050004585
remove_items_from_list_del_elements, list_slow_eval_remove_many: t=1.4632593330024974

remove_items_from_list_list_comprehension, list_slow_eval_keep_many: t=1.1344162709938246
remove_items_from_list_new_list, list_slow_eval_keep_many: t=1.1323430630000075
remove_items_from_list_new_list_by_ind, list_slow_eval_keep_many: t=1.1354237199993804
remove_items_from_list_del_elements, list_slow_eval_keep_many: t=1.3084568729973398

- Markus Dutschke

Answer 7

 import collections
 list1=collections.deque(list1)
 for i in list2:
   try:
     list1.remove(i)
   except:
     pass

不要检查元素是否存在，使用 try except。我想这样更快。

- Prabhas