python - 从大列表中按规则删除重复项

Question

我有一个包含 10.000 个自定义对象元素的列表。重要的是这些对象有一个图作为属性(由 20 到 500 个节点组成)。

现在我想删除列表中的所有重复项，我假设两个对象相等，当且仅当它们的图是同构的。

我的代码看起来像这样:

import networkx as nx
#
def remove_duplicates(list_):
 
    filtered_list = list()
 
    while len(list_) > 0:
        A = list_.pop()
        filtered_list.append(A)
 
        for B in list_:
            if A.num_of_nodes == B.num_of_nodes:
                if nx.is_isomorphic(A.graph, B.graph, node_match=node_check):
                     list_.remove(B)

    return filtered_list

但是，程序会在某个点停止进行。我检查了事件监视器，显然内存不是问题，但可能是 CPU。

是否有人提示如何更有效/更优雅地解决这个问题？对于较小的样本，我的代码运行良好。

Answer 1

只要您在 self.graph 中找到与任何其他同构图相同的内容，并将其放在 ??? 的位置，这就会起作用(例如 self.graph.some_isomorphic_characteristic)

import networkx as nx
from typing import List

class custom_object:
    def __init__(self, num_of_nodes, graph):
        self.num_of_nodes = num_of_nodes
        self.graph = graph
    def __eq__(self, other):
        return self.num_of_nodes == other.num_of_nodes and nx.is_isomorphic(self.graph, other.graph, node_match=node_check)
    def __ne__(self, other):
        return not self.__eq__(other)
    def __hash__(self):
        return hash((self.num_of_nodes, ???))

def remove_duplicates(list_: List[custom_object]) -> List[custom_object]:
    return list(set(list_))

否则你可以使用

import networkx as nx
from typing import List

class custom_object:
    def __init__(self, num_of_nodes, graph):
        self.num_of_nodes = num_of_nodes
        self.graph = graph
    def __eq__(self, other):
        return self.num_of_nodes == other.num_of_nodes and nx.is_isomorphic(self.graph, other.graph, node_match=node_check)
    def __ne__(self, other):
        return not self.__eq__(other)

def remove_duplicates(list_: List[custom_object]) -> List[custom_object]:
    filtered_list = []
    for obj in list_:
        add = True
        for filtered_obj in filtered_list:
            if obj == filtered_obj:
                add = False
                break
        if add:
            filtered_list.append(obj)
    return filtered_list