6

一般的な使用のために、Pythonにはheapqがあります。10e7レコードのtopN(0~20)を記録したい。

heapq を使用する場合は、'-' を使用して最大値を最小値に変換する必要があります。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

の唯一の問題は、stdlib の他のすべてが提供するような機能をheapq提供しないことです。key(理由が気になる方は、Raymond Hettinger がこのメールheapqで説明しています。他の並べ替え関数と同じインターフェイスを提供できなかったという彼の意見は正しいですが、その理由はユース ケースには影響しませkeyんlambda x: -x。

通常の回避策は、decorate-heap-undecorate です。つまり、値の変更されたバージョンを でソートするヒープに入れますkey。通常、これは次のいずれかを意味します。

  • key(x)の代わりに保存し、代わりにxアクセスします (可逆であると仮定します)。unkey(value)valuekey
  • (key(x), x)の代わりに保存xしてからアクセスしvalue[1]ます。(これは安定性を損なう可能性がありますが、heapqとにかく安定性を約束するものではありません。)
  • カスタム__le__メソッドを実装するラッパー クラスを作成し、代わりに を保存Wrapper(x)して代わりにアクセスしxます。value.valuevalue

あなたの場合、キー機能は可逆的です。したがって、 を保存-xしてアクセスするだけです-value。それは装飾と同じくらい些細なことです。

それでも、どれだけ単純であっても、おそらくラッパーを作成する必要があります。たとえば、次のようmaxheapに minheap をラップするa を記述できます。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を取るように変更し、他のすべての関数をスルーパスに変更することは、おそらく同じくらい簡単で、確かにより明確です。それが勝ったことに注意してください)一度しか呼び出されない通常の保証を行うことができないため、もはや一般的に適用できません。)keykeykey

あなたが本当に危険な生活をしたいのであれば (そうすべきではありません)、モンキーパッチを適用することもできます:

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 に答える