Сортировка на основе файлов на больших наборах данных в Java

Ответ 1

Java предоставляет универсальную процедуру сортировки, которая может использоваться как часть более крупного решения вашей проблемы. Общий подход к сортировке данных, который слишком велик для всех в памяти, таков:

1) Прочитайте столько данных, сколько поместится в основную память, скажем, 1 Гб

2) Quicksort, что 1 Гб (здесь, где вы будете использовать встроенную сортировку Java из структуры Collections)

3) Напишите этот отсортированный 1 Gb на диск как "chunk-1"

4) Повторяйте шаги 1-3 до тех пор, пока не пройдете все данные, сохраняя каждый фрагмент данных в отдельном файле. Поэтому, если ваши исходные данные были 9 Гб, теперь у вас будет 9 отсортированных фрагментов данных с надписью "chunk-1" через "chunk-9"

5) Теперь вам просто нужна окончательная сортировка слияния, чтобы объединить 9 отсортированных фрагментов в один полностью отсортированный набор данных. Сорт слияния будет работать очень эффективно против этих предварительно отсортированных кусков. Он будет по существу открывать 9 файловых читателей (по одному для каждого фрагмента), плюс один файловый писатель (для вывода). Затем он сравнивает первый элемент данных в каждом файле чтения и выбирает наименьшее значение, которое записывается в выходной файл. Читатель, с которого это выбранное значение переходит к своему следующему элементу данных, и 9-позиционный процесс сравнения, чтобы найти наименьшее значение, повторяется, снова записывая ответ в выходной файл. Этот процесс повторяется до тех пор, пока все данные не будут прочитаны из всех файлов chunk.

6) Как только шаг 5 завершит чтение всех данных, которые вы выполнили, ваш выходной файл теперь содержит полностью отсортированный набор данных

С помощью этого подхода вы можете легко написать общую "мегазотную" утилиту, которая принимает параметр filename и maxMemory и эффективно сортирует файл, используя временные файлы. Я бы поспорил, что вы можете найти по крайней мере несколько реализаций там для этого, но если нет, вы можете просто свернуть свое, как описано выше.

Ответ 2

Самый распространенный способ обработки больших наборов данных - в памяти (в наши дни вы можете купить сервер с 1 ТБ) или в базе данных.

Если вы не собираетесь использовать базу данных (или приобретаете больше памяти), вы можете легко ее легко написать.

Существуют библиотеки, которые могут помочь в выполнении функций Map-Reduce, но они могут добавить больше сложности, чем они сохраняются.