Сложность времени/стоимость внешней сортировки слиянием

Я получил это по ссылке, в которой говорится о внешних Сортировка слиянием.

Из слайда 6 Пример: с 5 буферными страницами для сортировки 108-страничного файла

  • Pass0: [108/5] = 22 отсортированных запуска по 5 страниц каждый (последний запуск только с 3 страницами)

  • Pass1 [22/4] = 6 отсортированных запусков по 20 страниц каждый (последний запуск только с 8 страницами)

  • Pass2: [6/3] = 2 отсортированных прогона, 80 страниц и 28 страниц.

  • Проход 3: [2/2] = 1 отсортированный файл из 108 страниц

Вопрос: Насколько я понимаю, во внешней сортировке слиянием на проходе 0 вы создаете фрагменты, а затем сортируете каждый фрагмент. В оставшихся проходах вы продолжаете их объединять. Таким образом, применяя это к приведенному выше примеру, поскольку у нас есть только 5 буферных страниц, на проходе 0 ясно, что нам нужно 22 отсортированных прогона по 5 страниц в каждом.

  1. Теперь, почему мы делаем отсортированные прогоны для оставшихся проходов или слияние?

  2. Почему он сообщает для прохода 1 6 отсортированных прогонов по 20 страниц каждый, когда у нас есть только 5 буферных страниц?

  3. Где именно здесь происходит слияние? и как N уменьшается в каждом проходе, то есть со 108 до 22 до 6 до 2?


algorithm mergesort
person Frank Q.    schedule 28.04.2012    source источник

Ответы (2)


arrow_upward
17
arrow_downward

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

Pass0: вы выполняете операции НА МЕСТЕ. Таким образом, вы загружаете 5 страниц данных в буферы, а затем сортируете их на месте, используя алгоритм сортировки на месте. Эти 5 страниц будут храниться вместе как прогон.

Последующие проходы: вы больше не можете выполнять операции на месте, так как вы объединяете прогоны многих страниц. В буферы загружаются 4 страницы и 5-я является буфером записи. Слияние идентично алгоритму сортировки слиянием, но вы будете разделять и властвовать с коэффициентом B-1 вместо 2. Когда буфер записи заполняется, он записывается на диск и запускается следующая страница.

Сложность. При анализе сложности внешней сортировки слиянием учитывается количество операций ввода-вывода. В каждом проходе вы должны прочитать страницу и записать страницу. Пусть N будет количеством страниц. Каждый запуск будет стоить 2N. Прочтите страницу, запишите страницу.
Пусть B будет количеством страниц, которое вы можете хранить в буферном пространстве, а N будет количеством страниц.
Будет ceil(log_B-1(ceil(N/B)) ) проходит. Каждый проход будет иметь 2N операций ввода-вывода. Итак, O(nlogn).

При каждом проходе длина страницы увеличивается в B-1 раз, а количество отсортированных запусков уменьшается в B-1 раз.
Pass0: ceil(108 / 5) = 22, 5 страниц за прогон
Проход 1: ceil(22 / 4) = 6, 20 страниц за прогон
Проход 2: ceil(6 / 4 ) = 2, 80 страниц за прогон
Проход 3: ceil(2 / 4) ) = 1 - выполнено, 1 прогон 108 страниц

person JustinDanielson    schedule 28.04.2012
comment
Предположим, что размер всех страниц одинаков. Вы загружаете 4 страницы из 108 страниц и сохраняете их на 4 страницах входного буфера, а затем объединяете данные в буфер результатов. Теперь, как буфер результатов может содержать данные размером с 4 страницы входного буфера? - person Frank Q.; 28.04.2012
comment
Все страницы одинакового размера, кроме последней. В проходе 0 вы загружаете 5 страниц и сортируете их на месте. Он не вмещает все 4 страницы одновременно. Он содержит только первую страницу каждого прогона, думайте о каждом прогоне как о связанном списке. В конце каждой страницы находится указатель на следующую страницу в прогоне. Данные отсортированы, поэтому данные на странице 2 будут логично следовать за данными на странице 1. Я думаю, вы путаете страницу и прогон. Прогоны состоят из нескольких страниц, страницы содержат данные. - person JustinDanielson; 28.04.2012
comment
Для прохода 1 вы копируете 4 страницы с диска в 4 входных страницы в ОЗУ, а затем объединяете эти страницы с выходной страницей, которая находится в ОЗУ. Эта выходная страница в 4 раза больше размера других входных страниц? Вы видите, что я пытаюсь сказать? - person Frank Q.; 28.04.2012
comment
Уфф, ладно. Ну да. Ввод и вывод 1 к 1, поэтому, если вы прочитаете 108 страниц, 108 страниц будут записаны на диск. Но количество страниц за прогон увеличивается с каждым проходом. Вы записываете 1 страницу в оперативную память, когда она заполняется, вы записываете ее на диск. Затем она опорожняется и снова заполняется, после заполнения записывается на диск после предыдущей страницы. Если буфер может вместить 250 #s, то 200 будет из 4-х страниц, как только 50 отсортированных чисел будут записаны в выходной буфер, он сохраняется на диск и очищается. Всякий раз, когда во входном буфере заканчиваются числа, считывается следующая страница. Надеюсь, это поможет. - person JustinDanielson; 28.04.2012
comment
В таком странном случае, как этот, когда количество страниц очень мало, поэтому важно, чтобы они были дискретными, вы могли бы выполнить меньше работы по слиянию, объединив три прогона по 20 страниц между pass1 и pass2. Тогда pass2 будет единственным 4-сторонним слиянием. Это уменьшает общий объем перемещения данных. В реальной ситуации, когда доступны тысячи или миллионы страниц памяти, идеальная ширина слияния, вероятно, ограничена чем-то другим, а не количеством страниц. (например, избегая слишком большого количества операций ввода/вывода) - person Peter Cordes; 28.10.2015

arrow_upward
0
arrow_downward

О. Поскольку слияние НИКОГДА не упоминается, я бы предположил (надеюсь), что более поздние проходы «сортировки» выполняют слияния.

B. Опять же, если предположить, что это слияние, вам нужен один буфер для сохранения объединенных записей, и используйте один из оставшихся буферов для каждого объединяемого файла: таким образом, 4 входных файла, каждый с 5 страницами: 20 страниц.

C. Думаю, я уже дважды ответил, где слияние :)

person Scott Hunter    schedule 28.04.2012
comment
Я не понимаю, откуда взялись 4 входных файла? Вы имеете дело со страницами здесь. Я могу использовать 4 страницы буфера из 5, чтобы загрузить 4 страницы из 108 страниц и сохранить результат на последней странице. Но, похоже, это не так, как описано выше. А во втором проходе как получилось 6/3? - person Frank Q.; 28.04.2012
comment
@FrankQ.: Извините; Я научился этому, используя файлы вместо страниц. Но страницы группируются в более крупные наборы, чтобы хранить более длинные последовательности записей. Вы хотите зарезервировать одну буферную страницу для каждой группы, извлекая каждую страницу последовательно из этой группы по мере того, как слияние доходит до нее. Для прохода 2 группы теперь имеют размер 20 страниц (из 4 групп размера 5), поэтому групп всего 6. - person Scott Hunter; 28.04.2012