Python：如何基于对象的ID查找两个列表之间的交集？

Question

我知道如果我有两个列表，比如整数，我可以简单地执行 list(set(list1) & set(list2)) 来获取它们的交集。但是，在我的两个列表中，我有可变对象，即Nodes。 Node是一个可以用值初始化的类。

在不必进行双重循环的情况下，是否有任何方法可以根据它们的id获取两个列表的交集？ 我正在寻找类似于list(set(list1) & set(list2))的东西。

更新：通过id，我指的是Python中内置的id()函数，它返回存储对象的内存地址。

所以，我想问的是，例如[Node1，Node2，Node3]和[Node100，Node2，Node3]的交集是什么。显然，我不能使用上面的集合交集方法。我需要通过访问内存来识别它们是否相同。如果我不能基于它们的值属性进行识别，因为它们可能具有与Node100相同的值，但它们不是内存中的相同对象。

- TheRealFakeNews

---

你说的“基于它们的id”是什么意思？id是Node对象的属性吗？ - Philip Tzou

你所说的“id”，是指可能同时出现在list1和list2中的相同对象的引用吗？ - Valentino

@Primusa，你为什么删除了你的回答？ - Mad Physicist

@MadPhysicist Philip的回答更好。我没有继续保留我的意义; 我会点赞他的回答并继续前进。 - Primusa

只是为了确认，因为我不确定：如果两个节点在内存中不是同一个对象，但它们的值相同，你是否想在最终列表中保留它们？ - Valentino

你提出的建议可行。 - Olivier Melançon

Answer 1

不需要求两个集合的交集。在这种情况下，您只需检查id()是否存在于另一个集合中。

set2 = {id(n) for n in list2}
result = [n for n in list1 if id(n) in set2]

这段代码的复杂度为 O(n1 + n2)。我将在下面提供等效但更易读的代码来解释它：

set2 = {id(n) for n in list2}  # O(n2)
result = []
for n in list1:  # O(n1)
    if id(n) in set2:  # O(1)
        result.append(n)  # O(1)

总共是 O(n1 + n2)。

---

如果您可以对Node类进行更改并定义__hash__和__eq__方法，则还有另一种替代方案。

class Node:
    ...

    def __hash__(self):
        return id(self)

    def __eq__(self, another):
        return id(self) == id(another)


list1 = [...]
list2 = [...]

result = set(list1) & set(list2)

- Philip Tzou

---

我指的是Python中的id内置函数，而不是我的属性。 - TheRealFakeNews

此外，这只是一个for循环。 - TheRealFakeNews

@MadPhysicist 嗯，你首先必须将列表转换为集合。在内部，set() 初始化程序也会遍历整个列表（我认为它会计算一个循环）。 - Philip Tzou

@AlanH。这不仅仅是一个for循环。集合构建是O(n2)，循环是O(n1)。这使得它成为O(n1+n2)，而不是O(n1*n2)。对于可比较的列表大小，您最终得到O(n)而非O(n^2)。而且，您可以轻松地将n.id替换为id(n)。 - Mad Physicist

@MadPhysicist 实际上，默认情况下 __hash__ 返回 id() / 16 返回的内容...(参见 https://dev59.com/5Ggu5IYBdhLWcg3wbWk9#11324771) - Philip Tzou

Answer 2

你提出的解决方案可行。

class Node:
    def __init__(self, value):
        self.value = value

    def __repr__(self):
        return "Node {}".format(self.value)

nodes1 = [Node(1), Node(2), Node(3)]
nodes2 = nodes1[:2] + [Node(4)]

common_nodes = set(nodes1) & set(nodes2)

print(common_nodes) # {Node 2, Node 1}

这段代码之所以能够运行，是因为尽管是可变的，但如果你没有定义__hash__或__eq__方法的类的实例，它会默认使用id来进行哈希和比较，因为它继承了这些方法来自于object。

你可以通过以下实验来验证这一点。

>>> obj = object()
>>> hash(obj)
155115580943
>>> id(obj)
2481849295088
>>> id(obj) // 16 == hash(obj)
True

- Olivier Melançon