我有几个项目 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/TimeComplexity
remove 是 O(n),因为它首先在列表中线性搜索,然后,如果找到它,则删除对象之后的每个元素在内存中向左移动一个位置。因为这个 remove 是一个相当昂贵的操作。

因此,从长度为 M 的列表中删除 N 项是 O(N*M)
列表上的 in 也是 O(n) 因为我们需要按顺序搜索整个列表。因此,使用过滤器构建新列表也是 O(N*M) 。然而,集合上的 inO(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/

10-11 23:13
查看更多