Cтраница 4
Когда 7 з исчерпана, она перематывается, и в качестве этапа 2 выполняется двухпоточное слияние степени ft - - 2 пяти строк. Когда Т2 исчерпана, она перематывается и происходит однопоточное слияние ( степени k - 3 или этап копирования) на Тг. Когда этот этап ( 3) завершен, то уже достигнут новый идеальный уровень, а данный просмотр закончен. Просмотр каскадного слияния состоит из последовательности этапов. Каждый этап имеет собственную степень слияния. Каждый этап завершается исчерпанием ленты ввода. После перемотки опустошенная лента используется на следующем этапе для вывода. Лента вывода на каждом этапе также перематывается. Каждый просмотр состоит из k - 1 этапов. Каждый этап требует двух перемоток, так что при каждом просмотре выполняется 2 ( - 1) перемоток. Перемотка исчерпанной ленты должна быть закончена до начала следующего этапа, так как на следующем этапе она будет лентой вывода. Это время перемотки всегда добавляется к общему времени слияния. [46]
Знание числа строк позволяет выбирать метод слияния более осознанно. Помимо того, что число строк влияет на эффективность слияния, у точного предвидения есть и другие преимущества. Если число просмотров известно или может быть оценено на основе ожидаемого числа-строк, то направление исходных строк можно выбрать так, чтобы избежать просмотров копирования при каскадном, сбалансированном или осциллирующем слияниях. При каскадных слияниях число просмотров необходимо знать при любом алгоритме определения формы возрастающих и убывающих строк во избежание перемоток или копирования неисчерпанных лент. [47]
На восьми лентах каскадное предпочтительнее многоэтапного при 145 строках, а многоэтапное предпочтительнее каскадного при 45 строках. В общем случае, в силу своей способности просматривать строки, каскадное слияние более эффективно при большом числе строк, тогда как многоэтапное эффективнее при меньшем их числе. Для достижения нового уровня при каскадном слиянии надо обработать намного больше строк, и эта тенденция становится особенно ярко выраженной на высоких уровнях. Однако и при меньших совокупностях строк бывает, что каскадное слияние предпочтительнее. Это случается тогда, когда уровни очень близки к совершенным уровням каскадного слияния. При плохом уровне каскадного слияния уменьшению числа перемещаемых строк могут способствовать методы частичных просмотров. При большом количестве лент число строк, при котором каскадное слияние становится предпочтительным, намного меньше. При малом количестве лент ( например, k 4) многоэтапное слияние превосходно во всех отношениях. [48]
На восьми лентах каскадное предпочтительнее многоэтапного при 145 строках, а многоэтапное предпочтительнее каскадного при 45 строках. В общем случае, в силу своей способности просматривать строки, каскадное слияние более эффективно при большом числе строк, тогда как многоэтапное эффективнее при меньшем их числе. Для достижения нового уровня при каскадном слиянии надо обработать намного больше строк, и эта тенденция становится особенно ярко выраженной на высоких уровнях. Однако и при меньших совокупностях строк бывает, что каскадное слияние предпочтительнее. Это случается тогда, когда уровни очень близки к совершенным уровням каскадного слияния. При плохом уровне каскадного слияния уменьшению числа перемещаемых строк могут способствовать методы частичных просмотров. При большом количестве лент число строк, при котором каскадное слияние становится предпочтительным, намного меньше. При малом количестве лент ( например, k 4) многоэтапное слияние превосходно во всех отношениях. [49]
На восьми лентах каскадное предпочтительнее многоэтапного при 145 строках, а многоэтапное предпочтительнее каскадного при 45 строках. В общем случае, в силу своей способности просматривать строки, каскадное слияние более эффективно при большом числе строк, тогда как многоэтапное эффективнее при меньшем их числе. Для достижения нового уровня при каскадном слиянии надо обработать намного больше строк, и эта тенденция становится особенно ярко выраженной на высоких уровнях. Однако и при меньших совокупностях строк бывает, что каскадное слияние предпочтительнее. Это случается тогда, когда уровни очень близки к совершенным уровням каскадного слияния. При плохом уровне каскадного слияния уменьшению числа перемещаемых строк могут способствовать методы частичных просмотров. При большом количестве лент число строк, при котором каскадное слияние становится предпочтительным, намного меньше. При малом количестве лент ( например, k 4) многоэтапное слияние превосходно во всех отношениях. [50]
На восьми лентах каскадное предпочтительнее многоэтапного при 145 строках, а многоэтапное предпочтительнее каскадного при 45 строках. В общем случае, в силу своей способности просматривать строки, каскадное слияние более эффективно при большом числе строк, тогда как многоэтапное эффективнее при меньшем их числе. Для достижения нового уровня при каскадном слиянии надо обработать намного больше строк, и эта тенденция становится особенно ярко выраженной на высоких уровнях. Однако и при меньших совокупностях строк бывает, что каскадное слияние предпочтительнее. Это случается тогда, когда уровни очень близки к совершенным уровням каскадного слияния. При плохом уровне каскадного слияния уменьшению числа перемещаемых строк могут способствовать методы частичных просмотров. При большом количестве лент число строк, при котором каскадное слияние становится предпочтительным, намного меньше. При малом количестве лент ( например, k 4) многоэтапное слияние превосходно во всех отношениях. [51]
На восьми лентах каскадное предпочтительнее многоэтапного при 145 строках, а многоэтапное предпочтительнее каскадного при 45 строках. В общем случае, в силу своей способности просматривать строки, каскадное слияние более эффективно при большом числе строк, тогда как многоэтапное эффективнее при меньшем их числе. Для достижения нового уровня при каскадном слиянии надо обработать намного больше строк, и эта тенденция становится особенно ярко выраженной на высоких уровнях. Однако и при меньших совокупностях строк бывает, что каскадное слияние предпочтительнее. Это случается тогда, когда уровни очень близки к совершенным уровням каскадного слияния. При плохом уровне каскадного слияния уменьшению числа перемещаемых строк могут способствовать методы частичных просмотров. При большом количестве лент число строк, при котором каскадное слияние становится предпочтительным, намного меньше. При малом количестве лент ( например, k 4) многоэтапное слияние превосходно во всех отношениях. [52]