python - 如何快速比较列表和集合？

Question

假设我有一个列表

l = [1, 1 , 1, 2, 3, 4, 5, 5]

和两个等长的不相交集合

a = (1, 3)和 b = (2, 5)

我想获取 l 中的元素那是在a和 b分别点赞

[1, 1, 1, 3]和 [2, 5, 5]

我尝试了像 [x for x in l if x in a] 这样的列表理解但是如果 l 的长度需要很长时间, a , 和 b是 10^5

编辑:集合是等长的不相交集合。

编辑:我需要做的是计算 l 中的元素这在 a 中很常见(重复)减去 l 的元素在b (也有重复项)。所以上面的例子应该输出1 .问题是列表和集合是否与 10E5 一样长。使用过滤器和 itertools 仍然需要很长时间。

编辑:我现在明白了!显然我必须用 set() 包装输入集!一开始我不知道(我只是通过 input().split() 得到的)因为输入已经是唯一的但不知道列表和集合非常不同并且集合更快!好吧，直到我。

Answer 1

根本问题是您没有为工作使用适当的数据结构。 在这种情况下，使用元组表示集合对于小集合可能ok， 但是对于 large 集，您可以期望搜索平均数 列表中每个元素的集合组合大小的一半 那实际上是在其中一个集合中。 对于列表中不在任一集合中的每个元素， 我们必须搜索 两个 集合的所有 元素来确定。

所以任何基于这些数据结构的算法 (即，使用元组表示集合) 最多为 O(m*n)，其中 m 是列表的大小 n 是集合的大小。

我们确实没有任何方法可以减少 m 组件 — 我们必须检查列表的每个元素以确定哪个集合 (如果有的话)它属于。

但是，我们可以减少 n 组件。 如何？通过为我们的集合使用更高效的数据结构。

幸运的是，这并不难，因为 Python 包含一个内置的 set 类型。 所以第一步是构建两个集合:

a = set((1, 3))
b = set((2, 5))

现在，我们可以轻松(高效)确定元素 e 是否在其中一个集合中:

e = 1
e in a # => True
e in b # => False

现在，我们只需要遍历输入列表并累积结果:

l = [1, 1, 3, 2, 5, 7, 8, 3, 2, 1]
result = 0 # accumulator for result
for e in l:
  if e in a:
    result += 1
  elif e in b:
    result -= 1

print result # prints "2"