高效算法或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进行包含检查的列表理解

这仅比上面的设置差异方法略慢,但是与当前方法相比,列表的顺序得以保留并且仍然执行得非常快.

%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