python topN max heap, use heapq o self implement?

hay heapq en python, para uso general. Quiero grabar topN (0 ~ 20) para 10e7 registros.

si usa heapq, debe usar ‘-‘ para traducir max a min; y registrando un número mínimo de fondos, para llamar a heapq.heappushpop ()

¿Debo usar heapq o auto implementar un montón (quizás con errores o menos eficiente)?

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

El único problema con heapq es que no proporciona una función key como lo hace todo lo demás en stdlib. (Si tiene curiosidad por saber por qué, Raymond Hettinger lo explica en este correo electrónico . Tiene razón en que heapq no pudo proporcionar la misma interfaz que otras funciones de clasificación, pero las razones no afectan su caso de uso, donde key sería simplemente lambda x: -x .)

La solución habitual es decorar-amontonar-decorar. Es decir, ponga una versión modificada de sus valores en el montón que ordena por key . Normalmente, esto significa uno de los siguientes:

  • Almacenar key(x) lugar de x , y luego acceder a unkey(value) lugar de value (suponiendo que la key es reversible).
  • Almacenar (key(x), x) lugar de x , y luego acceder al value[1] . (Esto puede romper la estabilidad, pero heapq no promete estabilidad de todos modos).
  • Escribir una clase contenedora que implemente un método __le__ personalizado, luego almacenar Wrapper(x) lugar de x y acceder a value.value lugar de value .

En su caso, la función clave es reversible. Entonces, simplemente almacene -x , y acceda -value . Eso es tan trivial como la decoración.

Aún así, independientemente de lo simple que sea, probablemente deberías escribir una envoltura, o la estropearás en algún momento. Por ejemplo, podría escribir un maxheap que envuelva el minheap en un heapq como este:

 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) 

… y así sucesivamente para cualquier otra función que necesite. Puede ser un poco molesto, pero es mucho menos trabajo que implementar todo desde cero.

Mientras esté en ello, es posible que desee envolver el montón en una API orientada a objetos para que pueda hacer heap.push(x) lugar de heapq.heappush(heap, x) , etc.

 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) 

Si echa un vistazo rápido a las recetas en ActiveState o los módulos en PyPI, debería descubrir que otros ya han hecho la mayor parte del trabajo por usted.

Alternativamente, puede copiar y pegar la fuente heapq (es Python puro) como maxheapq.py y simplemente reemplazar la función cmp_lt con su opuesto. (Por supuesto, si está haciendo eso, es probablemente igual de fácil, y ciertamente mucho más claro, modificar cmp_lt para tomar un argumento key en primer lugar, y modificar todas las demás funciones para pasar la key , teniendo en cuenta que ya no será aplicable en general, ya que no puede ofrecer la garantía habitual de que la key solo se llama una vez.)

Si realmente quieres vivir peligrosamente (no deberías), incluso podrías hacerlo:

 import heapq def cmp_gt(x, y): return y < x if hasattr(y, '__lt__') else not (x <= y) heapq.cmp_lt = cmp_gt 

Pero no quieres hacer eso en código real.