我有几个项目 list 。没有重复,每个列表中的每个项目最多出现一次(通常在所有列表中只出现一次)。我还有一个要从此数据集中删除的项目列表。如何以最干净、最有效的方式完成?
我在 python 中读到过,创建一个新对象通常比过滤现有对象更简单、更快。但我没有在我的基本测试中观察到这一点:
data = [[i*j for j in range(1, 1000)] for i in range(1, 1000)]
kill = [1456, 1368, 2200, 36, 850, 9585, 59588, 60325, 9520, 9592, 210, 3]
# Method 1 : 0.1990 seconds
for j in kill:
for i in data:
if j in i:
i.remove(j)
# Method 2 : 0.1920 seconds
for i in data:
for j in kill:
if j in i:
i.remove(j)
# Method 3 : 0.2790 seconds
data = [[j for j in i if j not in kill] for i in data]
哪种方法最适合在 Python 中使用?
最佳答案
https://wiki.python.org/moin/TimeComplexityremove
是 O(n),因为它首先在列表中线性搜索,然后,如果找到它,则删除对象之后的每个元素在内存中向左移动一个位置。因为这个 remove
是一个相当昂贵的操作。
因此,从长度为 M
的列表中删除 N
项是 O(N*M)
列表上的 in
也是 O(n)
因为我们需要按顺序搜索整个列表。因此,使用过滤器构建新列表也是 O(N*M)
。然而,集合上的 in
是 O(1)
由于散列使我们的过滤器 O(N)
因此最好的解决方案是(为了简单起见,我将使用平面列表,而不是嵌套)
def remove_kill_from_data(data, kill):
s = set(kill)
return [i for i in data if i not in kill]
如果你不关心保持顺序,这会更快(由于是在 C 级别完成的,它仍然是
O(N)
)def remove_kill_from_data_unordered(data, kill):
s = set(kill)
d = set(data)
return d - s
应用于您的列表列表
kill_set = set(kill)
[remove_kill_from_data(d, kill_set) for d in data]
一些时间(每个先从静态
data
复制)%timeit method1(data, kill)
210 ms ± 769 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit method2(data, kill)
208 ms ± 2.89 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit method3(data, kill)
272 ms ± 1.28 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit method4(data, kill) # using remove_kill_from_data
69.6 ms ± 1.33 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit method5(data, kill) # using remove_kill_from_data_unordered
59.5 ms ± 3.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
关于python - 在python中删除多个列表中的多个项目的最有效方法?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/49696350/