Top N Sorter in Python

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

 

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

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

 

コード

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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