Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2), страница 3

Может показаться, что появление виртуальной памяти прщюдит к отмираиию методов внешней сортировки, так как зта раГюта может быть выполиена с помощью методов, предназначенных для внутренней сортировки. Проанализируйте такую ситуацию. Почему специально разработанный метод внешней сортировки может оказаться лучше применения обычной технологии подкачки страниц к методу внутреиней сортировкиу ь 21. [М15[ Сколько блоков переходят на диск У из 1 блочного файла при разделении на Р дисков? 22. [32[ Пусть сливаются два файла по принципу Гилбрета и желательно сохранить ключи о~ с о блоками и ключи )1з с Ь блоками.

В какай блок необходимо поместить аз для того, чтобы получить при необходимости нужиук> ииформациюу ь 23. [30[ Какой объем памяти необходим для входных буферов., в которых предполагается довольно продолжительно хранить исходные даниые, если выполняется 2-путевое слияние посредством (а) разделеиия суперблоков; (Ь) принципа Гилбретау 24, [Муб[ Предположим, что Р серий разделены между Р дисками ззк, что блок У серии (с находится иа диске (яь + 1) пюб Р. Прп выполиеиии Р-путевога слияиия зги блоки будут считываться в некотором хроиологическом порядке, подобном (19).

Если группы из Р блоков должиы вводится продолжительное время, то в момент времени Г мы будем считывать с каждого диска г-й в хронологическом порядке блок, как в (21). Каков мииимжи,ный объем буфера в памяти (в количестве записей), необходимый для хранения исходных данных, которые еще це были вовлечены в процесс слияиия, если не учитывать хронологический поридок? Объясиите, как выбрать смещения ям яв, ..., яр с тем, чтобы в худшем случае требовалось как можио меньше буферов.

25. [ЗУ[ Повторите пример из текста раздела, рассмотреиимй в связи с раидомизировав- иым разделением, изменив условия: пусть (в = 3 вместо»в ш 4. Что окажется в буферах в отличие от (24)7 26. [26] Сколько выходиых буферов необходимо, чтобы выполиеиие Р-путевого слияния с раидомизироваииым разделеиием никогда ие было приостановлено из-за отсутствия места в памяти для размещения только что полученных в результате слияния данных? Считайте, что время записи блока равна времени считывания, 27. [НМ27[ (Проблеме циклической веиятосгяи.) Предположим, что и пустых урп рас- ставлены по кругу и им присвоеиы номера О, 1, ..., и — 1. При и = 1, 2, ..., р мы бросаем т» и»аров в урны (Х» + у) шоб и, / = О, 1, ..., гл» вЂ” 1, где целые числа Х» выбираются случайно.

Пусть Я„(тм..., тр) — число шаров в урне О, а Е„(т,,..., тр) — ожидаемое число шаров в самой заполиеииой урне, а) Докажите, что Е„(тм...,тр) с 2",, ппп(1, прг(Я»(тм...,тр) > 1)), где т = т, + + глр, Ь) Используя неравенство в оютиошеиии 1.2.10-(25), докажите, что Е„(тм..,,тп ) < ву пил~1, ч . 7 п(1+а»/п)м Х (1+ а»)" ) для любых иеотрипательиых действительных чисел ам ам ..., а .

Какие значения ам ..., а„дадут наилучшую верхнюю оценку? 28. [НМ47) Продолжая упр. 27, ответьте, справедливо ли иеравеиство Е„(тм..., тр) > Е (т»+гп2,т», тр) р 20. [Муд) Назиачеиие этого уиражиеиия — вывести верхнюю опенку средиего времени, необходимого для ввода любой последовательности блоков в хронологическом порядке при выполнении процедууры раидомизироваииого разделеиия, когда блоки представляют Р серий и Р дисков. Мы говорим, что блок, ожидаемый иа некотором временном цикде в то время, когда выполняется алгоритм (см.

(24)), является "маркированным"; таким образом, суммарное время ввода пропорционально числу маркированных блоков. Маркирование зависит только от хроиологической последовательности доступа к блокам (см. (20)). а) Докажите, что если Я+ 1 последоват ельиых блоков в хронологическом порядке имеют )У блоков иа диске 3, то ие более шах(№, №,..., Жп ~) из иих являются маркироваипыми. !») Усильте результат (а), показав, что ои имеет место также для Я+ 2 последовательных блоков. с) Теперь используйте результаты анализа проблемы циклической занятости из упр.

27 и получите верхнюю оценку среднего времени выполнения в терминах функции г(Р, »/+ 2), как в табл. 2, задав любой хронологический порядок. ЗО. [НМЮО) Докажите, что для функции г(И, гл) из упр. 29 при в -+ ~ю выполияется условие г(Ы, во!обд) = 1+ О(1/ /в ) для фиксированного Ы.

З2. [НЩ8) Проаиализируйте раидомизироваииое разделение и определите поведение этого алгоритма в среднем, а ие только но отношению к верхней оценке, как функцию от Р., (в' и Р, (Иитересен даже случай для Я = О, когда требуется в средием ЩЕ/иРР ) циклов чтения.) 5.5. РЕЗЮМЕ. ИСТОРИЯ И БИБЛИОГРАФИЯ ТепеРь, когда мы почти достигли конца этой очень длинной главы, "рассортируем" наиболее важные из рассмотренных выше сведений. Алгоритм сортировки — - зто процедура, которая реорганизует файл записей таким образом, что ключи оказываютси расположенными в порядке возрастания. Вследствие такого упорядочения группируются записи с равными ключами, становится возможной эффективная обработка множества файлов, рассортированных по одному ключу, создается информационная основа для эффективных алгоритмов выборки и более убедительно выглядят документы, подготовленные с помощью компьютера.

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

Но теперь перед нами безрадостная перспектива — предстоит на деле решить, какой метод следует использовать в той или иной конкретной ситуации. Было бы прекрасно, если бы один или два метода сортировки превосходили все остальные безотносительно к приложению или используемой ма~пине. На самом же деле каждый метод имеет свои собственные, одному ему присущие достоинства. Например, метод пузырька (алгоритм 5.2.2В) не имеет ярко выраженных преимуществ, так как всегда можно найти лучший способ сделать то, что он делает; по даже он после соответствующего обобщения оказывается полезным для сортировки с двумя лентами (см. раздел 5.4,8). Итак, приходим к заключению, что почти все алгоритмы заслуживают того, чтобы о них помнили., так как существуют приложения, в которых какой-либо из них оказывается самым подходящим.

В следующем кратком обзоре освещаются основные аспекты наиболее важных алгоритмов внутренней сортировки, с которыми мы встречались. (Как обычно, А' означает число записей в файле.) 1. Распределлющий гюдс ~ет. Если диапазон ключей невелик, очень полезен алгоритм 5.20, Метод устойчив (не изменяет порядок записей с равными ключами), но требуется память для счетчиков и 2А" записей. Одна из модификаций, позволяющая сэкономить Ж из этих записей ценой устойчивости, встречается в упр. 5.2-13.

2. Простая вставка. Алгоритм 5.2.13 наиболее прост для программной реализации, не требует дополнительного объема памяти и довольно эффективен при малых Х (скажем, при Х < 25). При больших Х он становится невыносимо медленным, если только исходные данные пе окажутся сразу почти упорядоченными. 3. Сортировка с убивающим смещением. Алгоритм 5.2.1Р (метод Шелла) также довольно просто программируется, использует минимальный объем памяти и весьма эффективен при умеренно болыпих % (скажем, при 1У < 1000).

4. Вставка в список. Алгоритм 5.2.11, основан на той же идее, что и алгоритм простой вставки, и поэтому годится только при небольших Ж. Как и в других методах сортировки списков, в нем благодаря операциям со ссылками экономятся затраты на пересылку длинных записей; это особенно удобно, когда записи имеют переменную д'шну или являются частью других структур данных. 5. Соршнроека с вычислением адреса эффективна, если ключи подчиняются известному (обычно — равномерному) закону распределения; важнейшими вариантами этого подхода являются всшаекн е иескояьке списков (программа 5.2.1М) и комбинированная поразрядная сортировка со вставками Ыак-Ларена (рассмотренная в конце раздела 5.2.5). Для последнего метода достаточно иметь О(~/Х) дополнительных ячеек памяти.

Двухпроходный метод, который позволяет иметь дело с неравномерным распределением, анализируется в теореме 5.2.5Т. б. Обменная соршироека со слиянием. Алгоритм 5.2.2М (метод Бэтчера) и родственный ему алгоритм бишонной сортировки (упр. 5.3.4-10) полезны, если можно одновременно выполнять Гюльшое число сравнений. 7. Обменная сортировка с разделением (метод Хоара, широко известный как быстрая сортировка). Алгоритм 5.2.2Я, веронтно, — самый полезный универсальный алгоритм внутренней сортировки, поскольку он требует очень мало памяти и опережает своих конкурентов по среднему времени выполнения на болыпинстве компьютеров.

Однако в наихудшем случае он может работать очень медленно, Поэтому, если вероятность неслучайных данных достаточно велика, приходится тщательно выбирать разделяющие элементы. Если выбирается медиана из трех элементов (как предлагается в упр. 5.2.2-55), то такое поведение, как в наихудшем случае, становится крайне маловероятным и, кроме того, несколько уменьшается среднее время работы. 8.

Простой выбор. Алгоритм 5.2.35 довольно прост и особенно подходит в случае, когда имеется специальное оборудование для быстрого поиска наименьшего элемента в списке, 9. Пирамвдеяьнея сортировке. Алгоритм 5.2.3Н прн минимальных тре5ованнях к памяти обеспечивает достаточно высокую скорость сортировки: как среднее, так н максимальное время работы примерно вдвое больше среднего времени быстрой сортировки. 10. Слияние списков. Алгоритм 5.2.41 осуществляет сортировку списков, обеспечивая при этом, так же как и алгоритм пирамидальной сортировки, весьма высокую скорость даже в наихудшем случае.