Сортировка с ограниченной памятью

Предположим, что у меня есть X GB свободного пространства для оперативной памяти, и мне нужно отсортировать огромный массив данных (намного больше доступной памяти, хранящейся на жестком диске). Не могли бы вы дать подсказку, как это можно сделать?

5 ответов

Вы ищете внешнюю сортировку. Наибольшая стоимость в этих сценариях часто является дисковым IO. Таким образом, трюк заключается в использовании алгоритма, который минимизирует диск IO. Обычный подход заключается в том, чтобы читать достаточно большие куски в памяти, сортировать эти куски, сохранять их обратно на диск, а затем объединять отсортированные куски.

Поиск "внешней сортировки" или "сортировки слияния" и ваших технологий выбора должен дать хорошие результаты.


Предположим, что у вас есть огромный файл H и ограничить память M. У меня есть два решения.

Решение 1: Шаг 1: Прочитайте M из файла и запишите его в временный буфер. Шаг 2: Сортировка (вы должны использовать алгоритм сортировки на месте, например QuickSort, HeapSort). Шаг 3: Создайте временный файл и напишите буфер в файл temp. Сохраните имя временного файла. Шаг 4: Повторите шаги с 1 по 3, пока не прочитайте файл H out и не сортируйте M out и сохраните все временные файлы. Шаг 5: Слейте все временные файлы в новый файл. Создайте новый файл и откройте все временные файлы, поместите файлы в массив. Шаг 6: Найдите минимальное число из набора чисел, на которые указывает указатель чтения файла. Вы можете использовать обычный способ сделать это, сравнить каждый номер и использовать временную переменную для запоминания (сложность по времени - O (n). Или вы можете создать приоритетQueue и карту, ключ карты - это число, и значение карты - это последовательность дескрипторов файлов (временная сложность - O (lgn), второй способ - больше памяти, но производительность лучше, если вы хотите лучше, вы можете использовать int для замены списка используя растровое изображение, потому что имена файлов temp исполняются. Шаг 7: Сохраните номер в новом файле. Шаг 8: Прочитайте еще один номер из файла, который содержит минимальное число на шаге 6. Шаг 9: Повторите шаги с 7 по 8, пока не будут обработаны все номера из всех временных файлов.

Решение 2: Шаг 1. Создайте файлы N temp, диапазон номеров всех временных файлов различен. (Например, диапазон temp_file_1 от 0 до 1000000, а следующий временный файл - от 1000001 до 2000000...) Шаг 2: Прочтите m из файла H и напишите номер в разные временные файлы, пока ничего не прочитайте из файла H. Шаг 3: Сортировка всех временных файлов. Шаг 4: Создайте новый файл, объедините все временные файлы в этот новый файл один за другим.

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


То, что вы ищете, это внешний вид.

http://en.wikipedia.org/wiki/External_sorting


Практически, если вы не хотите писать слишком много кода, а использование диска не является проблемой, поместите данные в базу данных с соответствующим индексом, а затем просто select * order by оттуда.


Я бы хотел, чтобы вы могли создать некоторую систему индексов, чтобы вы могли разделить ваши отсортированные данные.

Представьте полки в библиотеке. Пройдите 1/x данных, отсортируйте все элементы на полках и поместите каждую полку в отдельный файл на диске. Затем отсортируйте следующие 1/x данных, запишите их обратно на диск и т.д. После того, как все ваши данные на полках пройдут и отсортируйте каждую полку отдельно, затем, наконец, объедините их в один хороший отсортированный файл.

licensed under cc by-sa 3.0 with attribution.