如何基于evaluation_function属性在有序Node列表中高效插入节点？

嘿，这个问题我之前做类似项目的时候也遇到过！每次插入后全量排序确实有点浪费性能，尤其是当队列里的节点越来越多的时候。其实Python标准库就有专门解决这个问题的工具——bisect模块，它能帮你快速找到新元素应该插入的位置，然后直接把节点插进去，不用全量排序。

下面给你两种可行的方案，看哪种更适合你的场景：

方案1：给Node类添加比较运算符（推荐） #

如果可以修改Node类的定义，直接给它加上__lt__方法，这样bisect模块就能直接比较Node对象的大小了：

class Node:
    def __init__(self, evaluation_function):
        self.evaluation_function = evaluation_function
    
    # 定义小于比较规则，按evaluation_function升序排列
    def __lt__(self, other):
        return self.evaluation_function < other.evaluation_function

之后你就可以用bisect.insort直接插入节点，它会自动找到正确的位置：

import bisect

# 初始化有序队列
queue = []

# 插入新节点
new_node = Node(3.5)
bisect.insort(queue, new_node)

bisect.insort内部会先用*O(log n)的时间找到插入位置，然后用O(n)的时间移动元素完成插入，比每次append后sort的O(n log n)*效率高很多，节点越多性能提升越明显。

方案2：不修改Node类，手动计算插入位置 #

如果不能修改Node类，也可以通过提取evaluation_function的值来找到插入位置，再用列表的insert方法插入：

import bisect

queue = []  # 假设queue已经是按evaluation_function有序的
new_node = Node(3.5)

# 提取已有节点的evaluation_function值，找到插入位置
insert_pos = bisect.bisect_left(
    [node.evaluation_function for node in queue],
    new_node.evaluation_function
)
# 插入到对应位置
queue.insert(insert_pos, new_node)

这种方法不需要修改Node类，但每次插入都要生成一个临时的key列表，会有额外的内存开销，适合节点数量不多的场景。

小提示 #

如果你的场景中允许有相同evaluation_function的节点，并且需要保持插入顺序（稳定排序），可以用bisect.insort_right代替bisect.insort，它会把新节点插在相同值元素的后面。

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