python - 快速字典查找

Question

我正在编写一些 python 代码，其中我必须检查 list2 中的所有值是否都存在于 list1 中，我这样做了通过使用 set(list2).difference(list1) 但是该函数对于列表中的许多项目来说太慢了。

所以我在想 list1 可以是一个用于快速查找的字典...

所以我想找到一种快速的方法来阻止列表中是否有不属于字典的项目

性能方面有什么区别

d = {1: 1, 2:2, 3:3}
l = [3, 4, 5]

for n in l:
  if not n in d:
    do_stuff

对比

for n in l:
  if not d[n]:
    do_stuff

如果这两个都是垃圾，请告诉我。

Edit1:list1 或 d 可以包含不在 list2 中的元素，反之则不行。

Answer 1

使用 all 和生成器推导式可以快速实现您想要的效果。

s_list2 = set(list2)
all_present = all(l in s_list2 for l in list1)

这在 list1 的某些元素不存在于 list2 中的情况下将是有利的。

一些时机。如果第一个列表中的所有值都包含在第二个列表中:

In [4]: l1 = range(100)
In [5]: l2 = range(1000)
In [6]: random.shuffle(l1)
In [9]: random.shuffle(l2)
In [20]: %timeit s2 = set(l2); all(l in s2 for l in l1)
10000 loops, best of 3: 26.4 us per loop
In [21]: %timeit s1 = set(l1); s2 = set(l2); s1.issubset(s2)
10000 loops, best of 3: 25.3 us per loop

如果我们观察第一个列表中的某些值不出现在第二个列表中的情况:

In [2]: l1 = range(1000)
In [3]: l2 = range(100)
In [4]: random.shuffle(l1)
In [5]: random.shuffle(l2)
In [6]: sl2 = set(l2)
In [8]: %timeit ss = set(l2); set(l1) & ss == ss
10000 loops, best of 3: 27.8 us per loop
In [10]: %timeit s1 = set(l1); s2 = set(l2); s2.issubset(s1)
10000 loops, best of 3: 24.7 us per loop
In [11]: %timeit sl2 = set(l2); all(l in sl2 for l in l1)
100000 loops, best of 3: 3.58 us per loop

您可以看到，此方法在第一种情况下在性能上等同于 issubset，而在第二种情况下更快，因为它会短路并避免构造 2 个中间集(仅需要一个)。

有一个大列表和一个小列表证明了 gencomp 方法的好处:

In [7]: l1 = range(10)
In [8]: l2 = range(10000)
In [9]: %timeit sl2 = set(l2); all(l in sl2 for l in l1)
1000 loops, best of 3: 230 us per loop
In [10]: %timeit sl1 = set(l1); all(l in sl1 for l in l2)
1000000 loops, best of 3: 1.45 us per loop
In [11]: %timeit s1 = set(l1); s2 = set(l2); s1.issubset(s2)
1000 loops, best of 3: 228 us per loop
In [12]: %timeit s1 = set(l1); s2 = set(l2); s2.issubset(s1)
1000 loops, best of 3: 228 us per loop