从非常大的列表中删除子列表的高效算法或python的内置函数

Question

我想从包含大约100000个网络地址作为元素的列表中删除子列表（20000-80000个元素）。我正在用python创建我的程序。你知道吗

我知道有两种方法：

1. python的过滤方法：

   newl = [x for x in list if x not in sublist]
   

2. 简单嵌套for循环

但是，在我的案例中，两者都需要花费大量的时间来处理。 我需要有效的方法来解决这个问题，它可以给出快速的结果。 如果有人有任何想法或面临这种问题，请分享。谢谢。你知道吗

Answer 1

当您执行x in list操作时，它是O(n)操作。但是如果您执行x in set操作，那就是O(1)操作，因为集合在内部维护哈希。所以最好的方法就是比较不同的选择。你知道吗

from random import shuffle, sample
list = range(100000)
shuffle(list)
sublist = sample(list, 20000)
set_sublist = set(sublist)

使用列表进行包含检查的列表理解

列表上的顺序将保留，但列表的包含检查速度较慢。你知道吗

%time newl = [x for x in list if x not in sublist]
CPU times: user 40.8 s, sys: 146 ms, total: 41 s
Wall time: 41.7 s

设置差异

快速，但列表上的顺序不保留。你知道吗

%time news = set(list) - set(sublist)
CPU times: user 16.2 ms, sys: 44 µs, total: 16.3 ms
Wall time: 16.3 ms

使用集合进行包含检查的列表理解

这只比上面的set difference方法稍微慢一点，但是列表的顺序保持不变，并且与当前方法相比执行速度仍然非常快。你知道吗

%time newl = [x for x in list if x not in set_sublist]
CPU times: user 42.3 ms, sys: 2.95 ms, total: 45.3 ms
Wall time: 44.8 ms