6

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()
4

1 回答 1

19

唯一的问题heapq是它没有key像标准库中的其他所有功能一样提供功能。（如果你好奇为什么，Raymond Hettinger 在这封电子邮件中解释。他是对的，heapq不能提供与其他排序函数相同的接口——但原因不会影响你的用例，key只是在哪里lambda x: -x。）

通常的解决方法是装饰堆取消装饰。也就是说，将值的修改版本放入按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)

…</p>

如果您快速浏览一下 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

但是您不想在实际代码中这样做。

于 2013-01-07T04:07:12.680 回答