1

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

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

所以我想找到一种快速的方法来阻止列表是否包含不属于 dict 的项目

性能方面有什么区别

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 中的元素，但反之则不行。

4

3 回答 3

3

实现您想要的东西的快速方法将是使用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
于 2013-01-21T17:29:23.563 回答
2

您可以将列表转换为集合，然后使用该方法issubset()检查一个是否是另一个集合的子集。

In [78]: import random

In [79]: lis2=range(100)

In [80]: random.shuffle(lis2)

In [81]: lis1=range(1000)

In [82]: random.shuffle(lis1)

In [83]: s1=set(lis1)

In [84]: all(l in s1 for l in lis2)
Out[84]: True

In [85]: %timeit all(l in s1 for l in lis2)
10000 loops, best of 3: 28.6 us per loop

In [86]: %timeit s2=set(lis2);s2.issubset(s1)
100000 loops, best of 3: 12 us per loop

In [87]: s2.issubset(s1)
Out[87]: True
于 2013-01-21T17:29:39.423 回答
1

对两个列表进行排序然后一起遍历它们是 O(n log n)。IE：

l1.sort()
l2.sort()

j = 0
for i in range(0,len(l1)):
  while ((j < len(l2)) and (l1[i] == l2[j])):
    j = j+1
  if (j == len(l2)):
    break
  if (l1[i] > l2[j]):
    break

if (j == len(l2)): # all of l2 in l1

现在就时间复杂度而言，就像我说的那样，这是 O(n log n) 因为排序（第二个循环小于 O(n) 处的那个）。然而，它在 python 中可能不会比内置的集合操作更快。你必须尝试一下。

[顺便说一句，如果我考虑一下，可能是一种更pythony的方式来完成最后一段理解]

于 2013-01-21T21:31:02.967 回答