Каскадное слияние
Каскадное слияние, подобно многофазному, начинается с точного распределения отрезков по лентам, хотя правила распределения другие. В качестве примера рассмотрим слияние, использующее 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;