有没有更快的方法来快速修改、更新和排序列表或字典？

Question

我试图找出除了本机“排序”函数之外，是否有更快的方法在 python 中排序和修改列表。

具体细节： 我有来自自定义类的多个对象，我想根据它们的 Z 属性（一个整数值）对其进行排序。理想情况下，对象存储在字典中，但如果列表性能更高，也可以使用。它们每秒更新 60 次。在任何帧中，任何对象的任何 Z 属性都可能发生变化，并且列表需要相应地进行排序。可能会不时添加或删除对象，但优化尤其针对对象 Z 值更改后对列表/字典进行排序。

我还可以一次更新一个对象或一个 Z 值更改的列表，并且仅更改该对象在排序中的位置（如果有一种快速方法可以做到这一点）。

我询问heaps是否是一个很好的解决方案，但事实并非如此。 在那篇链接的文章中，我得到了有关 B 树、AVL 树、红黑树、跳过列表和 Python 排序容器的建议，但我不确定它们对我的特定用例是否有帮助。

我尝试通过列表循环单个对象，直到它到达正确的 Z 位置，但该方法也比使用本机排序（）命令对整个列表进行排序要慢得多。我在下面粘贴了该测试的示例代码。

有谁知道是否有更快更有效的方法来针对我的特定用例进行排序？如果是这样，基本实现的示例代码是什么？

示例代码（此代码仅用于性能测试，并不意味着完全优化）:

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)

# Creating a sorted list first:
list_base = [Object() for i in range(10000)]
sorted_list = sorted(list_base, key = lambda name: name.Z)

# New object that will be added to the beginning of the list with a higher Z value than the others:
new_obj = Object()
new_obj.Z = 1000001

# Store the timing results in lists for performance testing:
results_native = []
results_custom = []

# Run performance test multiple time:
for i in range(200):
    # inserting new object at the beginning of the list:
    # current index:
    index = 0
    sorted_list.insert(index, new_obj)
    # Sort method native:
    start_time = time.time()
    sorted_list = sorted(sorted_list, key = lambda name: name.Z)
    finish_time_1 = time.time() - start_time

    results_native.append(finish_time_1)
    # Inserting the object back to the beginning of the list to repeat the test:
    sorted_list.insert(0, sorted_list.pop(-1))

    # Sort method Custom looping:
    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("Native finish time:", mean(results_native))
print("Custom loop finish time:", mean(results_custom))

Answer 1

性能很重要。 您将以 60 FPS 的速度扫描排序列表中的每个显示帧。 您将每帧进行 K 次对象更新，其中 K > 1。

Big-Oh 表示法隐藏了一个常数因子。 对于用 C 实现的代码来说，这只是一个小因素， 对于 python 解释的字节码来说，还有一个更大的因素。

有“增量”和“排序一切”的方法 获得排序列表。 既然一万已经到了“小”的边缘 数量，您也许可以批量进行 K 个更新 然后每帧对所有内容进行一次排序，成本为 O(N log N)。

from sortedcontainers import SortedList

更有吸引力的方法是逐步 每次更新后保持列表始终排序。 一个非常好的 C 实现很乐意让你的容器保持排序。 对于 K 次更新，成本为 K × O(log N)。 注意 K << N.

您可能仍然更喜欢使用每帧批处理，因为 .更新（可迭代） （在 C 中）可以比字节码更快地破解 K 项

for i in range(K):

可以。

请注意，还有一个 排序字典 如果你愿意的话。