Частичный просмотр

Cтраница 4

Заключительные частичные просмотры. Просмотр 2 сокращен до однопоточного слияния. [46]

Альтернативой условию отслеживания состояний в конце слияния является настройка слияния вначале. Она включает серию копирований, слияний и перемоток с целью перемещения некоторых строк для того, чтобы их число стало кратно степени слияния до начала полных просмотров слияния. Этот подход в общем случае является наиболее мощным. Рассмотрим рис. 13.9, на котором показана настройка частичных просмотров. Мы не утверждаем, что эта настройка является наилучшей в данном случае; тем не менее мы показываем ее, чтобы проиллюстрировать сам принцип. В этом примере предполагается, что ленты читаются только вперед. Сначала сливается по одной строке с каждой ленты. При этом возникает состояние, изображенное в первой строчке рис. 13.9. Теперь осталось 28 строк. [47]

Компромиссное слияние с тремя этапами. [48]

Это название отражает то место, какое это слияние занимает между предельными случаями, которыми являются многоэтапное и каскадное слияния. Эта промежуточность вытекает из формы этапов слияния, выполняемых в течение просмотра слияния. У многоэтапного слияния степени k - 1 на один частичный просмотр приходится один этап. У каскадного - на один просмотр приходится k - 1 отдельных этапов. [49]

Рассмотрим 20-ленточную систему со 145 начальными строками. Многоэтапное слияние упорядочит эти данные за 2.54 просмотра. Несмотря на то, что теоретически эффективность сбалансированного слияния при k 20 выше, многоэтапное слияние оказывается более эффективным, потому что в данном случае у него совершенный уровень, тогда как для сбалансированного слияния 45 - это плохой уровень. Важность частичных просмотров для сбалансированного слияния можно проиллюстрировать тем, что при частичных просмотрах оно может упорядочить 145 строк за 2.36 просмотров данных. При 100 строках, образующих совершенный уровень для сбалансированного слияния, это слияние превосходит по производительности многоэтапное: 2.00 просмотров данных против 2.37 просмотров. [50]

Слияния, описанные в этой книге, чувствительны к числу строк, а кроме этого, к появлению определенных чисел - к так называемым совершенным распределениям. Чувствительность к совершенным числам может быть понижена методами частичных просмотров. Однако, слияние, которое обычно менее эффективно, чем другие при данном числе лент, может стать эффективнее, если его совершенные уровни распределены по этому числу лент. Реакция слияний на плохие. Сбалансированное слияние будет тратить дополнительный полный просмотр Данных, если эффективная степень слияния не достигнута, а частичные просмотры не используются. [51]

Альтернативой копированию является частичный просмотр, где понятие просмотра ослаблено, и сортировка переходит не от просмотра к просмотру, а от этапа к этапу. Вернемся к рис. 9.12. Строка 33 - копия строки 25, которая создается в конце просмотра 2 и освобождает область C / D. Однако при других стратегиях управления памятью копировать эту строку было бы не обязательно. Ее можно было бы оставить там, где она есть, совсем не изменив характер последующих слияний. Поскольку она в равной степени доступна из любой позиции, ее перемещать абсолютно незачем. При этом слияния на рис. 9.1, по правде говоря, не образуют просмотра, так как обрабатываются не все данные. Частичный просмотр или этап завершен, и следующий начинается с состояния, изображенного на рис. 9.13, с той лишь разницей, что последовательность 4, 9, 16 расположена в другом месте. [52]

На восьми лентах каскадное предпочтительнее многоэтапного при 145 строках, а многоэтапное предпочтительнее каскадного при 45 строках. В общем случае, в силу своей способности просматривать строки, каскадное слияние более эффективно при большом числе строк, тогда как многоэтапное эффективнее при меньшем их числе. Для достижения нового уровня при каскадном слиянии надо обработать намного больше строк, и эта тенденция становится особенно ярко выраженной на высоких уровнях. Однако и при меньших совокупностях строк бывает, что каскадное слияние предпочтительнее. Это случается тогда, когда уровни очень близки к совершенным уровням каскадного слияния. При плохом уровне каскадного слияния уменьшению числа перемещаемых строк могут способствовать методы частичных просмотров. При большом количестве лент число строк, при котором каскадное слияние становится предпочтительным, намного меньше. При малом количестве лент ( например, k 4) многоэтапное слияние превосходно во всех отношениях. [53]

Страницы: 1 2 3 4