如何在嵌套列表中找到所有列表共有的元素？

Question

我有一个大的嵌套列表，其中每个子列表都包含格式为浮点数的数字列表。但是除了一些例外之外，嵌套列表中的每个单独的列表都是相同的。我想提取所有嵌套列表中所有列表都包含的数字。下面是我的问题的简单示例：

nested_list = [[1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0],
              [2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0],
              [1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0],
              [2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0]]

在下面的案例中，我想要提取以下内容：

common_vals = [2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0]

我尝试使用集合交集来解决这个问题，但是由于我无法将其应用于嵌套列表的所有元素，因此并没有成功。

- sTr8_Struggin

Answer 1

您可以使用reduce和set.intersection来实现：

>>> reduce(set.intersection, map(set, nested_list))
set([2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0])

使用itertools.imap可以实现更节省内存的解决方案。

时间比较：

>>> lis = [[1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0],
              [2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0],
              [1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0],
              [2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0]]
>>> %timeit set.intersection(*map(set, lis))
100000 loops, best of 3: 12.5 us per loop
>>> %timeit set.intersection(*(set(e) for e in lis))
10000 loops, best of 3: 14.4 us per loop
>>> %timeit reduce(set.intersection, map(set, lis))
10000 loops, best of 3: 12.8 us per loop
>>> %timeit reduce(set.intersection, imap(set, lis))
100000 loops, best of 3: 13.1 us per loop
>>> %timeit set.intersection(set(lis[0]), *islice(lis, 1, None))
100000 loops, best of 3: 10.6 us per loop


>>> lis = [[1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0],
              [2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0],
              [1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0],
              [2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0]]*1000
>>> %timeit set.intersection(*map(set, lis))
10 loops, best of 3: 16.4 ms per loop
>>> %timeit set.intersection(*(set(e) for e in lis))
10 loops, best of 3: 15.8 ms per loop
>>> %timeit reduce(set.intersection, map(set, lis))
100 loops, best of 3: 16.3 ms per loop
>>> %timeit reduce(set.intersection, imap(set, lis))
10 loops, best of 3: 13.8 ms per loop
>>> %timeit set.intersection(set(lis[0]), *islice(lis, 1, None))
100 loops, best of 3: 8.4 ms per loop


>>> lis = [[1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0],              [2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0],
              [1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0],
              [2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0]]*10**5
>>> %timeit set.intersection(*map(set, lis))  
1 loops, best of 3: 1.92 s per loop
>>> %timeit set.intersection(*(set(e) for e in lis))
1 loops, best of 3: 2.17 s per loop
>>> %timeit reduce(set.intersection, map(set, lis))
1 loops, best of 3: 2.14 s per loop
>>> %timeit reduce(set.intersection, imap(set, lis))
1 loops, best of 3: 1.52 s per loop
>>> %timeit set.intersection(set(lis[0]), *islice(lis, 1, None))
1 loops, best of 3: 913 ms per loop

结论：

Steven Rumbalski的解决方案在效率方面显然是最佳的。

- Ashwini Chaudhary

Answer 2

试试这个，它是最简单的解决方案：

set.intersection(*map(set, nested_list))

如果您更喜欢使用生成器表达式，这应该是一种在内存使用方面更有效的解决方案：

set.intersection(*(set(e) for e in nested_list))

- Óscar López

---

在这种特定情况下，在调用函数之前，生成器表达式被转换为元组，因此没有任何好处。 - Sven Marnach

Answer 3

Ashwini Chaudhary的解决方案很优雅，但对于大型输入可能相当低效，因为它会创建许多中间集合。如果你的嵌套列表很大，可以这样做：

>>> set.intersection(set(nested_list[0]), *itertools.islice(nested_list, 1, None))
set([2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0])

- Steven Rumbalski

---

注意： nested_list[1：] 创建了 nested_list 的浅拷贝，可以使用 itertools.islice(nested_list, 1, None) 避免这种情况。 - Sven Marnach

@SvenMarnach：好观点。已更改为使用itertools.islice。Sven Marnach回来了！ - Steven Rumbalski

Answer 4

统计嵌套列表中每个集合中元素的出现次数，如果出现次数等于嵌套列表中元素的数量，则表示该元素在所有集合中都存在。 如果嵌套列表中的元素没有重复数字，则不需要进行集合转换。

nested_list = [[1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0],
              [2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0],
              [1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0],
              [2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0]]

from collections import Counter
result = [val for val,cnt in Counter([x for t in nested_list for x in set(t)]).items() if cnt == len(nested_list)]
print result


 #  [2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0]

- DhruvPathak