python - 在 Python 中获取多个元组列表的第二个元素的交集的简单有效的方法？

Question

我是 Python 的新手(在 2.7 中工作)，我发现 SO 是非常有值(value)的资源!

假设我正在处理几个通常采用 (ID, value) 形式的 2 元素元组列表，例如，

list1 = [(111, 222), (111, 333), (111, 444)]
list2 = [(555, 333), (555, 444), (555, 777)]
list3 = [(123, 444), (123, 888), (123, 999)]

我真正想做的是找到一种简单(且计算效率高)的方法来获取这些元组的第二个元素的交集。我看过 Python docs并发现 sets 可能会做我想要的......和 ​​this post帮助我了解如何获得两个列表的交集。

我知道我可以通过像这样遍历元组来制作三个全新的“仅值”列表:

newList1 = []
for tuple in list1:
   newList1.append(tuple[1])
newList2 = []
for tuple in list2:
   newList2.append(tuple[1])
newList3 = []
for tuple in list3:
   newList3.append(tuple[1])

然后像这样得到每对的交集:

i_of_1and2 = set(newList1).intersection(newList2)
i_of_1and3 = set(newList2).intersection(newList3)
i_of_2and3 = set(newList1).intersection(newList3)

但我的列表有点大 - 像数十万(有时数千万)个元组。这真的是获取这三个列表元组中第二个元素交集的最佳方法吗？在我看来……不优雅……

感谢您的帮助!

Answer 1

从 variable1 开始你展示了一个大问题通常是一个不好的迹象 - 如果你想要有多个值，使用数据结构，而不是很多带有编号名称的变量。这会阻止您一遍又一遍地重复您的代码，并有助于阻止错误。

让我们使用列表列表代替:

values = [
    [(111, 222), (111, 333), (111, 444)],
    [(555, 333), (555, 444), (555, 777)],
    [(123, 444), (123, 888), (123, 999)]
]

现在我们只想获取子列表中每个元组的第二个元素。这很容易使用 list comprehension 来计算:

>>> [[item[1] for item in sublist] for sublist in values]
[[222, 333, 444], [333, 444, 777], [444, 888, 999]]

然后，我们想要项目之间的交集，我们使用 itertools.combinations()得到各种可能的两对:

>>> for values, more_values in itertools.combinations(new_values, 2):
...     set(values).intersection(more_values)
... 
{444, 333}
{444}
{444}

所以，如果我们将其包装在一起:

import itertools

values = [
    [(111, 222), (111, 333), (111, 444)],
    [(555, 333), (555, 444), (555, 777)],
    [(123, 444), (123, 888), (123, 999)]
]

sets_of_first_items = ({item[1] for item in sublist} for sublist in values)
for values, more_values in itertools.combinations(sets_of_first_items, 2):
    print(values.intersection(more_values))

这给了我们:

{444, 333}
{444}
{444}

我在这里所做的更改是使内部列表成为集合推导式，以避免创建列表只是为了将其转换为集合，并使用生成器表达式而不是列表推导式，因为它是延迟计算的。

最后一点，如果您想要我们用来生成交集的列表的索引，使用 the enumerate() builtin 很简单:

sets_of_first_items = ({item[1] for item in sublist} for sublist in values)
for (first_number, first_values), (second_number, second_values) in itertools.combinations(enumerate(sets_of_first_items), 2):
    print("Intersection of {0} and {1}: {2}".format(first_number, second_number, first_values.intersection(second_values)))

这给了我们:

Intersection of 0 and 1: {444, 333}
Intersection of 0 and 2: {444}
Intersection of 1 and 2: {444}

编辑:

作为noted by tonyl7126 ，这也是一个可以通过使用更好的数据结构得到很大帮助的问题。这里最好的选择是将用户 ID 的字典用于一组产品 ID。当您只需要一个集合并稍后将其转换为一个集合时，没有理由将您的数据存储为列表，对于您尝试存储的数据类型，dict 是一个更好的解决方案。

请看下面的例子:

import itertools

values = {
    "111": {222, 333, 444},
    "555": {333, 444, 777},
    "123": {444, 888, 999}
}

for (first_user, first_values), (second_user, second_values) in itertools.combinations(values.items(), 2):
    print("Intersection of {0} and {1}: {2}".format(first_user, second_user, first_values.intersection(second_values)))

给我们:

Intersection of 555 and 123: {444}
Intersection of 555 and 111: {444, 333}
Intersection of 123 and 111: {444}