Top N Sorter in Python

Python: トップNソートの実装

 

ソート可能な iterable に対して、降順の上位 N件のソート結果を取得したい。

heapq を使えば効率が良さそうだ。

 

コード

import heapq


class TopNSorter(object):
    def __init__(self, limit):
        self._heap = []
        self.limit = limit

    def insert(self, item):
        if len(self._heap) == self.limit:
            heapq.heappushpop(self._heap, item)
        else:
            heapq.heappush(self._heap, item)

    def result(self):
        h = self._heap[:]
        buf = []
        while h:
            buf.insert(0, heapq.heappop(h))
        return buf

 

実行例

>>> s = TopNSorter(5)
>>> s.result()
[]
>>> s.insert(10)
>>> s.result()
[10]
>>> s.insert(20)
>>> s.result()
[20, 10]
>>> s.insert(10)
>>> s.result()
[20, 10, 10]
>>> s.insert(5)
>>> s.result()
[20, 10, 10, 5]
>>> s.insert(30)
>>> s.result()
[30, 20, 10, 10, 5]
>>> s.insert(15)
>>> s.result()
[30, 20, 15, 10, 10]
>>> s.insert(10)
>>> s.result()
[30, 20, 15, 10, 10]
>>> s.insert(25)
>>> s.result()
[30, 25, 20, 15, 10]
>>> s.insert(1)
>>> s.result()
[30, 25, 20, 15, 10]

 

Related Posts

• mog project: Top N Sorter in Scala