在python中删除多个列表中的几个项目的最有效方法？

Question

我有几个项目列表.没有重复项,每个项目最多出现一次(通常,在所有列表中只出现一次).我还有一个要从此数据集中删除的项目列表.如何以最干净,最有效的方式完成？

我已经读过,在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中使用？

Answer 1

https://wiki.python.org/moin/TimeComplexity

remove是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)