Что бы вы использовали модуль heapq Python в реальной жизни?

После прочтения Guido Сортировка миллиона 32-разрядных целых чисел в 2 МБ ОЗУ с использованием Python, я обнаружил модуль heapq, но концепция довольно абстрактно для меня.

Одна из причин заключается в том, что я не понимаю концепцию кучи полностью, но я понимаю, как Гвидо использовал ее.

Теперь, помимо своего безумного примера, что бы вы использовали модуль heapq для?

Всегда ли это связано с сортировкой или минимальным значением? Это только то, что вы используете, потому что оно быстрее, чем другие подходы? Или вы можете делать действительно элегантные вещи, без которых вы не можете обойтись?

Ответ 1

heapq module обычно используется для реализации очередей приоритетов.

Вы видите очереди приоритетов в планировщиках событий, которые постоянно добавляют новые события и должны использовать кучу, чтобы эффективно находить следующее запланированное событие. Вот некоторые примеры:

Python собственный sched модуль: http://hg.python.org/cpython/file/2.7/Lib/sched.py#l106
Tornado веб-сервер: https://github.com/facebook/tornado/blob/master/tornado/ioloop.py#L260
Twisted интернет-серверы: http://twistedmatrix.com/trac/browser/trunk/twisted/internet/base.py#L712

В документах heapq включены примечания о реализации очереди приоритетов, которые касаются общих случаев использования.

Кроме того, кучи отлично подходят для реализации частичных сортировок. Например, heapq.nsmallest и heapq.nlargest может быть гораздо более эффективная память и делает намного меньше сравнений, чем полный сорт, за которым следует срез:

>>> from heapq import nlargest
>>> from random import random
>>> nlargest(5, (random() for i in xrange(1000000)))
[0.9999995650034837, 0.9999985756262746, 0.9999971934450994, 0.9999960394998497, 0.9999949126363714]

Ответ 2

Сравнивая это с самобалансирующимся двоичным деревом, куча, похоже, не сильно вас впечатляет, если вы просто посмотрите на сложность:

Вставка: O (logN) для обоих
Удалить максимальный элемент: O (logN) для обоих
Построить структуру из массива элементов O (N) для кучи, O (N log N) для двоичного дерева.

Но в то время как для двоичного дерева требуется, чтобы каждый node указывал своим детям на эффективность, куча хранит свои данные, плотно упакованные в массив. Это позволяет хранить гораздо больше данных в фиксированном объеме памяти.

Итак, для случаев, когда вам требуется только вставка и максимальное удаление, куча идеальна и может часто использовать вдвое меньше памяти, чем самобалансирующееся двоичное дерево (и намного проще реализовать, если вам нужно). Стандартный прецедент - это очередь приоритетов.

Ответ 3

Это было случайное открытие меня, пытаясь понять, как я могу реализовать Counter-модуль в Python 2.6. Просто посмотрите на реализацию и использование collections.Counter. Это фактически реализуется через heapq.