Внешняя сортировка между двумя файлами

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

Требуется внешняя сортировка файла произвольного размера, но с использованием только исходного файла и еще одного (назовите их fileA а также fileB) - два файла, включая оригинал. Я могу читать / писать на любой из них - так что можно поменять местами между двумя...

Я не могу понять, как это реализовать - так как большинство алгоритмов сортировки требуют, чтобы вы могли иметь обзор всего массива в памяти, чтобы, конечно, отсортировать его?

Скажем, у меня есть массив случайных целых чисел:

[1, 5, 8, 7, 3, 4, 1, 9, 0, 1, 8, 7, 7, 3, 2, 9, 1, 2];

И в любой момент времени я могу читать только четыре страницы (например, четыре целых числа) в память.

На каждом проходе это дает мне пять отдельных массивов для сортировки:

[1, 5, 8, 7]
[3, 4, 1, 9] 
[0, 1, 8, 7] 
[7, 3, 2, 9]
[1, 2]

Если я применяю сортировку в памяти, я получаю:

[1, 5, 7, 8]
[1, 3, 4, 9] 
[0, 1, 7, 8] 
[2, 3, 7, 9]
[1, 2]

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

Я полностью сбит с толку - потому что, не читая весь массив в память, мы понятия не имеем, что это за элементы перед четырьмя страницами или после - поэтому мы не можем по-настоящему отсортировать их?

Может кто-нибудь помочь мне, пожалуйста, и объяснить решающий шаг в решении этого?

Источник

2 ответа

Решение

Поскольку основная идея внешней сортировки состоит в том, чтобы объединить списки, которые больше доступной памяти, поэтому вы управляете списками (которые могут быть фактически реализованы в виде массивов или связанных списков или чего-либо еще) с помощью дескриптора над ними. Чтобы прочитать элемент из списка, вы будете использовать такой метод, как listHandle.getNextElement(), Для записи на диск в списке используйте mergedDoubleSizedList.writeNextElement(),

После того, как у вас есть:

[1, 5, 7, 8] // controlled using handle1
[1, 3, 4, 9] // controlled using handle2
[0, 1, 7, 8] // controlled using handle3
[2, 3, 7, 9] // controlled using handle4
[1, 2] // controlled using handle5

и что вы читаете только 4 дюйма, вы получаете дескриптор первых двух массивов (handle1 и handle2), считывает их элемент за элементом одновременно и записывает их обратно как один консолидированный массив, который отсортирован (mergedListHandle1). Как это:

[1, 1, 3, 4, 5, 7, 8, 9] // written by creating new handle - mergedListHandle1
[0, 1, 2, 3, 7, 7, 8, 9] // written by creating - mergedListHandle2
[1, 2] // written back by creating mergedListHandle3

Теперь снова вы получаете дескриптор двух массивов (mergedListHandle1 и mergedListHandle2), полученный в результате предыдущего шага, и продолжаете объединять их до тех пор, пока не останетесь только с двумя дескрипторами, что приведет к одному окончательному отсортированному массиву. Пожалуйста, предоставьте свой код, если вы хотите, чтобы решение на основе кода для того же самого.

За раз у вас будет только 4 элемента в памяти, если это позволяет ваша память. Итак, чтобы объединить списки, представленные handle1 и handle2, вы сделаете следующее:

  1. Читать первый элемент из handle1 и handle2 (1 а также 1)
  2. Записать меньшее из этих двух в mergedListHandle1 (т.е. записать 1 из ручки1)
    1. Вы не можете сбрасывать числа в mergedListHandle1 в данный момент.
  3. Читать следующий элемент из handle1 (5)
  4. Запишите меньшее из текущих чисел из handle1 и handle2 в mergedListHandle1
  5. Очистить содержимое mergedListHandle1, когда он заполнится
  6. Извлеките следующие меньшие дескрипторы с дисков (handle3 и handle4) и повторите тот же цикл с ними, пока вы пишете в новый больший дескриптор списка с именем mergedListHandle2.
Источник

Объяснение для простой двусторонней сортировки слиянием. Рассмотрим данные как 18 прогонов размера 1. Поскольку размер равен 1, каждый прогон можно считать отсортированным.

[1] [5] [8] [7] [3] [4] [1] [9] [0] [1] [8] [7] [7] [3] [2] [9] [1] [2]

На каждом проходе четные прогоны объединяются с нечетными прогонами слева направо из исходного массива или файла в целевой массив или файл. После каждого прохода роли источника и назначения меняются местами.

Первый проход

[1 5] [7 8] [3 4] [1 9] [0 1] [7 8] [3 7] [2 9] [1 2]

Второй проход

[1 5 7 8] [1 3 4 9] [0 1 7 8] [2 3 7 9] [1 2]

Третий проход

[1 1 3 4 5 7 8 9] [0 1 2 3 7 7 8 9] [1 2]

Четвертый проход

[0 1 1 1 2 3 3 4 5 7 7 7 8 8 9 9] [1 2]

Пятый проход (сделано)

[0 1 1 1 1 2 2 3 3 4 5 7 7 7 8 8 9 9]

Основными переменными являются размер прогона и 4 индекса начала и конца пары прогонов (четные и нечетные). Последний запуск заканчивается в конце данных и может быть четным или нечетным. Для внешней сортировки индексы становятся файловыми указателями.

Для внешней сортировки требуется только 2 области памяти для хранения данных, один элемент из четного цикла, один элемент из нечетного цикла. Два элемента сравниваются: нижний или равный записывается в целевой файл, и следующий элемент из этого прогона считывается. Если достигнут конец этого прогона, тогда записывается другой элемент, а остальная часть другого прогона копируется в файл назначения. Два файловых указателя продвигаются к началу следующей пары четных и нечетных запусков, и объединение продолжается до тех пор, пока не будет достигнут конец данных, заканчивая проход объединения. Размер прогона удваивается, роли исходного и конечного файлов меняются местами, и следующий этап слияния выполняется, повторяясь до тех пор, пока размер прогона не станет>= числом элементов.

Источник
Другие вопросы по тегам