Десять максимумов из двух миллионов чисел: чем nlargest отличается от sorted
В списке data два миллиона целых чисел. Нужно получить 10 самых больших. Рассматриваем три варианта:
import heapq
a = sorted(data)[-10:]
b = heapq.nlargest(10, data)
heapq.heapify(data)
c = [heapq.heappop(data) for _ in range(10)] # 10 минимумов
Какое утверждение о стоимости верно?
- `sorted(data)[-10:]` асимптотически лучший вариант: сортировка в CPython реализована на C, а nlargest — на Python
- `heapify` плюс 10 извлечений стоит O(k log n) целиком, потому что построение кучи из готового списка бесплатно
- `heapq.nlargest(k, data)` работает за O(n log k) и держит в памяти только k элементов
- `nlargest` и `sorted(...)[-k:]` совпадают по асимптотике — внутри nlargest та же полная сортировка