Каскадное слияние

Каскадное слияние, подобно многофазному, начинается с точного распределения отрезков по лентам, хотя правила распределения другие. В качестве примера рассмотрим слияние, использующее 6 файлов. Каждая строка в таблице, приведенной ниже, представляет полный проход по всем данным.

№ прохода F1 F2 F3 F4 F5 F6 Всего отрезков
55*1 50*1 41*1 29*1 15*1 -
- 5*1 9*2 12*3 14*4 15*5
5*15 4*14 3*12 2*9 1*5 -
- 1*15 1*29 1*41 1*50 1*55
1*190 - - - - -

Проход 2, например, поучается выполнением 5-путеврго слияния с F1…F5 на F6, пока не опустеет F5, затем 4-путевого слияния с F1…F4 на F5, 3-путевого с F1, F2, F3 на F4, 2-путевого с F1, F2 на F3, и, наконец, однопутевого (копирования) – с F1 на F2. Подробно второй проход представлен в таблице:

Слияние F1 F2 F3 F4 F5 F6
исходно 55*1 50*1 41*1 29*1 15*1 -
5-путевое 40*1 35*1 26*1 14*1 - 15*5
4-путевое 26*1 21*1 12*1 - 14*4  
3-путевое 14*1 9*1 - 12*3    
3-путевое 5*1 - 9*2      
копирование - 5*1        

Ясно, что операция копирования излишня и оставлена в описании алгоритма только для сохранения единообразия процесса.

Рассматривая процесс в обратном порядке, и игнорируя выходной файл, можно вывести точные распределения отрезков по файлам на любом этапе:

Уровень F1 F2 F3 F4 F5
. . . . . .
n an bn cn dn en
N+1 an+bn+cn dn+en an+bn +cn+dn an+bn+cn an+bn an

Числа в распределении носят название каскадных.








Дата добавления: 2014-12-02; просмотров: 1533;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.