AOP_Tom3 (1021738), страница 93
Текст из файла (страница 93)
И. Никитин и Л. И. Шолмов (Кибернетика 2,6 (1966), 79 — 84). Имеются счетчики чиста ключей (по одному на каждую возможную конфигурацию старших битов), на основе которых строится искусственные ключи кы кз,...,кы так, чтобы для каждого 1 число действительных ключей, лежащих между и; и к,~ы находилось в заранее заданном диапазоне между Р~ и Рю Таким образом, М лежит между (Х/Рз) и (Х~РП'.
Если счетчики старших битов не дают достаточной информации для определения таких кы кю.,,, км, то делается еще один или более проходов для подсчета частоты конфигураций менее значащих битов при некоторых конфигурациях старших битов. После того как таблица искусственных ключей построена, 2 (1к М) проходов будет достаточно для завершения сортировки.
(Данный метод требует объема оперативной памяти, пропорционального Ж, и поэтому не может использоваться для внешней сортировки при Ж -з сю. На практике мы не станем применять его для файлов на нескольких бобинах, и, следовательно, М будет сравнительно невелико, так что таблица искусственных ключей легко поместится в памяти.) Имитация дополнительных лент. Ф. К. Хеппи (Г. С. Непше) и Р.
Э. Стирнз (Н. Е. 8геагпк) изобрели общий метод имитации й лент всего на двух л< птах, причем таким образом, что требуемое суммарное перемещение ленты возрастает всего лишь в О(!об Ь) раз, где Л вЂ” максимальное расстояние, которое нужно пройти на любой одной ленте [3АСМ 13 (1966), 533 — 546). Их построение в случае сортировки можно слегка упростить, что и сделано в слгдукицем методе, предложенном Р.
М. Карпом. Будем имитировать обычное сбалансированное слияние на четырех лентах, используя две ленты: '1'1 и Т2. На первой нз них (т. е. на Т1) содержимое имитируемых лент хранится так, как изображено на рис. 86. Представим себе, что данные записаны на четырех "дорожках" по одной для каждой имитируемой ленты.
(В действительности лента не имеет таких дорожек. Мы просто будем считывать блоки 1., 5, 9, 13,..., как дорожку 1, блоки 2, 6, 16, 14,..., как дорожку 2, н т. д.) Другая лента (Т2) используется только для вспомогательного хранения, чтобы помочь в выполнении перестановок на Т1. Зона 3 Зона О Зона ! Зона 2 Дорожка 1 Дорожка 3 Дор Дорожка 4 Рис. 86. Разбивка ленты Т1 в конструкции Хенни-Стирнэа (веоустые зоны заштрихованы). Блоки на каждой дорожке разделяются на зоцж. содержащие соответственно 1, 2, 4, 8, ..., 2~, ... блоков, Зона к на каждой дорожке либо заполнена точно 2 блоками данных, либо пуста, Например, на рис.
85 на дорожке 1 данные содержатся в зонах 1 и 3, на-дорожке 2 — в зонах О, 1 и 2, на дорожке 3 — в зонах О и 2, на дорожке 4 — в зоне 1, а все остальные эоны пусты. Предположим, что мы выполняем слняние данных с дорожек 1 и 2 на дорожку 3. В оперативной памяти находятся два буфера, используемые двухпутевым слиянием для ввода, а также третий буфер — - для вывода. Когда буфер ввода для дорожки 1 станет пустым, можно заполнить вго следующим образом: найти первую непустую зону дорожки 1, скажем зону к, и скопировать ее первый блок в буфер ввода, затем скопировать остальные 2" — 1 блоков данных на Т2 и переместить нх в зоны О, 1, ..., к' — 1 дорожки 1. (Теперь зоны О, 1, ..., к — 1 заполнены, зона 1с пуста.) Аналогичная процедура используется, чтобы заполнить буфер ввода для дорожки 2, как только он станет пустым.
Когда буфер вывода подготовлен для записи на дорожку 3, мы обращаем этот процесс, т, е. просматриваем Т1, пока не найдется первая пустая зона на дорожке 3, .скажем зона й, и в то же время копируем данные из зон О, 1, ..., й — 1 на Т2. Данные на Т2, к которым присоединяется содержимое буфера вывода, используются теперь для заполнения зоны к на дорожке 3.
Для этой процеду'ры необходимо уметь выполнять запись в середину ленты Т1, не разрушая последующую информацию. Как и в случае осциллирующей сортировки с прямым чтением (раздел 5.4.5), можно без опасений выполнять это действие, если принять меры предосторожности. Поскольку просмотр до зоны к осуществляется только один раз за каждые 2ь шагов, то, чтобы переписать 2' — 1 блоков с дорожки 1 в память, потребуется переместить ленту на 2,'а<в<,2' 1 ". с '2ь = с!2' 1, где с - некоторая константа. Таким образом, каждый проход слияния требует 0(Ж!о8Ж) шагов.
Поскольку в сбалансированном слиянии имеется 0(!онАг) проходов, общее время работы будет составлять 0(Х(!обХ) ), что асимптотически значительно лучше, чем наихудший случай для быстрой сортировки. На самом же деле этот метод оказывается почти бесполезным, если применяется для сортировки 100,000 записей из примера раздела 5.4.6, поскольку информация, которая должна размещаться на ленте Т1, не поместится на одной бобине ленты.
И даже если мы пренебрежем этим фактом и будем исходить из самых оптимистических предположений относительно совмещения чтения/записи/вычислений, относительно длин междублочных промежутков и т. д., то найдем, что для выполнения сортировки потребуется около 37 ч! Итак, этот метод представляет чисто академический интерес: константа в 0(Х(!о8Аг)г) слишком велика, чтобы метод можно было эффективно использовать при реальных значениях Аг. Однолеиточная сортировка. Можно ли обойтись всего одной лентой? Нетрудно видеть, что сортировку методом пузырька Р-го порядка можно преобразовать в одноленточную сортировку, но результат будет ужасен.
Г, Б, Демут (РЬ. В, сЬея!я (Бсап1огд Пп!чегя1у, 1956), 85) сделал вывод, что в компьютере с ограниченной оперативной памятью после просмотра ограниченного участка ленты нельзя уменьшить число инверсий перестановки болыпе чем на ограниченную величину. Следовательно, любой алгоритм сортировки с одной лентой потребует в среднем не более чем Л~г! единиц времени (где а — некоторая положительная константа, зависящая от конфигурации компьютера). Р. М, Карп нашел очень интересный подход к исследованию этой задачи, обнаружив то, что, по существу, является оптимальным способом сортировки с одной лентой. При анализе алгоритма Карпа удобно следующим образом переформулировать задачу: как быстрее всего переасгтпи людей между этажами, если работает талько один лифт? !См.
СотЬтасола! А!8олсйтя, енес! Ьу Напг(а!! Впяйп (А!бог!1Ь|п!ся Ргеяя, 1972), 17 — 21.) Рассмотрим здание с н этажами; помещение каждого этажа рассчитано на 5 человек. В этом здании нет ни окон, ни дверей, ни лестниц, но есть лифт, который может останавливаться на любом этаже.
В здании находятся Ьп человек, и ровно 5 из них хотят попасть на свой этаж. В лифт вмещается самое большее т человек, и он затрачивает одну единицу времени для перемещения с этажа 1 на этаж ! + 1. Как найти самый быстрый способ перемещения всех людей на нужные этажи, если требуется, чтобы лифт начал и закончил свое движение на первом этаже". Нетрудно заметить связь между этой задачей и одноленточной сортировкой: люди — это записи, здание — лента, этажи — отдельные блоки на ленте, а лифт — оперативная память компьютера. Действиям программ для компьютера свойственна большая гибкость, чем действиям лифтера (программа может, напри- Рис.
87. Алгоритм Карпа для примера с лифтом. мер, создавать двойников или, разрезав человека на две части, оставить их на время на разных этажах и т, д,), но в приведенном ниже алгоритме задача решается самым быстрым мыслимым способом без выполнения таких операций. Алгоритм Карпа [рис.
87) использует два следующих вспомогательных массива: и», 1<1е<п: числа людей на этажах (й, стремящихся попасть на этажи >к; [4) о», 1(/с < и: число людей на этажах >/с, стремящихся попасть на этажи < к. ~ [[и»/т~[ + [и»/т) ) »=» [5) единиц времени при любом правильном графике работы. Карп обнаружил, что эта нижняя граница действительно достижима, если иы..., и„» ненулевые. Теорема К.
"Если и» > О прн 1 < й < и, то существует график работы лифта, при котором все люди доставляются на свои этажи эа минимальное время [5). Доказательство. Предположим, что в здании имеется дополнительно т человек. Изначально они находятся в лифте, и этаж их назначения искусственно полагается нулевым. Лифт может функционировать в соответствии со следующим алгоритмом, начиная с к [текущий этаж), равного 1.
К1. [Движение вверх.[ Иэ 6+т людей, которые находятся в данный момент в лифте н на этаже Й, толька т человек, стремящихся на самый высокий этаж, попадает в лифт. Остальные остаются на этаже Й. Пусть теперь в лифте находится и человек, стремящихся на этажи > 1е, н Н вЂ” на этажи < и. [Если и» ( т, окажется, что и = шш[гп,и»). Следовательно, можно увозить некоторых людей от их места назначения. Это — их жертва во имя общей пользы.) Уменьшить и» на и, увеличить Н»» на Н и затем увеличить й на 1.
Когда лифт пуст, мы всегда имеем и» = Н»е~ при 1 < и < п, поскольку на каждом этаже находится 5 человек. Количество людей, направляющихся с этажей 11,..., Й) на этажи (к+1,..., и), должна быть равно числу людей, стремящихся переехать в обратном направлении. По определению и„= 41 = О. Ясна, что лифт должен сделать, по крайней мере, [и»/т~[ рейсов с этажа к на этаж к+ 1 при 1 < и < и, так как толька т пассажиров могут подняться за один рейс. Аналогична ан должен сделать не менее [и»/т) рейсов с этажа и на этаж 1е — 1.
Следовательно, лифту потребуется, по крайней мере, К2. [Продолжить движение вверх?) Если иь > О, вернуться к шагу К1. КЗ. )Движение вниз.) Из 6+ пэ людей, находящихся в данный момент в лифте или на этаже й, только пт человек, стремящихся на самый низкий этаж, попадает в лифт. Остальные остаются на этаже к. Пусть теперь в лифте находится и человек, стремящихся на этажи > к, и и' — на этажи < к.
(Всегда оказывается, что и = О, а 91 = т, но алгоритм описывается здесь применительно к произвольным и и 9?, чтобы сделать доказательство несколько прозрачнее.) Уменьшить 94ь на с?, увеличить иь 9 на и и затем уменьшить ?с на 1. К4. (Продолжить движение вниз?] Если?е > 1 и пь 1 > О, вернуться к шагу КЗ. Если й = 1 и и1 — — О, закончить выполнение алгоритма (все люди доставлены на свои этажи, а тп "дополнительных" человек снова находятся в лифте).
В противном случае вернуться к шагу К2. На рнс. 88 показан пример выполнения этого алгоритма длв здания с девятью этажами, 6 = 2 и Эп = 3. Заметим, что один из тех, кто стремится на шестой этаж, временно отдаляется от своего места назначения, несмотря на то что лифт проходит максимально близко к этому этажу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
