AOP_Tom3 (1021738), страница 97
Текст из файла (страница 97)
Рис. 93. Оптимальный способ слияния 22 начальных серий равной длины, если а = Д в теореме Н. Эта схема позволяет минимизировать время поиска при предположениях, приведших к формуле (2). Выражение (2) показывает, что всегда, когда используются Р+ 1 буферов равных объемов, будет действительным соотношение а < Д. Предельный случай, когда а = Д, показанный в табл. 1 и на рис. 93, возникает тогда, когда необходимо минимизировать само время поиска безотносительно ко времени передачи. Вернемся к нашей первоначальной задаче.
Мы еще не выяснили, как получить начальные серии на первом месте; без совмещения чтения~записи/вычислений метод выбора с замещением теряет некоторые из своих преимуществ. Возможно, следует заполнить всю оперативную память, рассортировать данные в ней н вывестн результат. Каждую из таких операций ввода и вывода можно выполнить с одним поиском. Или, возможно, лучше использовать, скажем, 20Уо оперативной памяти в качестве комбинированного буфера ввода-вывода и выполнить выбор с замещением. Это требует в пять рвз больше поисков (дополнительно примерно 60 с или около того!), но позволяет уменьшить число начальных серий со 100 до 64; уменьшение будет еще более резким, если исходный файл уже почти упорядочен.
Голи не использовать выбор с замещением, то оптимальное дерево для о = 100, а = 0.00145., Д = 0.01545 [см. (2)] оказывается весьма прозаическим. Это просто 10-путевое слияние, выполняемое за два прохода по данным. Выделив 30 с на внутреннюю сортировку (скажем, 100 быстрых сортировок), получаем, что начальный распределительный проход выполняется примерно за 2.5 мнн, а каждый проход сли- Таблица 1 хАРАктеРистики ОцтимальнОГО ДеРеВА ! (ий ь (и), КОГДА о = и' = 1 и 1 2 3 4 5 6 7 8 9 10 11 12 Дерево и яния — за почти 5 мин; в итоге имеем 12.4 мин. Если использовать выбор с замещением, то оптимальное дерево для л = 64 ока)ывается одинаково неинтересным (два прохода 8-путевого слияния); начальный распределительный проход осуществляется примерно за 3.5 мин, каждый проход слияния — примерно за 4.5 мин, а оценка общего времени составляет 12.5 мин.
Не забудьте, что в обоих этих методах фактически полностью исключается совмещение чтения/записисвычислений с тем, чтобы иметь ббльшие буфера !для уменьшения времени поиска). Ни одна из этих оценок не включает время, которое может потребоваться для операций контрольного чтения. На практике последний проход слиянии отличается от остальных; например, выводные данные часто редактируются и/или записываются на ленту. В таких случаях дерсно, изображающее схему слияния, следует выбирать с использованием иного критерия оптимальности в корневом узле. *Подробности об оптимальных деревьях.
В теоремах Н и К интересно рассмотреть предельный случай, когда )3 = О, несмотря на то что на практике обычно нозникает соотношение между параметрами вида О < сс < б. Какое дерево с и листьями имеет наименьшую возможную длину степенного пути? Любопытно. что в этом случае наилучшим оказывается 3-путеное слияние. Теорема Ь. Длина степенного пути дерева с и листьями никогда не будет меньше, чем ) Зйи+ 2(и — 34), если 2 3' ' < п < 3'1 1 Зби+ 4)п — 34), если 34 < и < 2 3".
! 0,0 2 6,2 3 12,3 4 20,4 5 30,5 6 42,2 7 523 8 623 9 723 10 84,3 11 96,3 )г !о8.3 13 121,4 14 134,4 15 147,4 16 160,4 17 175,4 18 190,4 19 205. 4 20 220,4 21 236,5 22 252,3 23 266,3 24 282,3 25 296,3 0,1 б,! 0,1 12) 61 01 18 2 12 1 6 1 24,3 18,1 12,1 32,3 24,1 18,1 40,4 30,2 24,1 50,4 36,3 30,1 60,5 44,3 36,1 72,4 52,3 42,2 82,4 60,4 48,3 92,4 70,4 56,3 102,5 80,4 64,3 114,5 90,4 72,3 124,7 Н]2,4 80,4 134,8 112,4 90,4 !44,9 122,4 100,4 156,9 132,5 110,4 168,9 144,4 120,5 180,9 154,4 132,4 192,10 164,4 142,4 204,11 174,5 152,4 216,12 186,5 162,5 229,12 106,7 !74,4 0,1 6,1 0,1 12,) 6,1 ш,) )г,) 24,1 18,1 30,1 24,1 36,1 30,1 42,1 36,1 48,1 42,1 54,2 48,1 60,3 54,1 68,3 60 1 76,3 66,2 84,3 72,3 92,3 80,3 100,4 88,3 110,4 96,3 120,4 104,3 130,4 112,3 ! )0,4 120,4 1.50,5 130,4 0,1 6,1 0,1 12,) 6,1 18,1 12,) 24,1 18,1 30,1 24,1 36,! 30, 1 42,1 36,1 48,1 42,1 54,1 48,1 60,1 54,1 66,1 60,1 72,1 66,1 78,2 72,1 84,3 78,1 92,3 84,1 )00,3 90,2 108,3 96,3 116,3 104,3 0,1 6,1 0,1 12,1 6,1 0,1 18,1 12,1 6,1 О,! 24,1 18 ! 12,1 б 1 30,1 24,1 18,1 12,1 36,1 30,1 24,1 18,1 42 1 Зб 1 30 1 24 1 48,1 42,1 36,1 30,1 54,1 48,1 42,1 Зб,! 60,1 54,1 48,1 42,1 66,1 60,1 54,1 48,1 72.1 66,1 60,1 54,1 78,1 72,1 бб,! 60,1 84,1 78,1 72,1 66,1 90,1 84,1 78,1 72.1 96,1 90,1 84,1 78,1 1 1:1 2 1 1:! 3 1:1:1:1 4 1:1:1:1;1 5 3:3 б 1:3:3 7 2:3:3 8 3:3:3 9 3:3:4 10 34:4 11 4:4.4 12 3:3:3:4 13 3:3:4:4 14 3:4:4:4 15 4:4:4:4 16 4:4:4:5 17 4:4:5 5 18 4;5:5:5 19 5:5;5:5 20 4:4.4:4:5 21 4:9:9 22 599 23 5:9:10 24 7;9:9 25 Тернарные деревья Т„, определенные правиламп (7) имеют мнзшмвльную длину степенного пути.
Двказатиелъство. Обратите ннимание на то, что /(и) — вмпдклал функция, т. е. /(и+ 1) — /(и) > /(и) — /(и — 1) при всех и > 2. Это свойство существенно в соотнетстнии со следующей леммой, которая двойствен- на результату упр. 2.3.4.5 — 17. Лемма С. Функция д(п), определенная на положительных целых чпсввх, удовле- творяет условию ппп (д(й) + д(п — й)) = д((п/2)) + д((п/2)), и > 2, 1<<в<в (9) тогда и только тогда, когда она выпуклая.
Доказательство. Егли д(п+ 1) — д(п) < д(п) — д(п — 1) при некотором и > 2, то имеем д(п + 1) + д(п — 1) < д(п) + д(п), что противоречит (9). Обратно, если (8) выполняется для д и если 1 < Й < и — Й, то в силу выпуклости д(к+ 1) +д(п — Й вЂ” 1) < д(к) + д(п — 1с).
1 Последнюю часть доказательства леммы С можно обобщить для любого т > 2 и показать, что ппп (д(п~) + .. + д(п„,)) в~т — т пь ...т Ьм = д()п/ш)) + д(((п+ 1)/ш)) +. + д(((п+ ш — 1)/т)), (10) если д выпукла. Пусть /„,(и) = /((и/т)) +/(((и+ 1)/т)) + +/(((и+ ш — 1)/т)). (11) Доказательство теоремы Ь будет полным, если убедиться, что /з(п) + Зп = /(и) и /,„(и) + тп > /(и) при всех т > 2 (см. упр. 11). Было бы очень хорошо, если бы оптимальные деревья всегда характеризовались так же четко, квк н теореме Ь. Но результаты для о = 3, которые приведены в табл. 1, показывают, что функция Аз(п) не нсегда выпукла.
На самом деле данные, приведенные в табл. 1, достаточны, чтобы опровергнуть большинство простых предположений об оптимальных деревьях! Мы, однако, можем спасти часть теоремы Ь для общего случая. М. Шлюмбергер (М. БсЫпшЬегкег) и Ж. Вуйлемен (Д.
"х"ш11ешш) показали, что высоких порядков слияния всегда можно избежать. (12) Теорема М. Если даны о и й, как в теореме Н, то существует оптпматьнос дерево, в котором степень любого узла не превосходпт Доказательство. Пусть и,,..., и,„- — положительные целые числа, такие, что пь + - .. + и = и, А(пь) + .. +.4(пт) = А~(п) и и, < < и„„и предположим, что иь, ~ сХ(а,д) + 1. Пусть 1' — значение, при котором достигается минимум в (12); покажем, что ать(т — 1с) + 17п+ А ь(п) < опт+,9п+ А (п), (13) и, следовательно, минимум н (4) всегда достиьвется прн некотором пь < ь)(а, ь7).
По определению, поскольку т > 1с+ 2, мы должны иметь Аж — ь(ьь) < Аь(пь+ +пьь ь)+Аь(пь, в)+ +Аь(п,„) < а(иь+. +пьч.ь)(1с+1)+/1(гьь+ +пьгь)+Аь(пь)+ +Аь(п ) = (а(1+1)+/1)(пь+ . +иьгь)+А (и) < (а(Й+1)+17)(1с+1)п/т+А (ьь). Отсюда легко вььнодится (13). (Тщательный аяализ чтото доказательства показывает, что оценка (12) является "наилучшей из возможных" в том смысле, что некоторые оптимальные деревья должььы иметь узлы степени д(а, д); см. упр.
13.) 1 Для построения н теореме К требуется 0(ьььз) ячеек памяти и 0(ьь'~ 1ойдь) шагов для вычисления А,(п) при 1 < т < и < ь5ь; н теореме М показано, что необходимо только 0(ььь) ячеек н 0(ььСт) шагов. Шлюмбергер и Вуйлемен открыли еще несколько очень интересных свойств оптимальных деревьев (Ас1а ХпХогтабса 3 (1973), 25-36',. Величина асимптотического выражения для А,(и) ныводится, как продеъьонстрировано в упр. 9, (14) В +..+В, +В.„=М, где М вЂ” общий объем наличной оперативной памяти. Число операций поиска будет приблизительно равно Х,ь + в Хи Х гьь + (15) — + Вр Вггь *Еще один способ распределения буферов.
В работе Паг1ь1 Е. Регйььвоьь. САСЛХ 14 (1971), 476-478, показано, что можно уменьшить время поиска, если не делать все буфера одного размера. Та же мысль и примерно в то же время пришла в голову еще нескольким автоРам [8. 1. Чьаьегз, СотР. Х 14 (1971), 109 — 112, Есс1пй Я. 'ьГа1(сеть Войввге Айс 4 (АпбпвЫЯерсешбег, 1970), 16-17) Предположим, что мы выполняем 4-путевое слияние серий равной длины Вв, располагая оперативной памятью объемом ЛХ симвачов. Если разделить память на равные буфера размером В = ЛХ/5, то придется ныполннть около Вв/В операций поиска для каждого входного файла и 4/с/В операций поиска для выходного, что в сумме дает 8Хв/В = 40йе/ЛХ операций поиска. Но если использонать четыре буфера внода размером ЛХ/6 и один буфер вывода размером ЛХ/3, то потребуется нсего лишь около 4 х (6Хс/ЛХ) + 4 х (ЗХв/М) = 36йс/М операций поиска! Время передачи в обоих случаях одно н то же, так что мы ничего не потеряем от этого изменения.
В общем случае предположим, что необходимо слить рассортированные файлы длиной Хь,...,Х,р в рассортированный файл длиной Хг ь —— Хь + + ьт и предположим, что для 1с-го файла используется буфер объемом Вы Тогда Попытаемся минимизировать эту неличяну при условии (14), считая для удобства, что Вь не обязаны быть целыми. Если увеличить В на д и уменьшить Вь на ту же небольшую неличину, то число поисков изменится на — — б В'+Б В' Вь д Вь Вь(вь д) Ву'(В'+5) т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
