[Python] Как получить указанное число max или min чисел из списка. heapq vs list.sort()+slice. Нужно ли это начинающему?

Я, наверное, как и многие увлекающиеся программированием люди подписан на некоторые телеграмм-каналы, ВК-сообщества, YouTube-каналы.

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

heapq - модуль обеспечивающий реализацию алгоритма очереди кучи, также известного как алгоритм очереди приоритетов.

Источник: https://docs.python.org/3/library/heapq.html

Все как обычно, прочитал, запомнил, интересная идея, все решается в одну строчку. Но побудило меня написать данную статью не решение задачи с использованием данного модуля, а комментарии к данному посту.

Зачем для решения данной задачи прибегать к теме куч и не проще ли воспользоваться сортировкой, а начинающему это пока рано.

И я решил проверить, а что лучше применить для решения подобного рода задачи и почему.

Ctrl+C, Ctrl+V в помощь.

Цикл отрабатывает 8 итераций, в каждой итерации количество элементов m списка берется как 10 в степени n, где n - номер итерации цикла. После чего формируется отсортированный список (!) от 1 до m.

Далее фиксируется время начала извлечения из исходного списка указанного числа минимальных и максимальных элементов списка, с помощью модуля heapq. После чего фиксируется время окончания данных операций и выводится результат.

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

Результаты

Время отработки heapq и list.sort()+slice на изначально отсортированном списке.

Время отработки heapq и list.sort()+slice на изначально отсортированном списке. Продолжение.

Что?

Как так? Такой крутой модуль и проиграл на любом размере списка.

В информатике ку́ча (англ. heap) — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами).

Источник: https://ru.wikipedia.org/wiki/Куча_(структура_данных)

Таким образом, применение heapq.nlargest(n, iterable, key=None) на уже отсортированном списке не актуально, в нашем случае будет построена min-куча в виде не сбалансированного дерева. Левое дерево будет пусто на каждом уровне, будут только правые деревья, таким образом, дерево вырождается в список, идущий вправо. И время поиска максимального элемента будет в худшем случае за O(n), где n - длина списка.

А что если изначальный список перетасовать?

Ctrl+C, Ctrl+V в помощь.

Код работает, как описано выше, только список после генерации перетасовывается:

shuffle(lst)

Результаты

Время отработки heapq и list.sort()+slice на изначально перетасованном списке.

Время отработки heapq и list.sort()+slice на изначально перетасованном списке. Продолжение.

Ну вот

А вот здесь ситуация меняется: модуль heapq начинает выигрывать, когда размер списка увеличивается до 1 000 000 элементов. Здесь уже строиться более сбалансированное дерево и операции извлечения минимальных и максимальных элементов выполнятся в худшем случае за время O(log n). Значит применение данного модуля имеет место быть.

Вывод

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

Спасибо за потраченное время на прочтение.

Строго не судите.

За уместные комментарии буду признателен.