在Python中维护访问计数排序列表的有效方法

Question

假设我有一个对象列表。（现在在一起：“我有一个对象列表。”）在我正在编写的Web应用程序中，每次有请求进入时，我都会根据未指定的标准挑选出这些对象中的一个，并用它来处理请求。基本上是这样的：

def handle_request(req):
    for h in handlers:
        if h.handles(req):
            return h
    return None

假设列表中对象的顺序不重要，则可以通过对列表进行排序以使最常用（或最近使用）的对象位于最前面来减少不必要的迭代。我知道这无关紧要-它只会在应用程序的执行时间上产生微小的，无法检测的差异-但是调试其余代码会使我发疯，所以我需要分心:)所以我出于好奇而问：按每个处理程序被选择的次数降序排序的最有效方法是什么？

显而易见的解决方案是创建handlers一个(count, handler)成对的列表，每选择一个处理程序，就增加计数并重新使用该列表。

    def handle_request(req):
        for h in handlers[:]:
            if h[1].handles(req):
                h[0] += 1
                handlers.sort(reverse=True)
                return h[1]
        return None

但是由于最多只有一个元素发生故障，而且我知道它是哪一个，因此似乎应该可以进行某种优化。标准库中是否有某些特别适合此任务的内容？还是其他一些数据结构？（即使未在Python中实现）还是应该/应该做一些完全不同的事情？

Answer 1

Python的sort算法timsort非常神奇：如果您列出的内容除一个元素之外被排序，它将本质上（发现并）使用该事实，并O(N)及时进行排序。（Java专家Josh Bloch对timsort的性能特征的介绍给人留下了深刻的印象，以至于他开始在笔记本电脑上为Java进行编码-它应该很快就会成为Java的标准类型）。我只是在每次定位和增加计数之后进行排序，并且非常怀疑其他方法是否能击败timsort。

编辑：首先想到的第一个选择是，可能只是将您刚刚增加计数的项目“向上移动”。但首先，要进行一些优化以避免复制handlers...）：

def handle_request(req):
    for h in handlers:
        if h[1].handles(req):
            h[0] += 1
            handlers.sort(reverse=True)
            break
    else:
        return None
    return h[1]

现在，“上移”变体

def handle_request(req):
    for i, h in enumerate(handlers):
        if h[1].handles(req):
            h[0] += 1
            for j in reversed(range(i+1)):
                if handlers[j][0] <= h[0]:
                    break
            if j < i:
                handlers[j+1:i+1] = handlers[j:i]
                handlers[j] = h
            break
    else:
        return None
    return h[1]

我可以想象使用这种方法可以节省一些时间的访问模式-例如，如果分布偏斜，以至于大多数匹配都位于处理程序[0]中，那么除了一次比较外，这几乎不会做任何工作（而其中sort需要大约N个）即使在最好的情况下）。如果没有您的访问模式的代表性样本，我将无法确认或反驳！-）