Python heapq по сравнению со сложной сложностью и производительностью
Я относительно новичок в python (используя синтаксис v3.x) и буду благодарен за заметки о сложности и производительности heapq vs. sorted.
Я уже реализовал решение на основе heapq для жадного алгоритма «найти лучший график работы». Но потом я узнал о возможности использования «отсортированного» вместе с operator.itemgetter () и reverse = True.
К сожалению, я не мог найти никакого объяснения ожидаемой сложности и / или производительности «отсортированного» по сравнению с heapq.
Если вы используете двоичную кучу, чтобы поместить все элементы в порядок, то вещь, которую вы делаете, – это, в основном, heapsort . Это медленнее, чем сортировка algorightm в sorted функции, кроме того, что реализация является чистым python.
heapq быстрее, чем sorted в случае, если вам нужно добавлять элементы «на лету», т.е. дополнения и вставки могут появляться в неуказанном порядке. Добавление нового элемента, сохраняющего внутренний порядок в любой куче, быстрее, чем обращение к массиву после каждой вставки.
sorted выполняется быстрее, если вам нужно будет восстановить все элементы в порядке позже.
Единственная проблема, с которой они могут конкурировать – если вам нужна часть самых маленьких (или самых больших) элементов из коллекции. Хотя в этом случае есть специальные алгоритмы , будет ли heapq или sorted быстрее, это зависит от размера исходного массива и части, которую вам нужно извлечь.
heapq реализуется как двоичная куча . Ключевыми моментами, которые нужно отметить для двоичных куч , а также расширения, heapq :
- Поиск не поддерживается
- Вставки – это постоянное время в среднем
- Исключения составляют O (log n) время в среднем
Дополнительная информация о двоичной куче, описанная здесь: http://en.wikipedia.org/wiki/Binary_heap
Хотя heapq – это структура данных, которая обладает свойствами двоичной кучи , использование sorted – это другое понятие. sorted возвращает отсортированный список , так что это по существу результат, тогда как heapq – это структура данных, с которой вы постоянно работаете, что можно, опционально, сортировать с помощью sorted .
Additonal sorted информация здесь: https://docs.python.org/3.4/library/functions.html#sorted
Что конкретно вы пытаетесь достичь?
Ответ на комментарий OP:
Почему, по-вашему, вам нужен heapq ? Бинарная куча – это специализированная структура данных , и в зависимости от ваших требований это, скорее всего, не требуется.
Вы, кажется, очень обеспокоены работой, но непонятно, почему. Если что-то «плохой исполнитель», но его суммарное время не имеет значения, то на самом деле это не имеет значения в большей картине. В общем случае, dict или list будут выполняться в обычном порядке. Почему вы специально думаете, что нужен heapq ?
Я задаюсь вопросом, не является ли это ситуацией, не имеющей отношения к совершенству.
Запись Python с использованием расширений C – это случайный вариант использования, зарезервированный для случаев, когда производительность действительно является серьезной проблемой. (т. е. может быть лучше использовать, скажем, XML- синтаксический анализатор, который является расширением C, чем что-то, что является чистым Python, если вы имеете дело с большими файлами, и если производительность ваша главная проблема).
Что касается сложного продолжения игры со структурным случаем: можно ли быстрее сортировать с отсортированными и добавлять элементы через .append () :
Я все еще не понимаю, что здесь используется. Как я уже упоминал выше, sorted и heapq – это действительно две разные концепции.
Каков прецедент, для которого вас так беспокоит производительность? (Отсутствие других факторов, которые еще не указаны, я думаю, что вы можете чрезмерно подчеркнуть важность наилучшей производительности вашего кода здесь.)