如何在忽略元组的最后一个元素的情况下找到一组元组的交集？

Question

编辑：已解决

我通过创建字典a和b解决了这个问题，其中键是元组(x,y)，我的值是整数t。然后我将我的键作为集合返回，进行内置的intersection操作，然后获取所有相交点(x,y)的值。

a{(x,y): t, ...}
b{(x,y): t, ...}
c = set([*a]).intersection(set([*b]))
for each in c:
    val_a = a.get(each)
    val_b = b.get(each)

原问题

我有两组元组，每个元组的形式为

a = {(x,y,t), (x,y,t), ...}
b = {(x,y,t), (x,y,t), ...}

我想找到a和b的“交集”，同时忽略元组中的t元素。

例如：

a = {(1,2,5), (4,6,7)}
b = {(1,2,7), (5,5,3)}
c = a.magicintersection(b,'ignore-last-element-of-tuple-magic-keyword')

其中c表示期望输出结果，将会得到{(1,2,5)，(1,2,7)}。

我想利用内置的intersection函数，而不是编写自己的（极其低效）函数，但我找不到解决此问题的方法。

- jrecord

---

预期输出是什么？请提供 [mcve]。 - Ch3steR

你可以从元组中派生一个新类（或创建一个全新的类），该类仅基于前两个元素返回哈希值，并仅在这些元素上测试相等性。然后，您需要将此类的实例存储在集合中。 - Michael Butscher

Answer 1

你不能使用内置的交集方法来实现。你也不能将函数附加到内置函数中：

def magic_intersect(x):
    pass

set.mi = magic_intersect

结果为

    set.mi = magic_intersect
TypeError: can't set attributes of built-in/extension type 'set'

---

你可以将它们全部放入一个字典中，使用每个元组的前两个元素作为键，匹配这些元组的所有元组作为集合/列表的值，以获得结果：

a = {(1,2,5), (4,6,7)}
b = {(1,2,7), (5,5,3)}

from collections import defaultdict

d = defaultdict(set)

for x in (a,b):
    for s in x: 
        d[(s[0],s[1])].add(s)

print(d)
print(d.get( (1,2) )) # get all tuples that start with (1,2,_)

输出：

defaultdict(<class 'set'>, {
    (4, 6): {(4, 6, 7)}, 
    (1, 2): {(1, 2, 5), (1, 2, 7)}, 
    (5, 5): {(5, 5, 3)}})

{(1, 2, 5), (1, 2, 7)}

但只有在需要多次查询且不需要将数百万个集合放入其中时，这才值得。

实际的“查找”哪个2元组具有哪些3元组是O(1)快速的 - 但您需要时间/空间来构建字典。

这种方法会丢失项目来自哪个元组集的信息 - 如果您还需要保留该信息，则还必须以某种方式存储它。

- Patrick Artner

---

谢谢。我有一种感觉，我可能需要使用一个我不熟悉的字典。我会研究一下这种形式的东西。 - jrecord

Answer 2

如果第三个组件变化，你的“交集”会有什么结果？

无论如何，做这件事的方法是拥有一个字典，其中键是感兴趣的元组。字典值可以是具有所有匹配3元组的列表，然后您可以仅选择具有多个元素的那些。

这不是低效的，您只需要遍历每个集合一次 - 因此它是O（M + N） - 并且您有许多列表和成千上万个具有相同x，y的元组 - 然后构建字典将匹配的元组附加到列表中，这是O（1）。

matches = {}
for series_of_tuples in (a, b):
    for tuple in series_of_tuples:
       matches.setdefault(tuple[:2], []).append(tuple)

intersection = [values for values in matches.values() if len(values) > 1]

- jsbueno

---

谢谢 - 我采纳了您的建议，创建了一个字典，其中每个键都是感兴趣的元组（x，y），并将值设置为整数t。 - jrecord