Внешняя сортировка

Question

На этой веб-странице:

http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html

Объедините полученные прогоны вместе в последовательно большие прогоны, пока файл не будет отсортирован.

Как я цитировал, как мы можем объединить полученные прогоны вместе??? У нас не так много памяти.

Answer 1

Представьте, что у вас есть номера 1 - 9

9  7  2  6  3  4  8  5  1

И давайте предположим, что только 3 помещаются в памяти одновременно.

Таким образом, вы разбили бы их на 3 части и отсортировали каждый, сохранив каждый результат в отдельном файле:

279
346
158

Теперь вы бы открыли каждый из трех файлов в виде потоков и прочитали первое значение из каждого:

2 3 1

Выведите самое низкое значение 1и получить следующее значение из этого потока, теперь у вас есть:

2 3 5

Выведите следующее наименьшее значение 2и продолжайте, пока не выведете весь отсортированный список.

Answer 2

Если вы обрабатываете два прогона A а также B в какой-то более крупный пробег C Вы можете делать это построчно, генерируя постепенно увеличивающиеся прогоны, но все равно читая не более 2 строк за раз. Потому что процесс итеративный, а вы работаете с потоками данных, а не с полными отрезками данных, вам не нужно беспокоиться об использовании памяти. С другой стороны, доступ к диску может замедлить весь процесс, но это, безусловно, лучше, чем невозможность выполнить эту работу.