Предположим, что у меня есть X GB свободного пространства для оперативной памяти, и мне нужно отсортировать огромный массив данных (намного больше доступной памяти, хранящейся на жестком диске). Не могли бы вы дать подсказку, как это можно сделать?
Сортировка с ограниченной памятью
Ответ 1
Вы ищете внешнюю сортировку. Наибольшая стоимость в этих сценариях часто является дисковым IO. Таким образом, трюк заключается в использовании алгоритма, который минимизирует диск IO. Обычный подход заключается в том, чтобы читать достаточно большие куски в памяти, сортировать эти куски, сохранять их обратно на диск, а затем объединять отсортированные куски.
Поиск "внешней сортировки" или "сортировки слияния" и ваших технологий выбора должен дать хорошие результаты.
Ответ 2
Предположим, что у вас есть огромный файл 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, без обработки слияния, но каждый номер читается и записывается три раза.
Ответ 3
То, что вы ищете, это внешний вид.
Ответ 4
Практически, если вы не хотите писать слишком много кода, а использование диска не является проблемой, поместите данные в базу данных с соответствующим индексом, а затем просто select * order by оттуда.
Ответ 5
Я бы хотел, чтобы вы могли создать некоторую систему индексов, чтобы вы могли разделить ваши отсортированные данные.
Представьте полки в библиотеке. Пройдите 1/x данных, отсортируйте все элементы на полках и поместите каждую полку в отдельный файл на диске. Затем отсортируйте следующие 1/x данных, запишите их обратно на диск и т.д. После того, как все ваши данные на полках пройдут и отсортируйте каждую полку отдельно, затем, наконец, объедините их в один хороший отсортированный файл.