Python中高效修改、更新及排序列表/字典的优化方案咨询

具体需求 #

• 需对多个自定义类对象按其整数类型的Z属性排序，优先考虑字典存储，若列表性能更优也可采用
• 对象每秒需更新60次，任意帧中任意对象的Z属性都可能变化，需随之重新排序
• 偶尔会添加或移除对象，但优化重点是Z值变化后的排序调整操作
• 支持每次仅更新单个对象或其Z值，若有快速调整该对象排序位置的方法也可采用

已有尝试与疑问 #

• 曾考虑用堆（heap）但不适用，得到的替代方案建议包括B树、AVL树、红黑树、跳表及Python Sorted Containers，但不确定是否适配当前场景
• 尝试过通过循环将单个对象移动到正确Z值位置，但该方法比原生sorted()函数排序整个列表慢得多，以下是性能测试代码：

import random
from statistics import mean
import time


class Object:
    def __init__(self):
        self.Z = random.randint(0, 1000000)
    def __repr__(self):
        return str(self.Z)
    def __str__(self):
        return str(self.Z)

# 先创建已排序的列表
list_base = [Object() for i in range(10000)]
sorted_list = sorted(list_base, key=lambda obj: obj.Z)

# 创建一个Z值大于所有现有对象的新对象，用于测试
new_obj = Object()
new_obj.Z = 1000001

# 存储性能测试的时间结果
results_native = []
results_custom = []

# 多次运行性能测试
for i in range(200):
    # 将新对象插入列表开头
    index = 0
    sorted_list.insert(index, new_obj)
    
    # 原生sorted方法测试
    start_time = time.time()
    sorted_list = sorted(sorted_list, key=lambda obj: obj.Z)
    finish_time_1 = time.time() - start_time
    results_native.append(finish_time_1)
    
    # 将对象移回开头，重复测试
    sorted_list.insert(0, sorted_list.pop(-1))
    
    # 自定义循环调整位置测试
    start_time = time.time()
    index += 1
    while not index >= len(sorted_list) and sorted_list[index].Z <= new_obj.Z:
        index += 1
    sorted_list.insert(index - 1, sorted_list.pop(0))
    finish_time_2 = time.time() - start_time
    results_custom.append(finish_time_2)

print("原生sorted平均耗时:", mean(results_native))
print("自定义循环平均耗时:", mean(results_custom))

问题 #

是否存在更高效的排序方法适配我的特定场景？若有，基础实现的示例代码是什么？

内容的提问来源于stack exchange，提问作者Lion In A Box