Какие есть способы сортировки больших файлов, не помещающихся в память?

Когда файл слишком велик для загрузки в оперативную память целиком, стандартные алгоритмы сортировки (например, быстрая сортировка) неприменимы. Решением является использование алгоритмов внешней сортировки, которые активно работают с диском, организуя данные так, чтобы итоговый файл был отсортирован.

Основной алгоритм: Сортировка слиянием

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

• Фаза разбиения и внутренней сортировки: Исходный файл читается порциями, которые помещаются в память (например, по 1 ГБ при 16 ГБ ОЗУ). Каждая порция сортируется в памяти с помощью эффективного алгоритма (например, Timsort в Python) и записывается на диск как отдельный отсортированный временный файл ("серия" или "run").
• Фаза слияния: Отсортированные серии сливаются в один файл. Наиболее распространено k-путевое слияние. Одновременно открываются k серий, из каждой читается по одному элементу (или небольшому блоку). С помощью структуры данных "мини-куча" (heap) постоянно выбирается минимальный (или максимальный) элемент из всех доступных и записывается в итоговый файл. Когда элемент из какой-либо серии записан, из той же серии читается следующий элемент.

Практическая реализация (упрощённый пример на Python)

Ниже приведён схематичный код, иллюстрирующий первую фазу и идею слияния. В реальности нужно управлять буферами ввода/вывода для эффективности.

import heapq
import os
import tempfile

def external_sort(input_filename, output_filename, chunk_size=1000):
    """Упрощённая внешняя сортировка чисел."""
    # Фаза 1: Создание отсортированных чанков
    temp_files = []
    with open(input_filename, 'r') as infile:
        chunk = []
        while True:
            line = infile.readline()
            if not line:
                break
            chunk.append(int(line.strip()))
            if len(chunk) >= chunk_size:
                chunk.sort()
                temp_file = tempfile.NamedTemporaryFile(mode='w+', delete=False)
                temp_file.writelines(f"{num}\n" for num in chunk)
                temp_file.close()
                temp_files.append(temp_file.name)
                chunk = []
        # Остаток
        if chunk:
            chunk.sort()
            temp_file = tempfile.NamedTemporaryFile(mode='w+', delete=False)
            temp_file.writelines(f"{num}\n" for num in chunk)
            temp_file.close()
            temp_files.append(temp_file.name)

    # Фаза 2: k-путевое слияние (здесь k = len(temp_files))
    # Открываем все временные файлы для чтения
    files = [open(fname, 'r') for fname in temp_files]
    # Создаём кучу из первых чисел каждого файла
    heap = []
    for i, f in enumerate(files):
        num = f.readline()
        if num:
            heapq.heappush(heap, (int(num.strip()), i))

    with open(output_filename, 'w') as outfile:
        while heap:
            val, file_idx = heapq.heappop(heap)
            outfile.write(f"{val}\n")
            # Берём следующее число из того же файла
            next_num = files[file_idx].readline()
            if next_num:
                heapq.heappush(heap, (int(next_num.strip()), file_idx))

    # Закрываем и удаляем временные файлы
    for f in files:
        f.close()
    for fname in temp_files:
        os.unlink(fname)

# Пример вызова (предполагается, что input.txt содержит по одному числу на строку)
# external_sort('input.txt', 'sorted_output.txt', chunk_size=100000)

Этот пример демонстрирует принцип, но в реальных системах (например, в утилите sort в Unix) используются более сложные оптимизации: буферизация ввода/вывода, учёт доступной памяти, выбор оптимального k, работа с разными типами данных.

Другие подходы и оптимизации

• Замена-выбор (Replacement Selection): В фазе создания серий можно генерировать серии, размер которых в среднем вдвое превышает доступную память, что уменьшает их общее количество.
• Каскадное и многофазное слияние: Более сложные схемы слияния, которые минимизируют операции чтения/записи.
• Использование MapReduce: В распределённых системах (Hadoop, Spark) задача сортировки разбивается на множество узлов, которые сортируют свои части данных, а затем происходит глобальное слияние.
• Сортировка с помощью базы данных: Загрузка данных в СУБД (например, PostgreSQL) и использование ORDER BY с правильными индексами позволяет делегировать сортировку оптимизированному движку базы данных.

Вывод: Внешняя сортировка слиянием — фундаментальный метод для обработки данных, не помещающихся в память. Её стоит применять при работе с большими лог-файлами, дампами данных, в ETL-процессах и в любых ситуациях, где требуется упорядочить огромные объёмы информации на диске. Оптимизации алгоритма позволяют эффективно использовать ресурсы диска и памяти.