基于图同构规则对含自定义对象的大型列表去重优化求助

一、原代码的核心问题 #

1. 遍历中修改列表：for B in list_时执行list_.remove(B)会破坏迭代器，导致部分元素被跳过，同时remove操作是O(n)时间，累积下来开销极大。
2. O(n²)的时间复杂度：每个元素都要和剩余所有元素做同构检测，对于10000个元素来说，最坏情况要做近5000万次同构判断，而图同构本身是NP问题，大图的检测耗时会指数级上升。
3. 过滤条件太弱：仅用节点数过滤，节点数相同的图数量可能很多，无法有效减少检测次数。

二、优化步骤 #

1. 提取图的哈希特征，预分组 #

先计算每个图的**不变特征（invariant）**作为分组键，比如NetworkX提供的nx.weisfeiler_lehman_graph_hash（WL哈希）——对同构图会生成相同哈希，不同图大概率不同哈希，是高效的预过滤手段。用WL哈希分组，把哈希相同的图分到同一组，只有同组内的图才需要做同构检测，能大幅减少检测次数。

2. 用字典管理分组，组内去重 #

遍历所有对象，按WL哈希分组，然后对每个分组内的对象，只保留第一个（或任意一个）与其他不同构的对象。

3. 避免遍历中修改列表，改用迭代器+集合记录已保留的图 #

对于每个分组，维护一个已保留的图的列表，新对象的图只需要和已保留的图做同构检测，而不是和所有剩余对象比较。

三、实现代码 #

import networkx as nx

def node_check(node1, node2):
    # 保持你原来的节点匹配逻辑，比如节点属性相等
    return node1.get('attr') == node2.get('attr')

def remove_duplicates(objs):
    # 第一步：按WL哈希分组
    hash_groups = {}
    for obj in objs:
        # 计算图的WL哈希，node_match参数和同构检测保持一致
        graph_hash = nx.weisfeiler_lehman_graph_hash(
            obj.graph,
            node_attr=list(obj.graph.nodes[0].keys()) if obj.graph.nodes else None,
            node_match=node_check
        )
        if graph_hash not in hash_groups:
            hash_groups[graph_hash] = []
        hash_groups[graph_hash].append(obj)
    
    # 第二步：每个分组内去重
    filtered = []
    for group in hash_groups.values():
        # 保留的对象列表
        kept = []
        for obj in group:
            # 检查当前对象的图是否和已保留的图都不同构
            is_unique = True
            for kept_obj in kept:
                if nx.is_isomorphic(obj.graph, kept_obj.graph, node_match=node_check):
                    is_unique = False
                    break
            if is_unique:
                kept.append(obj)
        filtered.extend(kept)
    
    return filtered

四、进一步优化建议 #

• 使用更快的同构算法：NetworkX的nx.is_isomorphic默认用VF2，对于大图可以尝试nx.vf2pp_is_isomorphic（VF2++，优化版，速度更快）。
• 并行处理分组：如果CPU核心足够，可以用multiprocessing对每个分组的去重做并行计算，示例代码：

  from multiprocessing import Pool
  
  def process_group(group):
      kept = []
      for obj in group:
          is_unique = True
          for kept_obj in kept:
              if nx.vf2pp_is_isomorphic(obj.graph, kept_obj.graph, node_match=node_check):
                  is_unique = False
                  break
          if is_unique:
              kept.append(obj)
      return kept
  
  def remove_duplicates_parallel(objs):
      hash_groups = {}
      for obj in objs:
          graph_hash = nx.weisfeiler_lehman_graph_hash(
              obj.graph,
              node_attr=list(obj.graph.nodes[0].keys()) if obj.graph.nodes else None,
              node_match=node_check
          )
          if graph_hash not in hash_groups:
              hash_groups[graph_hash] = []
          hash_groups[graph_hash].append(obj)
      
      with Pool() as pool:
          results = pool.map(process_group, hash_groups.values())
      
      filtered = []
      for res in results:
          filtered.extend(res)
      return filtered
  

• 提前过滤节点/边数不同的图：在计算哈希前，可以先把节点数、边数作为第一层分组键，再用WL哈希做第二层，进一步缩小同构检测范围。

内容的提问来源于stack exchange，提问作者student7481