Частичный просмотр
Cтраница 3
На рис. 14.4 показан этап слияния для распределения, изображенного на рис. 14.3. Каждый этап этого слияния поднимает начальной уровень до следующего идеального уровня, а число строк уменьшается в обобщенной последовательности Фибоначчи. На рис. 14.4 имеется пять частичных просмотров, эквивалентных 3.26 полным просмотрам данных. [31]
Интересный и эффективный, хотя и несколько сложный, подход для распределения при каскадном слиянии был создан для пакета сортировки SODA ( Sequential Ordering of DAta) для UNIVAC III. Он рассматривается здесь, потому что алгоритм частичного просмотра для каскадного слияния ранее не был опубликован в широкой литературе. [32]
Когда метод парных просмотров объединяется с методом частичных просмотров, возможна значительная экономия перемещения строк. В методе пар частичных просмотров все идеальные уровни, получаемые при нечетном числе просмотров, рассматриваются, как неидеальное межуровневое распределение. [33]
Слияния, описанные в этой книге, чувствительны к числу строк, а кроме этого, к появлению определенных чисел - к так называемым совершенным распределениям. Чувствительность к совершенным числам может быть понижена методами частичных просмотров. Однако, слияние, которое обычно менее эффективно, чем другие при данном числе лент, может стать эффективнее, если его совершенные уровни распределены по этому числу лент. Реакция слияний на плохие. Сбалансированное слияние будет тратить дополнительный полный просмотр Данных, если эффективная степень слияния не достигнута, а частичные просмотры не используются. [34]
Количество использований слоя на каждом уровне определяется числом строк на каждой ленте на предыдущем уровне. Количество удачно распределенных слоев определяет число строк, которое надо переместить с каждой ленты на частичном просмотре. [35]
Алгоритм слияния определяет конкретный способ чтения и записи при слиянии. Способы распределения, выбор конкретных строк для объединения с другими, регулировка степени слияния в течение процесса слияния, использование алгоритмов частичных просмотров, - все это бедует учитывать. При слиянии на лентах алгоритмом может быть один из основных способов слияния: сбалансированный, многоэтапный, каскадный, осциллирующий. Как только определен основной способ, разрабатывается стратегия частичного просмотра и определяются особые случаи. [36]
Установка в процессе сортировки-слияния точек, которые представляют места возврата, является важной характеристикой конструкции пакета. Общая процедура контрольной точки встраивается в сортировку и обязана устанавливать контрольные точки в конце просмотра распределения и в конце каждого просмотра слияния или частичного просмотра. Разные слияния отличаются тем, когда берутся контрольные точки, но все схожи в том, что пытаются обеспечить контрольные точки возврата так, чтобы защитить пользователя в случае ошибки от потери более чем одного просмотра данных. [37]
Когда метод парных просмотров объединяется с методом частичных просмотров, возможна значительная экономия перемещения строк. В методе пар частичных просмотров все идеальные уровни, получаемые при нечетном числе просмотров, рассматриваются, как неидеальное межуровневое распределение. [38]
Решающей разницей между распределениями является положение строк на лентах, когда идеальный уровень не может быть достигнут. Если идеальный уровень не достигнут, то для многоэтапного слияния нужен какой-то способ настройки. Таким способом может быть частичный просмотр или использование фиктивных величин. [39]
 |
Перекрестное слияние. [40] |
При достижении базового уровня вместо ( k - 2) - поточного слияния второго уровня, как в осциллирующем методе, в перекрестном методе возобновляется формирование строк. По существу каждое слияние - это частичный просмотр, который использует только часть строк с ленты ввода. [41]
Частичные просмотры пытаются сместить количество просмотров от flog2Af ] ближе к log2 M. Заметим, что обратное чтение не слишком усложняет рис. 13.9, где Го, Ту и Г2 читаются в обратном направлении при формировании строки на Та. Все строки, формируемые в течение двух частичных просмотров, являются убывающими. [42]
По мере продолжения процесса на лентопротяжных устройствах создаются строки разной длины. Когда данные исчерпаны, ( к - 2) - поточное слияние формирует заключительную строку. Во время слияния, в зависимости от распределения строк и их направления, может возникать необходимость в частичных просмотрах. [43]
Рассмотрим 20-ленточную систему со 145 начальными строками. Многоэтапное слияние упорядочит эти данные за 2.54 просмотра. Несмотря на то, что теоретически эффективность сбалансированного слияния при k 20 выше, многоэтапное слияние оказывается более эффективным, потому что в данном случае у него совершенный уровень, тогда как для сбалансированного слияния 45 - это плохой уровень. Важность частичных просмотров для сбалансированного слияния можно проиллюстрировать тем, что при частичных просмотрах оно может упорядочить 145 строк за 2.36 просмотров данных. При 100 строках, образующих совершенный уровень для сбалансированного слияния, это слияние превосходит по производительности многоэтапное: 2.00 просмотров данных против 2.37 просмотров. [44]
Алгоритм слияния определяет конкретный способ чтения и записи при слиянии. Способы распределения, выбор конкретных строк для объединения с другими, регулировка степени слияния в течение процесса слияния, использование алгоритмов частичных просмотров, - все это бедует учитывать. При слиянии на лентах алгоритмом может быть один из основных способов слияния: сбалансированный, многоэтапный, каскадный, осциллирующий. Как только определен основной способ, разрабатывается стратегия частичного просмотра и определяются особые случаи. [45]
Страницы: 1 2 3 4