本文探讨了在python `sortedcontainers.SortedList`中高效查找自定义对象的问题。当`SortedList`存储的是自定义类的实例，并需要根据其中某个属性（如名称）进行查找时，直接使用`bisect_left`并传入字符串会引发类型不匹配。传统的解决方案可能涉及创建临时对象或编写自定义二分查找，但更优雅的方法是为自定义类实现富比较方法（如`__lt__`），使其能够直接与字符串进行比较，从而简化`SortedList`的搜索逻辑，提升代码的简洁性和可维护性。
在处理Python中的有序列表（sortedcontainers.SortedList）时，我们经常需要存储自定义类的实例，并根据这些实例的特定属性进行快速查找。然而，当SortedList中存储的是自定义对象，而我们希望通过一个简单的字符串（例如，对象的名称）来查找对应对象时，会遇到一个常见挑战：bisect_left方法期望其搜索参数与列表中存储的元素类型兼容，以便进行有效的比较。
问题背景与传统方法局限
假设我们有一个Supplier类，包含Name、Id和SapId等属性，并将其存储在一个SortedList中，按照Name属性进行排序。
from typing import List from sortedcontainers import SortedList class Supplier: def __init__(self, name: str, id: int = 0, sap_id: int = 0): self.Name = name self.Id = id self.SapId = sap_id def __repr__(self): # 优化打印输出，方便调试 return f"Supplier(Name='{self.Name}', Id={self.Id})" class Data: def __init__(self): # 初始化时可以指定key，但对于bisect_left(str)不直接有效 self.suppliers = SortedList(key=lambda x: x.Name.lower()) def find_supplier(self, name: str): # 尝试直接用字符串搜索，但会失败 # index = self.suppliers.bisect_left(name) pass # 此处代码无法直接运行
当尝试使用self.suppliers.bisect_left(name)直接传入一个字符串name时，SortedList内部的比较逻辑会尝试将字符串与Supplier对象进行比较，这通常会导致TypeError，因为它们是不同的类型，默认情况下无法直接比较。
立即学习“Python免费学习笔记（深入）”；
一种常见的“变通”方法是创建一个临时的Supplier对象，只填充其用于比较的Name属性，然后用这个临时对象进行搜索：
# Part of the Data class (传统但不够优雅的方法) class Data: # ... (init方法同上) def find_supplier_ugly(self, name: str): temporary_supplier = Supplier(name) # 创建临时对象 index = self.suppliers.bisect_left(temporary_supplier) if index != len(self.suppliers) and self.suppliers[index].Name.lower() == name.lower(): return self.suppliers[index] return None
这种方法虽然能够实现功能，但每次查找都需要创建不必要的临时对象，不仅增加了内存开销，也使得代码不够简洁和优雅。
优雅的解决方案：实现富比较方法
Python的富比较方法（Rich Comparison Methods）提供了一种更优雅、更Pythonic的方式来解决这个问题。通过在自定义类中实现这些特殊方法，我们可以定义对象之间以及对象与不同类型（如字符串）之间的比较逻辑。对于SortedList和bisect_left而言，主要需要实现__lt__（小于）方法。
通过实现__lt__方法，我们可以让Supplier对象知道如何与另一个Supplier对象或一个字符串进行比较。
from typing import List from sortedcontainers import SortedList class Supplier: def __init__(self, name: str, id: int = 0, sap_id: int = 0): self.Name = name self.Id = id self.SapId = sap_id def __repr__(self): # 优化打印输出，方便调试 return f"Supplier(Name='{self.Name}', Id={self.Id}, SapId={self.SapId})" def __lt__(self, other): """ 定义Supplier对象的小于比较逻辑。 可以与另一个Supplier对象比较，也可以与字符串比较。 """ if isinstance(other, Supplier): return self.Name.lower() < other.Name.lower() elif isinstance(other, str): return self.Name.lower() < other.lower() else: # 处理其他不可比较类型，或者抛出错误 return NotImplemented # 建议返回NotImplemented让Python尝试其他比较方式 # 或者直接抛出TypeError
在__lt__方法中，我们首先检查other的类型。如果other也是一个Supplier对象，我们就比较它们的Name属性（为了大小写不敏感，都转换为小写）。如果other是一个字符串，我们就比较self.Name与这个字符串。这样，SortedList在内部进行排序以及bisect_left在查找时，都会使用我们定义的比较逻辑。
重要提示： 当自定义类实现富比较方法后，SortedList在初始化时就不再需要key参数了，因为它会直接使用对象自身的比较逻辑。
完整示例代码
下面是使用富比较方法实现Supplier查找的完整示例：
from sortedcontainers import SortedList class Supplier: def __init__(self, name: str, id: int = 0, sap_id: int = 0): self.Name = name self.Id = id self.SapId = sap_id def __repr__(self): return f"Supplier(Name='{self.Name}', Id={self.Id}, SapId={self.SapId})" def __lt__(self, other): """ 定义Supplier对象的小于比较逻辑，支持与Supplier对象和字符串的比较。 """ if isinstance(other, Supplier): return self.Name.lower() < other.Name.lower() elif isinstance(other, str): return self.Name.lower() < other.lower() else: # 尝试让Python处理其他比较，或抛出错误 return NotImplemented def __eq__(self, other): """ 可选：定义相等比较，确保能够正确判断两个对象是否相等。 对于查找后的精确匹配很有用。 """ if isinstance(other, Supplier): return self.Name.lower() == other.Name.lower() elif isinstance(other, str): return self.Name.lower() == other.lower() return NotImplemented class Data: def __init__(self): # Supplier类自身现在可比较，SortedList不再需要key参数 self.suppliers = SortedList() def find_supplier(self, name: str): """ 通过供应商名称在SortedList中查找对应的Supplier对象。 """ # bisect_left现在可以直接使用字符串进行搜索 index = self.suppliers.bisect_left(name) # 检查找到的索引是否有效，并且是精确匹配 if index != len(self.suppliers) and self.suppliers[index].Name.lower() == name.lower(): return self.suppliers[index] return None # 示例使用 if __name__ == "__main__": data_store = Data() # 添加供应商 data_store.suppliers.add(Supplier('apple Inc.', 101, 1001)) data_store.suppliers.add(Supplier('google LLC', 102, 1002)) data_store.suppliers.add(Supplier('microsoft Corp.', 103, 1003)) data_store.suppliers.add(Supplier('Amazon.com Inc.', 104, 1004)) data_store.suppliers.add(Supplier('facebook Inc.', 105, 1005)) data_store.suppliers.add(Supplier('apple holdings', 106, 1006)) # 测试大小写不敏感 print("SortedList中的供应商：") print(data_store.suppliers) # 输出会按照__lt__定义的顺序 print("n--- 查找示例 ---") # 查找存在的供应商 found_supplier = data_store.find_supplier('google LLC') if found_supplier: print(f"找到供应商: {found_supplier}") # 预期输出：Supplier(Name='Google LLC', Id=102, SapId=1002) else: print("未找到 Google LLC") # 查找大小写不敏感的供应商 found_supplier_case_insensitive = data_store.find_supplier('apple inc.') if found_supplier_case_insensitive: print(f"找到供应商 (大小写不敏感): {found_supplier_case_insensitive}") # 预期输出：Supplier(Name='Apple Inc.', Id=101, SapId=1001) else: print("未找到 apple inc.") # 查找不存在的供应商 not_found_supplier = data_store.find_supplier('Tesla Inc.') if not_found_supplier: print(f"找到供应商: {not_found_supplier}") else: print("未找到 Tesla Inc.") # 预期输出：未找到 Tesla Inc. # 查找另一个大小写不敏感的供应商 found_supplier_apple_holdings = data_store.find_supplier('apple holdings') if found_supplier_apple_holdings: print(f"找到供应商 (apple holdings): {found_supplier_apple_holdings}") else: print("未找到 apple holdings")
注意事项与总结
- 大小写敏感性： 在__lt__和find_supplier中的比较逻辑中，我们都使用了.lower()来确保查找是大小写不敏感的。如果需要大小写敏感的查找，可以移除.lower()调用。
- 精确匹配： bisect_left返回的是插入点索引，不保证该位置的元素就是我们要找的精确匹配。因此，在获取索引后，务必进行self.suppliers[index].Name.lower() == name.lower()的额外检查，以确认找到的是目标对象。
- 其他比较方法： 虽然__lt__对于SortedList的排序和bisect_left的查找至关重要，但如果需要更全面的对象比较行为（例如，使用==操作符），也应该实现__eq__方法。
- NotImplemented： 在富比较方法中，当遇到无法处理的类型时，返回NotImplemented而不是抛出TypeError是一种良好的实践。这允许Python尝试反向操作（例如，如果a < b返回NotImplemented，Python可能会尝试b > a）或使用其他默认比较机制。
- 代码简洁性： 通过在自定义类中实现富比较方法，我们消除了在查找逻辑中创建临时对象的需要，使find_supplier方法更加简洁、直观和高效。
通过这种方式，我们不仅解决了在SortedList中查找自定义对象的类型不匹配问题，还通过利用Python的面向对象特性，提升了代码的模块化和可读性，实现了更优雅的数据结构操作。