Найти K самых частых IP в огромном логе за O(n log K)
У вас очень большой access.log (N строк, IP клиента в первом поле), и нужно вернуть K самых частых IP, где K мал относительно числа различных IP. Полная сортировка всех уникальных IP — это O(U log U); нужно лучше.
Ограничения: цель — O(N log K) время и O(U + K) память; здесь можно использовать язык программирования. Реализуйте функцию ниже.
def top_k_ips(path: str, k: int) -> list[str]:
# ваш код здесь
...Напишите реализацию.
Сосчитайте частоты в хеш-таблице за один проход O(N), затем держите min-heap размера K по счётчикам: добавляйте каждую пару (count, ip), и как только куча превысит K — извлекайте наименьший. Каждая операция кучи O(log K), так что отбор по U различным IP — это O(U log K) ≤ O(N log K). В куче остаются K наибольших; отсортируйте лишь эти K для итогового порядка. Это лучше сортировки всех уникальных за O(U log U).
- ✗Брать max-heap размера K вместо min-heap — извлекать нужно наименьший
- ✗Сортировать все уникальные IP (O(U log U)), когда нужны лишь top-K
- ✗Забывать про проход подсчёта O(N) и пытаться класть в кучу сырые строки
- →Почему хранение K наибольших требует min-heap, а не max-heap?
- →Как адаптировать это, когда даже счётчики различных IP не влезают в память?
Решение
Две стадии: подсчёт частот хеш-таблицей, затем ограниченная куча для отбора top-K без сортировки всех различных IP.
import heapq
from collections import Counter
def top_k_ips(path: str, k: int) -> list[str]:
counts = Counter()
with open(path) as f:
for line in f: # O(N) single pass
ip = line.split(" ", 1)[0]
counts[ip] += 1
# min-heap of size K over (count, ip): the smallest sits at the root
heap: list[tuple[int, str]] = []
for ip, c in counts.items(): # O(U) items
if len(heap) < k:
heapq.heappush(heap, (c, ip))
elif c > heap[0][0]:
heapq.heappushpop(heap, (c, ip)) # O(log K)
# heap holds the K largest; order them descending for output
return [ip for _, ip in sorted(heap, reverse=True)]Почему min-heap. Нужны K наибольших счётчиков. Min-heap размера K держит в корне наименьший из текущих top-K; когда приходит больший счётчик, мы вытесняем этот корень. Выжившие — ровно K наибольших. Max-heap выдавал бы глобальный максимум, а это не тот элемент, который нужно вытеснять.
Сложность. Подсчёт — O(N). Отбор делает O(U) операций кучи, каждая O(log K), итого O(U log K) ≤ O(N log K). Память — O(U) на карту плюс O(K) на кучу. Это обгоняет сортировку всех U различных IP за O(U log U), когда K ≪ U.
