优化Python SortedList中自定义对象的查找策略-Python教程-PHP中文网

优化python sortedlist中自定义对象的查找策略

本文探讨了在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的面向对象特性，提升了代码的模块化和可读性，实现了更优雅的数据结构操作。

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