Python - 验证一个列表是否是另一个列表的子集

Question

我需要验证列表是否是另一个列表的一个子集 - 布尔返回是我寻求的全部内容.
在交叉路口之后测试相等的较小列表是最快的方法吗？
考虑到需要比较的数据集数量,性能至关重要.
根据讨论添加更多事实:

1. 对于许多测试,其中一个列表是否相同？
   它确实是其中一个是静态查找表
2. 它需要是一个列表吗？
   它没有 - 静态查找表可以是性能最佳的.
   动态的是一个dict,我们从中提取密钥以执行静态查找.

在这种情况下,最佳解决方案是什么？

Answer 1

>>> a = [1, 3, 5]
>>> b = [1, 3, 5, 8]
>>> c = [3, 5, 9]
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

>>> a = ['yes', 'no', 'hmm']
>>> b = ['yes', 'no', 'hmm', 'well']
>>> c = ['sorry', 'no', 'hmm']
>>> 
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

Answer 2

Python为此提供的性能函数是set.issubset.但它确实有一些限制,使得不清楚它是否是你问题的答案.

列表可以多次包含项目并具有特定顺序.一套没有.要实现高性能集,只能处理可清除对象.

您是在询问子集还是子序列(这意味着您需要字符串搜索算法)？对于许多测试,其中一个列表是否相同？列表中包含哪些数据类型？就此而言,它是否需要成为一个清单？

你的另一篇文章与dict和list相交,使得类型更清晰,并且确实建议使用字典键视图来实现类似集合的功能.在那种情况下,它是有用的,因为字典键的行为就像一个集合(以至于在我们使用Python之前我们使用字典之前).人们想知道这个问题在三小时内如何变得不那么具体.

Answer 3

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

all(x in two for x in one)

说明:生成器通过循环one检查列表是否在列表中来创建布尔值two. 如果每个项目都是真实的,则all()返回.TrueFalse

还有一个优点是all在缺少元素的第一个实例上返回False,而不是必须处理每个项目.

Answer 4

假设物品是可清洗的

>>> from collections import Counter
>>> not Counter([1, 2]) - Counter([1])
False
>>> not Counter([1, 2]) - Counter([1, 2])
True
>>> not Counter([1, 2, 2]) - Counter([1, 2])
False

如果你不关心重复的项目,例如.[1, 2, 2]并且[1, 2]然后只需使用:

>>> set([1, 2, 2]).issubset([1, 2])
True

在交叉路口之后测试相等的较小列表是最快的方法吗？

.issubset将是最快的方式.在测试之前检查长度issubset不会提高速度,因为您仍然需要迭代并检查O(N + M)个项目.

Answer 5

另一种解决方案是使用intersection。

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one).intersection(set(two)) == set(one)

集的交集将包含 set one

（要么）

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one) & (set(two)) == set(one)

Answer 6

集合论不适用于列表，因为使用集合论重复会导致错误的答案。

例如：

a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
set(b) > set(a)

没有任何意义。是的，它给出了一个错误的答案，但这并不正确，因为集合论只是比较：1,3,5 与 1,3,4,5。您必须包含所有重复项。

相反，您必须计算每个项目的每次出现并执行大于等于检查。这并不是很昂贵，因为它不使用 O(N^2) 操作并且不需要快速排序。

#!/usr/bin/env python

from collections import Counter

def containedInFirst(a, b):
  a_count = Counter(a)
  b_count = Counter(b)
  for key in b_count:
    if a_count.has_key(key) == False:
      return False
    if b_count[key] > a_count[key]:
      return False
  return True


a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

a = [1, 3, 3, 3, 4, 4, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

然后运行你会得到：

$ python contained.py 
b in a:  False
b in a:  True