Разработка алгоритма сортировки внешней памяти

Question

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

Answer 1

Прежде чем приступить к созданию собственной внешней сортировки, вы можете взглянуть на инструменты, поставляемые вашей операционной системой. В Windows есть SORT.EXE, который достаточно хорошо работает с некоторыми текстовыми файлами, хотя в нем есть идиосинкразии. Сортировка GNU тоже работает довольно хорошо. Вы могли бы попробовать кому-то из этих подмножество ваших данных, чтобы увидеть, будут ли они делать то, что вам нужно.

Иначе.,,

Внешняя сортировка является довольно известным алгоритмом. Общая идея:

1. Загрузите как можно больше данных в память.
2. Сортировать этот блок.
3. Запишите этот блок во внешнюю память.
4. Повторяйте шаги 1-3, пока все все блоки не будут отсортированы и сохранены.
5. Объединить отсортированные блоки.

Если у вас есть n предметы, которые разделены на k блоки m элементы каждый (так n = k*m), первая часть (шаги 1-4) занимает время, пропорциональное k*(m log m).

После выполнения шагов 1-4, у вас есть k отсортированные блоки m предметы (или возможно k-1 блоки m предметы, и один блок, который имеет несколько меньше предметов). Или, если вы сортируете строки, у вас есть k блоки примерно одинакового размера, но количество строк в каждом блоке будет различным.

Теперь вам нужно объединить эти отсортированные блоки. Типичный способ сделать это с помощью k-way merge.

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

create heap
for each block
    read item and add to heap
end for

while heap is not empty
    remove smallest item from heap
    write to output
    read next item from block that contained smallest item
    add to heap
end while

Эта часть алгоритма O(n log k), где n общее количество предметов и k это количество блоков.

Как заметил кто-то еще, одним из ключей к эффективной внешней сортировке является уменьшение количества операций ввода-вывода. Внешнее хранилище работает медленно. Алгоритм, который я описал выше, выполняет как можно меньше операций ввода-вывода. Каждый элемент читается из внешнего хранилища дважды, а каждый элемент записывается во внешнее хранилище дважды. Другие алгоритмы, которые на первый взгляд выглядят проще или быстрее, оказываются намного медленнее при работе с реальными данными, поскольку они тратят слишком много времени на ввод-вывод.

Если вы заинтересованы в реализации, я некоторое время назад написал серию статей о сортировке очень большого текстового файла. Код C#, но описание должно позволить вам перевести на любой язык без особых проблем.