Для чего вы будете использовать модуль Python heapq в реальной жизни? - PullRequest
Новая
       36

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

13 голосов
/ 25 декабря 2011

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

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

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

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

Ответы [ 3 ]

19 голосов
/ 25 декабря 2011

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

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

Документы 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]
6 голосов
/ 25 декабря 2011

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

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

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

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

3 голосов
/ 25 декабря 2011

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

...