python topN max heap,使用heapq还是自己实现？

Question

在python中有heapq,用于一般用法.我想为10e7记录录制topN(0~20).

如果使用heapq,应使用' - '将max转换为min; 并记录最小数量的底部,以调用heapq.heappushpop()

我应该使用heapq或自己实现一个堆(可能是错误或效率较低)？

#update

import heapq
class TopN(object):
    """
    v format: (num, value)

    after looking into http://hg.python.org/cpython/file/2.7/Lib/heapq.py, 
    i find heappushpop already optimize, no need bottom value

    feed() can be optimize further, if needed:
        using func object instead of compare len(self.h) each time
    """
    def __init__(self, N):
        self.N = N
        self.h = []        

    def feed(self, v):  
        if len(self.h) < self.N:
            heapq.heappush(self.h, v)
        else:
            heapq.heappushpop(self.h, v)

    def result(self):
        self.h.sort(reverse=True)
        return self.h

def t_topn():
    topn = TopN(10)
    for i in xrange(5):
        topn.feed((i, str(i)))
    res = topn.result()    
    assert sorted(res, reverse=True) == res 

def t_topn_random():
    import random
    topn = TopN(10)
    for i in xrange(100):
        x = random.randint(0, 1e4)
        topn.feed((x, str(x)))
    res = topn.result()    
    assert sorted(res, reverse=True) == res 

if __name__ == '__main__':
    t_topn()
    t_topn_random()

Answer 1

唯一的问题heapq是它不提供key像stdlib中的其他所有功能.(如果你很好奇,Raymond Hettinger在这封电子邮件中解释道.他是对的,heapq无法提供与其他排序功能相同的界面 - 但原因不会影响你的用例,key只会是这样lambda x: -x.)

通常的解决方法是decorate-heap-undecorate.也就是说,将值的修改版本放入按排序排序的堆中key.通常,这意味着以下之一:

• 存储key(x)而不是x,然后访问unkey(value)而不是value(假设key是可逆的).
• 存储(key(x), x)而不是x,然后访问value[1].(这可以打破稳定性,但heapq无论如何都不会保证稳定性.)
• 写实现定制的包装类__le__方法,然后储存Wrapper(x),而不是x和访问value.value代替value.

在您的情况下,关键功能是可逆的.所以,只需存储-x和访问-value.这和装饰一样微不足道.

尽管如此,无论它有多简单,你都应该写一个包装器,否则你会在某些时候搞砸它.例如,您可以像这样写一个maxheap包装minheap heapq:

import heapq
def heapify(x):
    for i in range(len(x)):
        x[i] = -x[i]
    heapq.heapify(x)
def heappush(heap, item):
    heapq.heappush(heap, -item)
def heappop(heap):
    return -heapq.heappop(heap)

......等等您需要的任何其他功能.这可能有点痛苦,但是比从头开始实施整个事情要少得多.

当你在它的时候,你可能想要将堆包装在面向对象的API中,这样你就可以heap.push(x)代替heapq.heappush(heap, x),等等.

import heapq
class MaxHeap(object):
    def __init__(self, x):
        self.heap = [-e for e in x]
        heapq.heapify(self.heap)
    def push(self, value):
        heapq.heappush(self.heap, -value)
    def pop(self):
        return -heapq.heappop(self.heap)

...

如果您快速浏览一下ActiveState的配方或PyPI上的模块,您会发现其他人已经为您完成了大部分工作.

或者,您可以复制并粘贴heapq源(它是纯Python)maxheapq.py,只需将cmp_lt其替换为相反的函数即可.(当然,如果你这样做,那么修改cmp_lt首先进行key论证,并修改所有其他功能以通过key轴承时,它可能同样容易,当然也更清晰,因为它赢了不再是普遍适用的,因为它不能做出通常的保证,key只能被召唤一次.)

如果你真的想要危险地生活(你不应该),你甚至可以将其打包:

import heapq
def cmp_gt(x, y):
    return y < x if hasattr(y, '__lt__') else not (x <= y)
heapq.cmp_lt = cmp_gt

但是你不想在实际代码中这样做.