Миллион наименьших чисел

Решение

Понимание задачи

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

Оптимальный алгоритм: Max Heap (Приоритетная очередь)

Лучший подход — использовать Max Heap размером 1 миллион элементов:

import heapq

def find_million_smallest(filename):
    max_heap = []  # Будем использовать -x для max heap
    k = 1_000_000
    
    # Читаем файл потоком
    with open(filename, r) as f:
        for line in f:
            num = int(line.strip())
            
            # Если heap меньше k, добавляем элемент
            if len(max_heap) < k:
                heapq.heappush(max_heap, -num)  # Отрицание для max heap
            # Иначе сравниваем с максимальным элементом
            elif num < -max_heap[0]:
                heapq.heapreplace(max_heap, -num)
    
    # Преобразуем обратно и сортируем
    result = sorted([-x for x in max_heap])
    return result

Анализ сложности

Временная сложность: O(n log k)

• n = 1 миллиард (количество элементов в файле)
• k = 1 миллион (размер heap)
• Для каждого элемента: O(log k) операция вставки/замены
• Итого: 10^9 × log(10^6) ≈ 10^9 × 20 ≈ 2×10^10 операций

Пространственная сложность: O(k)

• Храним максимум k элементов в памяти
• O(1 миллион) ≈ 4 МБ для целых чисел (очень эффективно)

Почему именно Max Heap?

1. Эффективность памяти: храним только 1М элементов вместо 1Б
2. Потоковая обработка: читаем файл строка за строкой, не загружая в память
3. O(log k) операции: вставка и удаление максимального элемента быстры
4. Инвариант: в heap хранятся k наименьших элементов, которые встречались до текущего момента

Альтернативные подходы

Quickselect (неоптимально)

• Требует предварительной загрузки всех данных в память
• O(n) в среднем, но O(n²) в худшем случае
• Не подходит для потоковой обработки

Сортировка (неоптимально)

• O(n log n) временная сложность
• O(n) память — невозможно загрузить 1Б чисел

Internal Sort с External Merge (для больших данных)

• Разбить файл на части, отсортировать каждую, слить
• Более сложно, но применимо если heap не хватает памяти

Практические оптимизации

import heapq
from typing import List

def find_million_smallest_optimized(filename: str, k: int = 1_000_000) -> List[int]:
    max_heap = []
    
    # Пакетное чтение для скорости
    batch_size = 10000
    batch = []
    
    with open(filename, r) as f:
        for line in f:
            batch.append(int(line.strip()))
            
            if len(batch) == batch_size:
                # Обработка батча
                for num in batch:
                    if len(max_heap) < k:
                        heapq.heappush(max_heap, -num)
                    elif num < -max_heap[0]:
                        heapq.heapreplace(max_heap, -num)
                batch.clear()
        
        # Обработка оставшихся элементов
        for num in batch:
            if len(max_heap) < k:
                heapq.heappush(max_heap, -num)
            elif num < -max_heap[0]:
                heapq.heapreplace(max_heap, -num)
    
    return sorted([-x for x in max_heap])

Выводы

• Вывод №1: Max Heap размером k — оптимальное решение для данной задачи
• Вывод №2: O(n log k) временная сложность с O(k) памятью позволяет обработать 1Б элементов
• Вывод №3: Потоковая обработка файла критична для работы с ограниченной памятью
• Вывод №4: В реальных системах нужно обработать исключения и edge cases (пустой файл, невалидные данные)