Распределение - строка
Cтраница 2
На рис. 16.1 показан процесс осциллирующего слияния в тот момент, когда уже выполнено слияние степени k - 2 второго уровня. Теперь этот процесс начинает распределение строк еще раз. [16]
Схема осциллирующего сли яния влияет на распределение строк разными путями. Поскольку сливается лишь k - 2 строк, то имеется незначительное ослабление требований к памяти относительно разбиения на блоки и буферизации. Однако, эта выгода перекрывается характером взаимодействия между слиянием и распределением. При попытке разместить в памяти поле, необходимое для сортировки, плюс код программ слияния и распределения размер строк будет ограничен. Альтернативой является повторное использование одних и тех же блоков внутренней памяти для фрагментов кода слияния и распределения. Решение об ограничении размера области сортировки или повторном использовании памяти от этапа к этапу - это компромисс, который необходимо исследовать при каждой реализации на любой системе. [17]
В интересах эффективности системы, пользователю может понадобиться вести какие-нибудь протоколы на этапе распределения. На системе с шестью лентами для распределения строк ему будет доступно скорее четыре, а не пять лент. Однако, пользователь хочет в течение слияния полностью использовать преимущество системы с шестью лентами. Этот случай показан на рис. 14.13. Лента 0 является лентой ввода. [18]
По мере продолжения процесса на лентопротяжных устройствах создаются строки разной длины. Когда данные исчерпаны, ( к - 2) - поточное слияние формирует заключительную строку. Во время слияния, в зависимости от распределения строк и их направления, может возникать необходимость в частичных просмотрах. [19]
Распределение строк на ленте при любой схеме слияния заданной степени включает выбор устройств ввода-вывода для получения строк в соответствии с назначениями данного слияния. Есть два основных типа алгоритмов - сбалансированные и несбалансированные. Несбалансированное распределение размещает строки так, чтобы достичь идеального уровня. Понятие идеальных уровней будет описано в связи с каждым типом несбалансированного слияния; в общем случае, идеальный уровень - это такое распределение строк, которое позволит несбалансированному слиянию работать без изменения алгоритма слияния от просмотра к просмотру. [20]
 |
Влияние длинных строк. [21] |
Вопрос о длине строки может тем или иным образом способствовать использованию выбора с заменой, но есть нокоторые соображения, которые могут сделать этот метод невыгодным. При двухпоточном слиянии выбор с заменой за счет длинных строк может сэкономить один просмотр. Для очень больших файлов это может быть несущественно. Эта разница сократит количество просмотров с 12 до 11, давая экономию менее 10 процентов при двухпоточном слиянии. Если же есть какие-нибудь дополнительные затраты, связанные с распределением длинных строк, то преимущество длинных строк вполне может стать эфемерным. [22]
Страницы: 1 2