External Sort

Программа для сортировки большого файла (до 1ТБ) с использованием ограниченного объема оперативной памяти (500МБ).

Решение

Для решения задачи используется алгоритм внешней сортировки, который работает в три этапа:

1. Разбиение исходного файла на части — файл разделяется на небольшие фрагменты, которые могут быть обработаны в памяти (примерно 400МБ).
2. Сортировка каждой части в памяти — каждый фрагмент сортируется и сохраняется обратно на диск.
3. Слияние отсортированных частей — отсортированные фрагменты объединяются в единый выходной файл с использованием алгоритма k-путевого слияния.

Особенности реализации

• Эффективная потоковая обработка данных с использованием Stream API
• Потребление памяти контролируется и не превышает указанного лимита
• Оптимизация дисковых операций для повышения производительности
• Параллельная обработка с использованием worker_threads для сортировки отдельных фрагментов
• Иерархическое слияние для обработки большого количества фрагментов
• Подробная диагностика и отчеты о прогрессе

Требования

• Node.js 14+ (тестировалось на версии 16)
• Достаточно дискового пространства для временных файлов (примерно 2x размер входного файла)

Установка и запуск

1. Клонировать репозиторий:

git clone https://github.com/topmonroe9/external-sort.git
cd external-sort

2. Установить зависимости:

npm install

3. Запустить сортировку:

node src/index.js <путь-к-входному-файлу> <путь-к-выходному-файлу> [объем-памяти-в-мб]

Например:

node src/index.js data/large-file.txt data/sorted-file.txt 400

Параметры командной строки

• <путь-к-входному-файлу> — путь к большому файлу, который нужно отсортировать
• <путь-к-выходному-файлу> — путь, куда будет записан отсортированный файл
• [объем-памяти-в-мб] — опциональный параметр, указывающий максимальный объем используемой памяти в МБ (по умолчанию 400МБ)

Структура проекта

• src/index.js — главный модуль, координирующий весь процесс сортировки
• src/splitter.js — модуль для разделения большого файла на части
• src/sorter.js — модуль для сортировки отдельных частей
• src/merger.js — модуль для слияния отсортированных частей
• src/utils.js — вспомогательные функции

Создание тестовых данных

Для генерации тестового файла можно использовать функцию createTestFile из модуля utils.js:

const { createTestFile } = require("./src/utils");

// Создать тестовый файл размером 1GB со случайными строками
createTestFile("data/test-file.txt", 1024)
  .then(() => console.log("Test file created"))
  .catch(console.error);

Алгоритмическая сложность

• Временная сложность: O(N × log(N) + N × log(K)), где N — общее количество строк, K — количество фрагментов
• Пространственная сложность: O(M + K), где M — максимальный объем используемой памяти, K — количество фрагментов

Дополнительные возможности

• Поддержка пользовательских функций сравнения для сортировки по определенным полям
• Возможность сортировки по нескольким полям
• Мониторинг использования памяти и автоматическая корректировка размера фрагментов

Замечания и ограничения

• Программа предполагает, что каждая строка входного файла может поместиться в память
• Для оптимальной производительности рекомендуется использовать SSD для временных файлов
• При работе с очень большими файлами (близкими к 1ТБ) убедитесь, что у вас достаточно дискового пространства

Лицензия

MIT