Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 97
Текст из файла (страница 97)
Эта конструкция при а = ~9 = 1 проиллюстрирована в качестве примера в табл. 1. Краткие описания соответствующих оптимальных деревьев приводятся в правой части таблицы; элемент '"4:9:9" для и = 22, например, означает, что оптимальное дерево 7ю с 22 листьями можно получить в результате объединения 74, 7э и 7э (рис. 93). Оптимальное дерево не является однозначной структурой; например, элемент 5:6:9 был бы столь же хорснпим, как и 4:9:9. Рно. 93. Оптимальный способ слияния 22 начальных серий равной длины, если а =:,9 в теореме Н. Эта схема позволяет минимизировать время поиска при предположениях, приведших к формуле (2). Выражение (2) показывает, что всегда, когда используются Р+ 1 буферов равных объемов, будет действительным соотношение о < 6.
Предельный случай, когда о = Д показанный в табл. 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 Дерево н яния — за почти 6 мнн: в ятоге имеем 12.4 мнн. Если использовать выбор с замещением, то оптимальное дерево для Я = 64 оказывается одинаково неинтересным (два прохода 3-путевого слияния); начальный распределительный проход осуществляется примерно за 3.3 мин, каждый проход слияния — примерно за 4.5 мин, а оценка общего времени составляет 12.6 мин.
Не забудьте, что в обоих зтнх методах фактически полностью исключается совмещение чтения/записи/вычислений с тем, чтобы иметь ббльшие буфера (для уменьшения времени поиска). Ни одна из этих оценок не включает время, аоторое может потребоваться для операций контрольного чтения. На практике последний проход слияния отличается от остальных; например, выводнь)е данные часто редактируются и/или записываются на ленту. В таких счучаях дерево, изображающее схему слияния, следует выбирать с использованием нного критерия оптимальности в корневом узле.
*Подробности об оптимальных деревьях. В теоремах Н и К интересно рассмотреть предельный случай, когда,9 = О, несмотря на то что на практике обычно возникает соотношение между параметрами вида О < а <,9. Какое дерево с и листьями имеет наименьшую возможную длину степенного путиу Любопытно, что в этом случае наилучшим оказывается 3-путевое слияние. Теорема Ь. Длина степенного пути дерева с и листьями никогда не будет меньше, чем ) Здп + 2(п — 3"), если 2 . 34 ' < и < 34; (6) )( Збп + 4(п — 34), ецш 3» < п < 2 34. 1 0,0 2 6,2 0,1 3 12,3 6,1 4 20,4 12,1 5 30,5 18,2 6 42,2 243 7 52,3 32,3 8 62,3 40,4 9 72,3 50,4 10 84,3 60,5 11 96,3 72,4 12 108,3 82,4 13 121,4 92,4 14 134,4 102,5 !5 !47,4 114,5 16 160,4 124,7 17 175,4 134,8 18 190,4 144,9 19 205,4 156,9 20 220,4 )68,9 22 252,3 192,Ш 23 266,3 204,11 24 282,3 216,12 25 296,3 229,12 0,1 6,1 0,1 12,1 6,1 18,1 12,1 24,1 !8,! 30,2 24,1 36„3 30,1 44.3 36,1 52,3 42,2 60,4 48,3 70,4 56,3 80,4 64,3 90.4 72,3 102,4 80,4 112,4 90,4 122,4 100,4 Г32,5 1) 0,4 !44,4 120,5 154,4 132,4 164,4 142,4 174,5 152,4 186,5 162,5 196,7 174,4 0,1 6,1 О,! !2,1 6,1 18,1 12,1 24,1 !8,1 30,! 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 8О,З 100,4 88,3 110,4 96,3 120,4 104„3 !30,4 112,3 140,4 120,4 !50,5 !30,4 0,1 6,1 0,1 12,1 6,1 !8,1 12,! 24,1 18,! 30,1 24,1 36,1 30,1 42,1 36,1 48, 1 42,! 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 100,3 90,2 108,3 96,3 116,3 104,3 О,) 6,1 0,1 121 б! 01 18,1 12,1 6,1 24,1 18,1 12,1 30,! 24,! 18,1 36,1 30,1 24,1 42,1 36,1 30,1 48,1 42,1 36,1 54,1 48,1 42,1 60 1 54,1 48,1 66,1 60,1 54,1 72,1 66,1 60,1 78,1 72,1 66,1 84,1 78,1 72,1 90,1 84,1 78,1 96,! 90,! 84,1 1 1:1 2 1: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 3:4:4 11 0,1 4М:4 12 6,1 3:3:3;4 13 12,1 30И4:4 14 18,1 3:4:4:4 15 24,1 4:4:4:4 16 30,1 4:4:4:5 17 36,1 4:4:о:5 !8 42,1 4;5;5:5 19 48,1 5:55И5 20 54,1 4:4:4:4:5 21 60.,1 4:9:9 22 66,1 5:9:9 23 72,1 5:9:10 24 78,1 7:9:9 25 Тернарные деревья Т, Определенные правилами (7) Я1 19+ 1 ~~~т1 имеют мнннмальную длину степенного пути.
Доказательства. Обратите внимание на то, что /(п) — вмпдклал функция, т. е. /(и + 1) — /(и) > /(н) — /(и — 1) прн всех и > 2. (д) Это свойство существенно в соответствии со следующей леммой, которая двойствен- на результату упр. 2.3.4.5-17. лемма с Функпня д(п)~ Определенная на НОложнтю!Нных целых числах, удовле" Хворает условию ш1п (д(Ж)+д(п — й)) = дИН/2))+д((п/21), и > 2, (д) ткни а только то1да, когда она выпуклая. Доказательство. Если д(п+ 1) — д(п) < д(п) — д(п — Ц при некотором и > 2, то имеем д(п + 1) + д(п — 1) < д(п) + д(п), .что противоречит (9), Обратно, если (8) выполняется для д и если 1 < к < и — Й, то в силу выпуклости д(х+ 1) + д(п — к -1) < д(к) + д(п — к). Последнюю часть доказательства леммы С можно обобщить для любого т > 2 и НОказать, чтО ппп (д(п|) + .
+ д(п,„)) К1+ +к Рн КОР.,Н й1 = д((п/т)) + д(((п + 1)/иЦ) + ° ° + д(!(и+ т — 1)/т) ), (Ю) если д выпукла. Пусть (и) = Щп/т)) + /(((и+ 1)/т)) + . + /(((и+ т — 1)/т)). (11) Доказательство теоремы Ь будет полным, если убедиться, что /з(п) + Зп = /(и) и / (и) + тп > /(и) при всех т > 2 (см. Упр. 11). 3 Было бы очень хорошо, если бы оптимальные деревья всегда характеризовались так же четко, как в теореме Е. Но результаты для О =,3, которые приведены в табл. 1, показывают. что функния А1(п) не всегда выпукла.
На самом деле данные, приведенные в табл. 1, достаточны, чтобы опровергнуть большинство простых предположений об оптимальных деревьях! Ыы, однако, можем спасти часть теоремы 1, для общего случая. М. Шлюмбергер (М. Ясп(ншЬегбег) и Ж. Вуйлемен (Л. х'и!!!еш(п) показали, что высоких порядков слияния всегда можно избежать. Теорема М. Есля даны О Н,З, как в теореме Н, то существует оптимальное дерево, в котором степень любого узла ие превосходит (12) Доказательство.
Пусть пь,..., пы — положителыьые целые числа„такие, что пь + ° . + и = и, А(нь) + +А(п ) = А (и) и пь « и, и предположим, что пь > с((а,д) + 1. Пусть /с -- значение, при котором достаьгается минимум в (12); покажем, что ап(т — й) + бп+ А «(и) < апт+ бп+ А (и), (13) и, следовательно, минимум в (4) всегда достигается при некотором т < с((а,/Х).
По определению, поскольку т > й + 2, мы должны иметь Аи-«(и) < Аь(пь+.. +п««ь)+Аь(п««з)+ ..+Аь(п ) < а(пь+ .+п«еь)(Л+1)+6(пь+ +н««ь)+Аь(пь)+ ° +Аь(п ) = (а(5+1)+д)(пь+ +п«еь)+А (и) < (а(й+1)+6)(/с+1)п/т+А„,(п). Отсюда легко выводится (13). (Тщательный анализ этого доказательства показывает, что оценка (12) является "наилучшей из возможных" в том смысле, что некоторые оптимальные деревья должны иметь узлы степени ьХ(а„З); см.
у.пр. 13.) 1 Для построения в теореме К требуется 0(Л'~) ячеек памяти и 0(Льт(ойа') шагов для вычисления А,„(п) при 1 < т < п < Л'; в теореме М показано, что необходимо только 0(Л') ячеек и 0(1т'~) шагов. Шлюмбергер и Вуйлемен открыли еще несколько очень интересных свойств оптимальных деревьев [Асса Хгь/огшас(са 3 (1973), 25--36[. Величина асимптотического выражения для Аь(п) выводится, .квк продемонстрировано в упр. 9, вЕгце один способ распределения буферов. В работе )УатЫ Е.
Гегйозоп, САСМ 14 (1971), 476-478, показано, что можно уменьшить время поиска, если не делать все буфера одного размера. Та же мысль н примерно в то же время пришла в гьхчову еще нескольким авторам [Я. 1. Жаьегэ, Сошр. Х 14 (1971), 109 — 112, Ен1пк Я. %а((сег, Яо/сьеаге Абе 4 (АпйььвЫЯерьвтЬег, 1970),. 16-17). Предположим, что мы выполняем 4-путевое слияние серий равной длины Хв, располагая оперативной памятью объемом М символов. Если разделить память на равные буфера размером В = ЛХ/5, то придется выполнить около Ьв/В операций поиска для каждого входного файла н 46сь/В операций поиска для выходного, что в сумме дает 86в/В =. 40/в/М операций поиска.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
