优化Python SortedList中自定义对象的高效搜索-Python教程-PHP中文网

优化Python SortedList中自定义对象的高效搜索

碧海醫心

发布： 2025-10-25 09:57:01

原创

619人浏览过

优化Python SortedList中自定义对象的高效搜索

本文探讨了在python `sortedcontainers`库的`sortedlist`中，如何高效地搜索自定义类对象。针对按字符串属性搜索的需求，我们分析了传统方法的局限性，并提出通过在自定义类中实现富比较方法（如`__lt__`和`__eq__`），以支持直接使用字符串进行二分查找，从而实现更简洁、更符合面向对象原则的解决方案。

背景与挑战

sortedcontainers库提供的SortedList是一个功能强大的有序列表实现，它在保持元素有序的同时，提供了高效的插入、删除和查找操作。当SortedList中存储的是自定义类的对象时，我们通常会为其指定一个key函数来定义排序规则。例如，一个Supplier类的列表可能按其Name属性进行排序：

from typing import List
from sortedcontainers import SortedList

class Supplier:
    def __init__(self, name: str, id: int, sap_id: int):
        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):
        # 初始 SortedList 按供应商名称（小写）排序
        self.suppliers = SortedList(key=lambda x: x.Name.lower())

登录后复制

然而，当需要根据一个简单的字符串（例如供应商名称）在SortedList中查找对应的Supplier对象时，bisect_left等二分查找方法会遇到挑战。bisect_left期望比较的两个对象类型一致，或者至少能够相互比较。如果直接传入一个字符串，而SortedList中存储的是Supplier对象，默认情况下它们无法直接比较，导致查找失败。

传统方法的局限性

为了解决上述问题，常见的尝试包括：

直接使用bisect_left(name)： 这种方法会因为str和Supplier类型不兼容而报错，因为SortedList的key函数只影响排序，不改变bisect_left在内部进行比较时的数据类型。
创建临时对象进行查找： 一种可行的变通方法是创建一个临时的Supplier对象，只填充用于比较的Name属性，然后用这个临时对象进行查找：
```
# Data 类的一部分
def find_supplier_with_temp_object(self, name: str) -> Supplier | None:
    temporary_supplier = Supplier(name, 0, 0) # 创建临时对象
    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免费学习笔记（深入）”；

优雅的解决方案：利用富比较方法

Python的面向对象特性允许我们通过实现“富比较方法”（rich comparison methods），如__lt__（小于）、__le__（小于等于）、__eq__（等于）等，来定义对象之间的比较行为。通过在Supplier类中实现这些方法，我们可以让Supplier对象能够直接与字符串进行比较，从而简化SortedList的查找逻辑。

为了实现按名称进行大小写不敏感的排序和查找，我们需要修改Supplier类，使其能够与str类型以及其他Supplier类型进行比较。

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

查看详情

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}')"

    # 定义小于比较行为，支持与字符串和Supplier对象比较
    def __lt__(self, other):
        if isinstance(other, str):
            # 将自身名称和小写化的other字符串进行比较
            return self.Name.lower() < other.lower()
        elif isinstance(other, Supplier):
            # 将自身名称和小写化的other Supplier名称进行比较
            return self.Name.lower() < other.Name.lower()
        return NotImplemented # 不支持与其他类型比较

    # 定义等于比较行为，支持与字符串和Supplier对象比较
    def __eq__(self, other):
        if isinstance(other, str):
            return self.Name.lower() == other.lower()
        elif isinstance(other, Supplier):
            return self.Name.lower() == other.Name.lower()
        return NotImplemented # 不支持与其他类型比较

    # 建议也实现 __gt__, __le__, __ge__, __ne__ 以提供完整的比较逻辑
    def __gt__(self, other):
        if isinstance(other, str):
            return self.Name.lower() > other.lower()
        elif isinstance(other, Supplier):
            return self.Name.lower() > other.Name.lower()
        return NotImplemented

    def __le__(self, other):
        if isinstance(other, str):
            return self.Name.lower() <= other.lower()
        elif isinstance(other, Supplier):
            return self.Name.lower() <= other.Name.lower()
        return NotImplemented

    def __ge__(self, other):
        if isinstance(other, str):
            return self.Name.lower() >= other.lower()
        elif isinstance(other, Supplier):
            return self.Name.lower() >= other.lower()
        return NotImplemented

    def __ne__(self, other):
        return not self.__eq__(other)

登录后复制

通过实现__lt__和__eq__方法，Supplier对象现在可以“理解”如何与字符串进行比较。这意味着：

SortedList在初始化时不再需要key函数，因为它会直接使用Supplier对象自身的比较逻辑进行排序。
bisect_left方法在接收一个字符串作为参数时，会调用Supplier对象的__lt__方法进行比较，从而正确地找到插入点。

实现与示例

现在，Data类中的SortedList初始化和find_supplier方法可以变得更加简洁：

class Data:
    def __init__(self):
        # SortedList 现在可以直接使用 Supplier 对象的 __lt__ 等方法进行排序
        self.suppliers = SortedList()

    def find_supplier(self, name: str) -> Supplier | None:
        # 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__":
    d = Data()

    # 添加供应商
    d.suppliers.add(Supplier('Apple Inc.', 101, 1001))
    d.suppliers.add(Supplier('Banana Corp.', 102, 1002))
    d.suppliers.add(Supplier('Cherry Ltd.', 103, 1003))
    d.suppliers.add(Supplier('apple holdings', 104, 1004)) # 名称大小写不同

    print("SortedList 内容:", d.suppliers) # 此时会按名称小写排序

    # 查找供应商
    found_supplier_apple = d.find_supplier('apple inc.')
    print(f"\n查找 'apple inc.': {found_supplier_apple}")

    found_supplier_banana = d.find_supplier('Banana Corp.')
    print(f"查找 'Banana Corp.': {found_supplier_banana}")

    found_supplier_grape = d.find_supplier('Grape Co.')
    print(f"查找 'Grape Co.': {found_supplier_grape}")

    found_supplier_apple_holdings = d.find_supplier('apple holdings')
    print(f"查找 'apple holdings': {found_supplier_apple_holdings}")

登录后复制

输出示例：

SortedList 内容: [Supplier(Name='Apple Inc.'), Supplier(Name='apple holdings'), Supplier(Name='Banana Corp.'), Supplier(Name='Cherry Ltd.')]

查找 'apple inc.': Supplier(Name='Apple Inc.')
查找 'Banana Corp.': Supplier(Name='Banana Corp.')
查找 'Grape Co.': None
查找 'apple holdings': Supplier(Name='apple holdings')

登录后复制

从输出可以看出，SortedList正确地将'Apple Inc.'和'apple holdings'相邻排序，并且find_supplier方法能够通过大小写不敏感的字符串查找，准确地返回对应的Supplier对象。

注意事项与最佳实践

全面实现比较方法： 为了确保对象在各种场景下（如排序、比较、集合操作等）都能正常工作，建议实现所有的富比较方法 (__lt__, __le__, __eq__, __ne__, __gt__, __ge__)。如果只实现了__lt__，Python有时会尝试推断其他比较操作，但明确定义它们可以避免潜在的混淆和错误。
NotImplemented的使用： 在富比较方法中，当遇到不支持的类型进行比较时，返回NotImplemented是一个良好的实践。这会告诉Python尝试调用other对象的反向比较方法，或者最终抛出TypeError，而不是返回一个可能误导的False。
性能考量： 这种方法避免了在每次查找时创建临时对象，从而提高了查找效率。同时，将比较逻辑封装在类内部，也使得代码更加内聚和易于维护。
一致性： 确保__lt__和__eq__等方法的比较逻辑与你期望的排序和查找行为（例如，大小写敏感或不敏感）保持一致。在本例中，我们选择了大小写不敏感的比较，这与原始SortedList使用key=lambda x: x.Name.lower()的意图相符。
bisect_left与__eq__： bisect_left找到的是元素可以插入而不破坏排序的最小索引。即使__lt__逻辑正确，最终仍需通过self.suppliers[index].Name.lower() == name.lower()来确认找到的元素是否精确匹配，因为列表中可能存在多个具有相同排序键但实际内容不同的元素，或者查找的元素不存在。

总结

通过在自定义类中巧妙地实现富比较方法，我们可以让SortedList中的对象与外部的简单类型（如字符串）进行直接、高效且符合逻辑的比较。这种方法不仅消除了创建临时对象的“丑陋”代码，还提升了代码的清晰度、可维护性和面向对象的设计原则。它提供了一种更自然、更Pythonic的方式来处理SortedList中自定义对象的复杂搜索需求。

以上就是优化Python SortedList中自定义对象的高效搜索的详细内容，更多请关注php中文网其它相关文章！