Лекции по информатике (984119), страница 23
Текст из файла (страница 23)
полученная объединенная слиянием последовательность более упорядочена, чем исходная и она вновь подвергается разделению и слиянию; при этом упорядоченные пары переходят в упорядоченные четверки, те переходят в восьмерки и т. д, до полной упорядоченности. Возьмем в качестве примера последовательность и 44 11 12 42 94 1В Об б7 1 После разбиения на две части получим 44 55 12 42 94 18 06 67 Слияние одиночных компонент (т, е, упорядоченных последовательностей длины 1) в упо- рядоченные пары дает: п' 44 94' 18 55' 06 12' 42 67 и Деля эту последовательность пополам и сливая упорядоченные пары, получаем 06 12 44 94' 18 42 55 67 '!еперь осуществляется слияние четверок 06 12 44 94 18 42 55 67.
Первый элемент первой четверки 06 меньше первого элемента второй четверки 18< поэтому <тн перемещается в выходную последовательность, а первым элементом первой четверки становится следующий за ним 12. Он выигрывает сравнение с 18 и также проходит на выход. Рассматривается очередной элемент первой четверки (уже пары!) 44.
Он, наконец-то, проигрывает 18 и пропускает это значение вперед, после чего и лля сравнения выбирается новый элемент второй четверки (42). Этот элемент меныпе 44, поэтому перемещается в выходную последовательность, выбирая для сравнения следующий элемент этой ж<-' последовательности 55. Теперь продвигает«я вперед 44, а на, его место приходит последний элемент первой четверки 94. Ему, как самому болыпому, придется уступить сначала 55, а потом 67: с 06 12 44 94, 1( 12 44 94 18 42 55 67 ( 18 42 55 67 ( 44 94 ( 44 94 1.8 42 55 67 '( 42 55 67 ==~06 !21842 ( -г =~0612 !84244 ( гг (44 94,, ( 94 55 67 55 67 =~ 06121842 4455 ~ =~ 06 12184244 5567 ~ ( 94 ( 94 =~ 06 12 18 42 44 55 67 94 Итак, третье разделение и слияние привели, наконец, к желаемому результату.
Терминология сортировки слиянием следующая. Однократное слияние или разделение всего множества называется фазой. Проходом или этапом называется пара фаз разделение- слияние. Сортировка приведенного примера происходит за три двухфазных прохода, каждый из которых состоит из фазы разделения и фазы слияния. Поскольку для такой сортировки нужны три магнитофона (три ленты), то она получила название «трехленточного слияния». Заметим, что фазы разделения носят вспомогательный характер и не улучшают упорядоченности элементов. Поскольку при разделении элементы пе переставляются, то половина трудоемкости сортировки слиянием, связанная с разделением, непродуктивна и от псе следует избавиться. Для этого применяется очень простой прием: результат слияния сразу же распределяется по двум выхо<п<ым лентам, которые станут входшями при следующем просмотре, поменявшись ролями с исходними лентами предыдущего этапа.
Цена вопроса еще один, четвертый, .магнитофон (и лента). Таким образом, вместо двухфазной трехленточной сортировки получаем однофазную четырехленточнуго с вдвое меньшей трудоемкостьнь Проанализируем идею сортировки слиянием. Количество проходов для этой сортировки есть (1о8 и'!< поскольку при каждом проходе размер отсортированных отрезков удваивается. Общее число пересылок ЛХ =в !1о82п~, поскольку при каждом проходе все элементы копируются по одному разу. Число сравнений ключей С даже меньше ЛХ, т. к.
при копировании остатков отрезков («сливе») сравнения не производятся. Однако поскольку сортировки слянием происходят на внешних электромеханических устройствах, то время пересылки между устройством внешней 357 памяти и основной памятьн> на несколько порядков превьппает время сравнения резидентных компонс>п в буферах оперативной памяти. Поэтому при анализе сортировок слиянием числом сравнений ключей обычно пренебрегают. Главным в оценке сортировки слиянием является большая пространственная сложность алгоритма двойная память, требуемая последовательным характером слияния-разделения, За, это многие программисты не вполне оправданно отказываются от се прим! нения для внутренней сортировки. Л между про >им, сортировка слиянием, .в отличие от бьп:трой и даже пирамидальной, изначально является устойчивой, и именно этот алгоритм предлагается в библиотеке БТ1.
под характерным названием в1а!>!е в!!тЯ. Что русскому хорошо, то иемиу смерть. Русская пословица В оценке сортировки слиянием как внешней следуют другим традициям, считая двойнос кО'>иче(>тВО лент (магнитОфонов) ВНОлне дОпустимым. Геъ! бс>лсе, что кОличестВО магнитофонов постоянно (0(1)!) и совершенно >ье зависит Ог Обьема входных данных (0(п)), а емкость каждого магнитофона потенциально бесконечна по сравнению с емкостью ОП. За примерами конкретных программ прямого слияния в оперативной памяти мы отсылаем к пособии> Н.
Вирта ~54) (Модула 2) или к исходным файлам В ГЕ (заголовочный файл (а1догйЬ>>>>). Еще более быстрым является естестве>!>юе сльчяние, В основе этого алгоритма предположение, что в исходном файле уже могут быть упорядоченные отрезки. Для простоты положим, что сортируемая последовательность изначально расположена на ленте 1, а ленты 2, 3 и 4 свободны, и последовательность необходимо упорядочить по возрастанию. Первая часть естественного слияния заключается в разбиении файла на ленте 1 и записи его на ленты 3 и 4. Для этого из файла 1 считывается первая компонента и помещается на ленту 3. Если следующая компонента файла 1 не меньше предыдущей, то она тоже помещается на ленту 3.
В противном случае ее следует записать на ленту 4, куда теперь будут пометцаться все комг>оненты до встречи новой инверсии - — двух подряд идущих элементов, не соответствующих устанавливаемому порядку. После инверсии необходимо снова начать запись отрезка па ленту 3, после еще одной инверсии - снова на 4 и т.
д. вплоть до исчерпания исходного файла 1. После такого разделения начинается операпия слияния. Будем осуществлять его на ленту 1, поскольку она поступила в качестве исходных данных, она же должна ссщержать результат. Выполним слияние как обычно, запоминая при этом значение послед>ей записанной на ленту 1 компоненты. Если эта >юследняя компонента больше, чем значения на лентах 3 и 4, то резу>>ьтат слияния необходимо направить на ленту 2. Как только ситуация повторится, следует вновь начать запись на ленту 1 и т. д, вплоть до исчерпания файлов 3 и 4. Если в результате вышеописанной операции все данные окажутся в файле 1, а файл 2 окажется пуст, то сортировка завершена.
Иначе следует повторить слияние с лент 1 и 2 на ленты 3 и 4,после чего проверить факт упорядоченности файла 3. В случае упорядоченности файл 3 следует переписать в файл 1 и закончить работу алгоритма. В противном случае необходимо повторить слияние с лент 3 и 4 на 1 и 2. Отзывчивость естественного слияния на наличие упорядоченных <>трсзков в сортируемой последовательности — нс единственное ее достоинство. Обычное слияние в случае любого (упорядоченного, почти упорядоченного или совсрпюнно неупорядоченного) файла выполняет строго и (!одев и1.
Сортировка естественным слиянием работает так же плохо только в худшем случае обратно упорядоченного файла. В случае упорядоченного файла естественному слиянию необходимо пройти по файлу только один раз, в то время как обычному опять необходимо и (1ой2 и1 операций.1о есть обычное слияние даже в случае почти упорядоченных последовательностей трудоголически выполняет отмеренное число Операций, сове рпгенно не используя уже имекпцийся частичный по1зядок. Еще одна идея усовершенствования слияний сократить число проходов сортировки, выполняя распределение и слияние отрезков более чем в два направления. Этот метод называется многоиутевым сбалансированным слиянием.
Его линеарифмическая оценка улучшается за счет повышения основания логарифма с двух до числа потоков /с: М = и. ~!одьи1 11апример, при удвоении числа магнитофонов с 4 до 8, время сортировки последовательности уменьшится в 2 раза (основное лога!)ифмическое тождество): ЛХ2 и ~!од~ и1 )!од~ и ~ 1оКэ 4 2 ~~Х4 и ' ~!О$4 и ~ (1ОДз и1 6.3 Таблицы с прямым доступом Ранее мы рассмотрели вопросы ускорения поиска с помощью упорядоченных таблиц и деревьев поиска, которые дали логарифмическое время доступа. Возможно ли дальнейшее ускорение доступа? Ведь обращение к каждому элементу данных осуществляется в конце концов по конкретному физическому адресу, и если мы сможем быстро вычислить этот адрес по ключу, то фактически мы получим прямой доступ за несколько большее, но иостолпиое время. Для этого необходимо построить отооражение О ключей К в адреса А (или в индексы 1): Поместим нашу таблицу в обычный массив и построим преобразование ключей в индексы.
Напомним, что массив -- это эффективная структура данных с доступом .за постоянное время, и для доступа к его элементам уже применяется некоторая расстановочная функция А = б+ (ю, '— 1) в1хео1'(Т), где б - адрес начала массива, в1хео1'(Т) --- размер компоненты вектора в байтах, а г - индекс компоненты вектора,, отсчитываемый от 1, как это принято в линейной алгебре. По соображениям эффективной аппаратной реализации массивы следует индексировать с О, как это делается в языке Си. Для многомерного массива эта функция является многочленом, степень которого равна числу измерений массива, а коэффициенты — суть его размеры по соответствующим индексным координатам.
Естествешю, многочлен вычисляется по экономной схеме Горнера. Так, лля матрицы 3 х 4 из восьмибайтных целых функция 1Х имеет вид: У(1,Я = 6 1 (г 4-! 1) в1иео1'(Т), где г = 0...2, у' = 0...3, в1яеоГ(Т) = 8. Итак, существует эффективный доступ к элементам массива за постоянное время. Применим это подход для доступа к элементам с произвольным клк>чом. Если клнш — некое слово ш из букв а1... а, то мы можем подставить в нашу схему Горнера вместо индексов элемента г, 1, /с, ... числовые колы этих букв огс1(ас), огс1(сса), ... и, как все математики, считать задачу в принципе решенной. Однако как програмълисты мы вынуждены констатировать, сзо произведение этих кодов даже для восьъсибуссвеннсл о ключа даст нам 16 384 терабайта, что составляет максимальное адресное пространство, аппаратно поддерживаемое современными процессорами.
То есть при лобовом преобразовании ключей множество возможных значений значительно шире ъсножества допустимых адресов в памяти (индексов массива). С другой стороны, делать такое полное отображенис нс имеет смысла, ведь реальные множс ства, ключей значительно уже, и требовать взаимнсюднозначного соответствия клквсей и адресов излишне.
Один из рецептов такого отображения сопоставить нескольким ключам один и тот же адрес в надежде на малую вероятность одновременного появления в таблице ключей, претендующих на этот адрес. Таким же образом мы отображали целую окрестность точки вещественной оси в ее конечного рационального представителя. Если же этот маловероятный случай произошел, и ключ преобразован в уже занятый адрес, то есть надежда вычислить за постоянное время еще один адрес, куда и переадресовать элемент с таким ключом. При поиске в таблице ситуация будет обратной: в случае неудачи по вычисленному адресу уже находится элемент с другим ключом, поэтому, как в случае поиска подстроки алгоритмом Рабина-Карпа, необходимо проверять точное совпадение ключей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
