在Python中取任意数量列表的交集

Question

假设我有一个元素都相同的列表列表（在这个例子中，我将使用 int ）

[range(100)[::4], range(100)[::3], range(100)[::2], range(100)[::1]]

什么是取这些列表的交集的好方法或有效的方式（这样您将获得每个列表中都存在的元素）？对于该示例，结果应为：

[0, 12, 24, 36, 48, 60, 72, 84, 96]

- thepandaatemyface

Answer 1

使用集合，它们具有交集方法。

>>> s = set()
>>> s.add(4)
>>> s.add(5)
>>> s
set([4, 5])
>>> t = set([2, 4, 9])
>>> s.intersection(t)
set([4])

例如，对于您的示例，请使用以下内容：

>>> data = [range(100)[::4], range(100)[::3], range(100)[::2], range(100)[::1]]
>>> sets = map(set, data)
>>> print set.intersection(*sets)
set([0, 96, 36, 72, 12, 48, 84, 24, 60])

- Mike Graham

---

我会将这个答案标记为最佳答案，因为它比我的答案快一点（而我的答案又比使用reduce的答案快两倍），并且因为同时使用多个集合的好处。谢谢！ - thepandaatemyface

另外，set.intersection(set(x) for x in data)。 - David Z

@thepandaatemyface，我总是很高兴听到我的代码表现良好，但也总有点怀疑。我相信这在很大程度上取决于输入，如果输入的大小是问题，你可能没有时间在真正巨大的输入上运行它。如果我试图在大数据的内部循环中优化速度，我会考虑尝试set(datas[0]).intersection(*datas[1:])并计时，这对我来说具有很好的性能优势。 - Mike Graham

@Mike Graham，我的意思是：在这里发布的所有优雅解决方案中，你的是最快的。我用[[randint(0, 100000) for i in range(1000)] for i in range(100)]作为我的数据进行了快速测试。虽然不太科学，但似乎一直都是你的最快。 - thepandaatemyface

@David，你缺少一个*(...)来将生成器的项应用为参数。除此之外，这绝对是一个不错的方法。我没有使用它的主要原因是强调如果你正在执行像交集这样的操作，你可能已经有了集合。 - Mike Graham

@thepandaatemyface，太棒了。=） - Mike Graham

Answer 2

我认为内置的set模块应该能够解决问题。

>>> elements = [range(100)[::4], range(100)[::3], range(100)[::2], range(100)[::1]]
>>> sets = map(set, elements)
>>> result = list(reduce(lambda x, y: x & y, sets))
>>> print result
[0, 96, 36, 72, 12, 48, 84, 24, 60]

- dwlz

---

你比我更快地完成了。我会保留我的答案，因为它对reduce的应用略有不同，但我很高兴看到其他人也在思考函数式编程。 :-) - Samir Talwar

太多学校直接跳过必修的函数式编程入门课程，转而直接学习Java，我认为这是不可取的。大家，SCIP是最好的计算机科学入门书籍之一... - Paul McMillan

请注意，set是一种类型，而不是一个模块。（set类型曾经在名为sets的模块中，但它已经被废弃很久了。） - Mike Graham

虽然这个解决方案非常优雅且运行良好，但似乎比不使用reduce的解决方案慢了两倍。有人有任何想法吗？ - thepandaatemyface

可能是因为需要构建更多的中间集合。 - Mike Graham

Answer 3

将它们转换为集合并使用set.intersection方法，针对集合列表进行缩减:

xs = [range(100)[::4], range(100)[::3], range(100)[::2], range(100)[::1]]
reduce(set.intersection, [set(x) for x in xs])

reduce是一种函数式编程设备，它遍历任何可迭代对象，并将提供的函数应用于前两个元素，然后应用于结果和下一个元素，以此类推。

- Samir Talwar

---

set.intersection 接受任意数量的可迭代对象作为参数（在最近的 Python 版本中）。如果我没记错的话，这可以用比 reduce 方法提供的更好的算法复杂度来实现。 - Mike Graham

@Mike：太棒了，我不知道。 - Samir Talwar

Answer 4

我来回答自己的问题：

lists =  [range(100)[::4],range(100)[::3],range(100)[::2],range(100)[::1]]

out = set(lists[0])
for l in lists[1:]:
    out = set(l).intersection(out)

print out

或者

print list(out)

- thepandaatemyface

Answer 5

这里有一个使用传统的all()内置函数的一行代码:

list(num for num in data[0] 
     if all(num in range_ for range_ in data[1:]))

有趣的是，我认为这比在大数据集上使用“set”更易读且更快。

- Zev Averbach

Answer 6

您可以将它们视为集合并使用set.intersection()：

lists = [range(100)[::4], range(100)[::3], range(100)[::2], range(100)[::1]]
sets = [set(l) for l in lists]

isect = reduce(lambda x,y: x.intersection(y), sets)

- Andrew Jaffe

---

这会引发 AttributeError 吗？ - Mike Graham

糟糕，intersect已更正为intersection。 - Andrew Jaffe

Answer 7

l = [range(100)[::4], range(100)[::3], range(100)[::2], range(100)[::1]]
l = [set(i) for i in l]
intersect = l[0].intersection(l[1])
for i in l[2:]:
    intersect = intersect.intersection(i)

- inspectorG4dget

---

这会引发 NameError 吗？ - Mike Graham

我不这么认为，@MikeGraham。也许你指的是我编辑之前的代码。我运行了旧代码，出现了错误，但是这段代码已经经过测试，可以正常工作。 - inspectorG4dget

@inspectG4dget，我指的是在它被编辑之前的代码（我的评论至少与编辑一样旧吧？）这段代码不会出现那个错误，尽管我必须承认我觉得你的设计有点奇怪。 - Mike Graham

@MikeGraham：我看到了编辑和评论的时间，这就是为什么我建议你的评论可能是在编辑之前发布的原因。但我很好奇你为什么要改变这个设计，以及如何改变的。 - inspectorG4dget

@MikeGraham：非常正确。我曾考虑过这样做，但我想让我的代码更透明 - 特别是因为我根本没有记录它。我不知道@thepandaatemyface的熟练程度，因此希望尽可能简单。 - inspectorG4dget

我不认为我的第一个示例比你的代码更复杂，但我想这就是世界运转的方式。:) - Mike Graham