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