nlargest и nsmallest; heapq python

Question

Это из любопытства о nmallest и самых крупных методах модуля heapq.py в python.

Я читал (а) here в документах.

В документации не указано, как это делается (nsmalles/nlargest) на любой итерабельной.

Это может быть глупый вопрос, но могу ли я предположить, что эти методы внутренне создают кучу итерируемой структуры данных (может быть, используется метод heapify), а затем возвращать n самых маленьких/наибольших элементов?

Просто хочу подтвердить мой вывод. благодаря!

Answer 1

Алгоритм поиска n самых маленьких или самых больших предметов из итерабельного с помощью N элементов немного сложнее. Видите ли, вы не создаете мини-кучу размера - N, чтобы найти самые маленькие предметы.

Вместо этого, вы делаете меньше, размерно n макс-кучу с первыми n элементов, то не повторяется pushpop операции на нем с остальными элементами из последовательности. Как только вы закончите, вы вытащите предметы из кучи и верните их в обратном порядке.

Этот процесс занимает O(N log(n)) времени (обратите внимание на маленький n) и, конечно, только O(n). Если n намного меньше, чем N, это намного эффективнее, чем сортировка и нарезка.

heapq module содержит чисто-Python реализации этого алгоритма, хотя при импорте, вы можете получить более быструю версию кода, написанного на C вместо (вы можете прочитать the source for that тоже, но это не совсем так дружелюбен, если вы, знать API Python C).