时间戳

首页 > 解决方案 > 有没有更快的方法从 Python 3 中的列表中删除成员？

python-3.x - 有没有更快的方法从 Python 3 中的列表中删除成员？

问题描述

我有一个定义为类的对象列表，例如：

class Foo:
    def __init__(self,value):
        self.v = value

我的列表包含大约 1e6 个这些对象，我经常在这样的 while 循环中删除其中一些：

from random import randrange

#Number of elements
N = 1000000

# Let's construct the list

Foos_list = []

for i in range(N):
    Foos_list.append(Foo(i))

# Now let's remove members one by one

while len(Foos_list) > 0:
    i_random = randrange(N)
    Foos_list.remove(Foos_list[i_random])

我使用随机生成器来选择在每次迭代中应该删除哪个元素，因为在我的真实情况下，我对成员的访问有些随机或稀疏Foos_list，我不确定这是否对我看到的缓慢有任何贡献。事实上，上面的代码可以正常工作，N ~ 200000但之后它变得很慢。与相比，有没有更好的方法可以更有效地从类对象列表中删除元素remove？

标签： python-3.x

解决方案

list.remove(list[i])是多余的，因为list.remove()需要在列表中搜索list[i]（这是 O(n)），但当然，它在i. 改为使用del。

while foos_list:
    i_random = randrange(len(foos_list))
    del foos_list[i_random]

现在，del仍然是 O(n)，所以你不会看到巨大的速度提升，但它至少应该有所帮助——比 O(2n) 更好。

顺便说一句，我做了三个修复：

  1. 避免使用 Upper_snake_case变量名。使用snake_case代替简单变量。
  2. 使用if list代替if len(list) > 0
  3. 在某些时候，i_random会大于len(foos_list)因为N大于len(foos_list)第一次迭代之后。

为了进一步加快速度，我们需要更多的上下文。例如，也许您可​​以先对列表进行洗牌，然后.pop()在每次迭代时简单地洗牌，但这取决于您对列表所做的事情。

推荐阅读