在Python中高效维护访问计数的排序列表

Question

假设我有一个对象列表。（大家一起说：“我有一个对象列表。”）在我写的这个网页应用中，每当有请求进来时，我会根据一些不明确的标准，从这个列表中挑选出最多一个对象来处理这个请求。基本上就是这样：

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

虽然 timsort 算法很神奇，但使用 list.sort() 并不是个好主意，因为它至少需要每次比较相邻的两个元素，来确保列表是排好序的。

使用优先队列（也就是 Python 的 heapq 模块）对很多类似的问题来说是个不错的解决方案，但对于你的应用来说并不理想，因为在遍历 heapq 的时候开销比较大。

令人惊讶的是，针对你的情况，最好的方法是使用像冒泡排序这样的简单算法。因为除了你刚调整的那个元素，其他的元素都是有序的，所以唯一可能发生的就是那个元素在列表中稍微向上移动一点。而且你每次只增加一个，所以它不会移动太远。只需要把它和前一个元素比较一下，如果顺序不对就交换它们。可以这样做：

def handle_request(req):
    for (i, h) in enumerate(handlers):
        if h[1].handles(req):
            h[0] += 1
            while i > 0 and handlers[i][0] > handlers[i-1][0]:
                handlers[i-1], handlers[i] = handlers[i], handlers[i-1]
                i -= 1
            return h[1]
    return None

（当然，如果多个线程同时访问处理器数组，你需要进行某种同步处理。）

Answer 2

听起来这个问题适合用优先队列来解决（也叫做堆）。在Python中，有一个标准库叫做heapq，它实现了优先队列。简单来说，你可以保持一个树状结构或堆，把最常用的东西或者最近使用的东西放在最上面。

Answer 3

Python的排序算法叫做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]

我可以想象一些访问模式，在这种情况下，这种方法可能会节省一些时间——例如，如果数据分布非常不均，大多数访问都集中在handlers[0]，那么这只需要进行一次比较（而sort即使在最佳情况下也需要大约N次比较）。没有你访问模式的代表性样本，我无法确认或否定这一点！-)