Степень - слияние
Cтраница 2
 |
Вычисление ALPHA для дискового файла IBM 2311. [16] |
На рис. 18.7 показаны вычисленные степени слияния для 128 строк. [17]
 |
Применение метода Блэка к примерам на, и ( ALPHA число строк 16. [18] |
Заключительный шаг в определении степени слияния состоит в использовании информации, указанной на рис. 18.8, для определения времени просмотра файла. [19]
 |
Типы деревьев.| Дерево прямого двухпоточного слияния из 16 элементов. [20] |
Теперь сами понятия просмотра и степени слияния становятся расплывчатыми. [21]
При слиянии внутри одной области степень слияния не зависит от количества областей, выделенных под строки. [22]
Если отказаться от условия постоянства степени слияния, станут приемлемыми намного больше конструкций слияния. [23]
Чередование строк полезно всегда, когда степень слияния больше желаемого числа штанг считывания-записи. Чередование можно использовать при сбалансированном слиянии, как это было описано в этом разделе, или при других конструкциях слияния, в которых число рабочих областей или штанг не связано со степенью слияния. [24]
 |
Итог сбалансированного слияния. [25] |
Если число исходных, строк не кратно степени слияния, то эти отношения являются приблизительными. Длина строки в любой момент слияния равна сумме длин всех строк. При трехпоточном слиянии три строки объединяются в одну строку. Если строки неодинаковой длины и / или порядок слияния не постоянен, то, чтобы определить длину строки, получаемую при слиянии, надо просуммировать длины всех сливаемых строк. [26]
Когда число оставшихся строк становится равным либо меньшим степени слияния, достигается условие последнего просмотра. Последний просмотр слияния обычно считается специальным этапом процесса сортировки-слияния. Как правило, последний этап отвечает за интерфейс с пользователями и последующими программами обработки. Он должен разблокировать и перестроить записи; часто он может передавать специальные сообщения, которые могут быть с успехом сформированы в процессе создания физически упорядоченного файла. [27]
Размер основной памяти является решающим фактором для выбора степени слияния. При любом заданном количестве памяти пространство, какое может быть занято под любую строку, зависит от степени слияния. Как показано на рис. 18.3, при 16-поточном слиянии максимальное число записей, какое получается из каждой строки и может разместиться в основной памяти, равно 6, тогда как при двухпоточном слиянии там может поместиться 50 записей. [28]
Обратите внимание на то, что эффект от увеличения степени слияний от 6 до 10 даже при малом количестве строк падает. Сортировка 10 000 элементов, которые можно разбить на 100 строк, при слияниях степени 5, 6, 7, 8 и 9 занимает одинаковое количество просмотров. Выбор степени слияния следует рассматривать в свете количества ожидаемых строк и времени, которое потребуется центральному процессору для выполнения слияний разных степеней. [29]
При обсуждении слияния на лентах нам были хорошо известны те ограничения на степень слияния, которые накладывают машины. На слияние на дисках влияют, и даже с большой силой, те же самые ограничения. [30]
Страницы: 1 2 3 4 5