読者です 読者をやめる 読者になる 読者になる

PythonのPriorityQueueが気に入らない

タイトルの通りである.

PythonのPriorityQueueが気に入らない.

まず,PythonのPriorityQueueクラスは,heapqをクラスにしたぐらいの存在にしか見えない.
(引数でheapqと指定してるのだけど,それ以外の使い道が思いつかない)
(本当はスレッドセーフとかいう機能もあるけど)

しかもmin-heapなので,Priorityと銘打っておきながら一番小さい優先度のものから取り出しやがるのである.
まぁ,そこは優先度の定義にもよるので,許すとしよう.

しかし,最も問題があるのは,「昇順・降順が自分で決められない」ことである.

え? __le__を定義すればいいって?
>>> x = Test()
>>> x.__le__ = lambda x, y: x <= y
>>> x = 1
>>> x.__le__ = lambda x, y: x <= y
Traceback (most recent call last):
  File "", line 1, in 
AttributeError: 'int' object has no attribute '__le__'


うーん,built-inなオブジェクト(list, tuple, map)や,基本型でそれをしようとするのはとても面倒なのです.
自分で継承して,新しいクラスを作らなくてはいけません.

それはだるい.

私のDebian(sqeeze)にはPython3.1と2.6が入っています.
そこで,Python3.1の/usr/lib/python3.1/queue.pyを改変して,Python2.6用のライブラリにしてみます.

具体的には,/usr/lib/python3.1/queue.pyをコピーして,PriorityQueueクラスを以下のように変えます.

class PriorityQueueItem:
  def __init__(self, item, lefunc):
   self.item = item
   self.lefunc = lefunc
  def __le__(self, o):
   return self.lefunc(self.item, o.item)

class PriorityQueue(Queue):
 '''Variant of Queue that retrieves open entries in priority order.
 '''
 def __init__(self, maxsize=0, lefanc=None):
  self.lefanc = lefanc
  Queue.__init__(self, maxsize)
 
 def _init(self, maxsize):
  self.queue = []

 def _qsize(self, len=len):
  return len(self.queue)

 def _put(self, item, heappush=heapq.heappush):
  if self.lefanc is None:
   heappush(self.queue, item)
  else:
   heappush(self.queue, PriorityQueueItem(item, self.lefanc))

 def _get(self, heappop=heapq.heappop):
  if self.lefanc is None:
   return heappop(self.queue)
  else:
   return heappop(self.queue).item

オーバーヘッドとか気にする言語じゃないし,そもそもqueueは普通に使ったらスレッドセーフとかいうオーバーヘッドあるしこれでおkでしょ.

使い方
#!/usr/bin/env python
#-*- coding:utf-8 -*-
import queue
def test(q):
 total = 0
 for i in xrange(100):
  q.put(i)
 while q.qsize() > 1:
  x = q.get() + q.get()
  total += x
  q.put(x)
 return total
print test(queue.PriorityQueue(lefanc=lambda x, y: x <= y))
print test(queue.PriorityQueue(lefanc=lambda x, y: x >= y))

ドキュメントには,(priority, value)のタプルを突っ込めって書いてあって,逆数にしたり負にしたりして突っ込めばいいような気がしてきたけど気にしない.