Степень - слияние
Cтраница 4
Теоретически, чем больше степень слияния, тем оно предпочтительнее. Однако тонкости внутренних возможностей машины, организация подсистемы ввода-вывода и доступная память могут создать условия, в которых предпочтительным окажется слияние небольшой степени. [46]
Формально время слияния равно сумме времен всех просмотров. Время просмотра зависит от степени слияния и влияния этой степени на производительность машины. [47]
Нужное пространство памяти зависит от степени слияния, способности аппаратуры совмещать операции чтения, записи и вычислений и сбалансированности машины. Стратегия буферизации зависит от соотношения скоростей центрального процессора и ввода-вывода машины, размера основной памяти и методов сортировки. В пакете она обычно фиксируется. Обычной стратегией является двойная буферизация, при которой каждое устройство слияния имеет два буфера. [48]
В пределах напряженности ( 5н - 7) - 103 В / м наблюдалось резкое возрастание величины зарядов и числа сателлитных капелек, которое указывает на изменение условий слияния капель. По-видимому, при больших напряженностях поля степень слияния больше и отрывание капель друг от друга происходит на большем расстоянии от экватора, чем при малых значениях напряженности поля. Капля, падающая быстрее, скользит вдоль поверхности капли, падающей с меньшей скоростью, и отрывается от ее нижней части. Действительно, знак заряда более быстро падающей капли всегда совпадал со знаком поля. [49]
Сокращенная совокупность таким образом определенных строк разделяется потом на части по рабочим областям. Количество строк в каждой части определяется степенью слияния. [50]
В конце просмотра существующие состояния определяют необходимость дополнительного просмотра такого типа. Если общее количество строк меньше, чем степень слияния, то последнее слияние между областями образует одну строку. Если число строк больше степени слияния, то необходим дополнительный промежуточный просмотр. На рис. 18.2 показаны окончание просмотра 1, дополнительный промежуточный просмотр 2 и заключительный просмотр. Заключительный просмотр отличается от промежуточного тем, что строки из разных областей объединяются в упорядоченную строку. Степень заключительного слияния равна числу оставшихся строк. [51]
При этом обеспечиваются достаточно высокие эффективность и степень слияния. Очевидно, что с помощью пяти устройств можно выполнять четырехпутевое слияние, еще более повысив эффективность. В то же время такого числа устройств не хватит даже для трехпутевой сбалансированной сортировки. [52]
Материал глав 12 и 13, где обсуждались степень слияния, буферизация, разбиение на блоки, естественно переплетается с контекстом действий, выполняемых универсальной сортировкой-слиянием. Функция этапа назначения или подготовительного этапа слияния должна определить степень слияния, произвести разбиение на блоки и буферизацию для любой генерируемой сортировки. [53]
В процессе слияния форма адресации становится менее локальной, но остается линейной. Критическим фактором конструкции является сохранение такого равновесия между степенью слияния и числом листов, при котором рее подстроки всегда находятся в оперативной памяти. Для двухпоточного слияния, как минимум, необходимо три листа: по листу для каждой строки и лист для слитой строки по мере ее образования. Добавление памяти не улучшает производительность слияния. [54]
В дисковых системах степень слияния определяется идеологией и случаем. Если в системе применяется идеология слияния максимальной поточности, то степень слияния всегда равна числу строк. Однако, такого не встретишь в современных системах, которые пытаются уравновесить степень слияния, разбиение на блоки и буферизацию. Степень слияния может вытекать и из других расчетов. В зависимости от стратегии буферизации степень слияния можно сокращать до тех пор, пока не будет найдена подходящая. [55]
 |
Слияние, первый просмотр [ IMAGE ] Слияние, формирование строк. [56] |
Идея слияния подразумевает многопросмотровый процесс, в котором при последовательных просмотрах части становятся все больше и больше до тех пор, пока заключительный просмотр не создаст часть, содержащую все элементы сортируемого списка. Необходимое для этого число просмотров зависит от числа исходных частей и степени слияния. [57]
Алгоритм слияния определяет конкретный способ чтения и записи при слиянии. Способы распределения, выбор конкретных строк для объединения с другими, регулировка степени слияния в течение процесса слияния, использование алгоритмов частичных просмотров, - все это бедует учитывать. При слиянии на лентах алгоритмом может быть один из основных способов слияния: сбалансированный, многоэтапный, каскадный, осциллирующий. Как только определен основной способ, разрабатывается стратегия частичного просмотра и определяются особые случаи. [58]
 |
Размеры блоков при слиянии разных степеней с указанием соответствующего числа обращений к данным и просмотров данных.| Временные характеристики разных слияний. быстрое обращение. [59] |
На рис. 18.3 показано общее число обращений к блокам, необходимое для разных степеней слияний при сворачивании 16 строк в одну строку. Для того чтобы определить наиболее подходящую степень для слияния 16 строк, надо найти такую степень слияния, при которой сумма времени передачи данных и времени поиска минимальна. [60]
Страницы: 1 2 3 4 5