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

python的排序算法, timsort 非常神奇:如果您的列表被排序,除了一个元素,它将本质上(发现和)使用这个事实,排序 O(N) 时间。(Josh Bloch,Java大师,对TimPoT的性能特征的介绍印象深刻,他开始在他的笔记本上为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个)。没有你的访问模式的代表性样本,我不能确认或反驳这一点!-)

听起来像是优先级队列的作业(也就是heapq)。python的优先级队列实现为 heapq 在标准库中。基本上,在树/堆的顶部保留最常用项或最新使用项。

尽管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

(当然,如果多个线程正在访问处理程序数组,则必须进行某种同步。)

我猜所有这些额外的sort()调用都会使您的速度减慢,而不是加快您的速度。我的建议是使用这样的包装器(取自 here )

class Memoize:
    """Memoize(fn) - an instance which acts like fn but memoizes its arguments
    Will only work on functions with non-mutable arguments
    """
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args):
        if not self.memo.has_key(args):
            self.memo[args] = self.fn(*args)
        return self.memo[args]

您可以这样使用它:

handle_request = Memoize(handle_request)

这将导致handle_请求的各种返回值被缓存,并可能实际提供显著的加速。我建议您在应用程序中使用memoize()包装各种函数的时间和时间进行试验,看看它占用了多少内存,以及加快了(或不加快)各种函数的速度。也可以使用类似的方法(例如,有一个memoizing修饰符 here )

下面是我用来解决这个问题的一些代码(虽然现在我读了其他的答案,但我想知道HeapQ是否更好):

class MRUSortedIterable:

    def __init__(self, data):
        self._data = list(data)
        self._i = 0

    def __iter__(self):
        if self._i:  # if previous use had a success, move to top
            self._data[0], self._data[1:self._i+1] = self._data[self._i], self._data[0:self._i]
        for self._i, value in enumerate(self._data):
            yield value
        self._i = 0  # reset on exhaustion (ie failed to find what we wanted)

您可以这样使用它(例如):

MY_DATA = MRUSortedIterable(a_list_of_objects)
...
def handler(criteria):
    for data in MY_DATA:
        if test(data, criteria):
            return data

它会根据需要自动重新排列基础数据,使最新使用的项位于最上面(在处理下一个请求时,重新排列实际上是完成的)。唯一的要求是在成功时停止迭代数据(并使用 全部的 故障数据)。

重要提示:这非常重要 不 线程安全(这可能是两年前Web服务器的一个问题)。但它 是 嗯,很干净…

经过思考,这是MRU,而具有访问计数的heapq将按总使用量排序。因此,它们的性能可能略有不同(如果访问模式不变,heapq可能更好)。