如何在Python中快速比较大型数据类对象列表

现有两个需对齐的数据源：主数据源（master）和需镜像主源状态的客户端数据源（client）。已将两者导入Python并转换为数据类（dataclass）对象列表，需要对比数据得到差异列表：客户端缺失的条目标记为添加，多余的条目标记为删除。

原对比代码如下：

import copy
from tqdm import tqdm

def compare_data(csv_data_expected, csv_data_actual):
        csv_data_to_add = copy.deepcopy(csv_data_expected)
        csv_data_to_delete = copy.deepcopy(csv_data_actual)
        for entry in tqdm(csv_data_expected):
            if entry in csv_data_actual:
                csv_data_to_add.remove(entry)
                csv_data_to_delete.remove(entry)
        [setattr(x, "add", "ADD") for x in csv_data_to_add]
        [setattr(x, "delete", "DEL") for x in csv_data_to_delete]
        return csv_data_to_delete + csv_data_to_add

原逻辑是复制两个列表，遍历主列表移除双方共有的条目，剩余部分分别作为待添加/待删除条目。但使用数据类后，4万条含3个属性的数据类对象对比耗时长达半小时，需在保留数据类的前提下提升对比速度。

• 让数据类支持哈希与快速比较
  默认数据类不可哈希（除非指定frozen=True），而列表的in和remove操作均为O(n)时间复杂度，这是性能瓶颈的核心。给数据类添加哈希支持，要么定义数据类时加上@dataclasses.dataclass(frozen=True)（允许数据类不可变），要么手动实现__eq__和__hash__方法，确保属性相同的对象被视为相等且哈希值一致，这样就能将对象存入集合，利用集合O(1)的查找效率。

• 用集合替代列表做差集计算
  将数据类对象列表转换为集合后，直接计算差集得到待添加和待删除条目，时间复杂度从原代码的O(n²)降到O(n)，性能会有数量级提升：

  import dataclasses
  
  # 示例数据类定义（带哈希支持）
  @dataclasses.dataclass(frozen=True)
  class DataEntry:
      attr1: str
      attr2: int
      attr3: bool
  
  def compare_data(csv_data_expected, csv_data_actual):
      expected_set = set(csv_data_expected)
      actual_set = set(csv_data_actual)
      
      # 待添加：主数据源有、客户端无
      csv_data_to_add = list(expected_set - actual_set)
      # 待删除：客户端有、主数据源无
      csv_data_to_delete = list(actual_set - expected_set)
      
      # 标记操作类型
      for entry in csv_data_to_add:
          setattr(entry, "action", "ADD")
      for entry in csv_data_to_delete:
          setattr(entry, "action", "DEL")
      
      return csv_data_to_delete + csv_data_to_add
  

  如果不能使用frozen=True，可以手动实现比较和哈希方法：

  @dataclasses.dataclass
  class DataEntry:
      attr1: str
      attr2: int
      attr3: bool
      
      def __eq__(self, other):
          if not isinstance(other, DataEntry):
              return False
          return (self.attr1 == other.attr1 and
                  self.attr2 == other.attr2 and
                  self.attr3 == other.attr3)
      
      def __hash__(self):
          return hash((self.attr1, self.attr2, self.attr3))
  

• 移除不必要的深拷贝
  原代码中的copy.deepcopy是高耗时操作，优化后的方案直接通过集合差集获取差异条目，无需复制整个列表，大幅节省拷贝开销。

• 替换低效的循环+remove操作
  原代码中每次remove都要遍历列表查找元素，4万条数据会导致大量重复遍历。换成集合操作后，差集计算直接完成筛选，彻底避免了O(n²)的时间消耗。

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