Фибоначчиево слияние
В действительности, можно полностью устранить копирование, если начать с fn отрезков в файле F1 и fn-1 отрезков в F2, где fn и
fn-1 – последовательные числа Фибоначчи. Таблица, приведенная ниже, поясняет процесс слияния. Элемент таблицы вида A*Bобозначает А отрезков относительной длины В.
| Фаза | F1 | F2 | F3 | Число обрабатываемых отрезков |
| 13*1 | 8*1 | Пусто | ||
| 5*1 | Пусто | 8*2 | ||
| Пусто | 5*3 | 3*2 | ||
| 3*5 | 2*3 | Пусто | ||
| 1*5 | Пусто | 2*8 | ||
| Пусто | 1*13 | 1*8 | ||
| 1*21 | Пусто | Пусто |
Суммарное число проходов по данным составит 
, в то время, как двухфазная процедура затратила бы 8 проходов. Эту идею можно обобщить на N входных файлов, используя N-1 –путевое слияние. В качестве примера рассмотрим случай N=6 при числе начальных отрезков 129.
| Фаза | F1 | F2 | F3 | F4 | F5 | F6 | Число отрезков |
| 31*1 | 30*1 | 28*1 | 24*1 | 16*1 | - | ||
| 15*1 | 14*1 | 12*1 | 8*1 | - | 16*5 | ||
| 7*1 | 6*1 | 4*1 | - | 8*9 | 8*5 | ||
| 3*1 | 2*1 | - | 4*17 | 4*9 | 4*5 | ||
| 1*1 | - | 2*33 | 3*17 | 2*9 | 2*5 | ||
| - | 1*65 | 1*33 | 1*17 | 1*9 | 1*5 | ||
| 1*129 | - | - | - | - | - |
Чтобы метод работал, необходимо после каждой фазы иметь точное "фибоначчиево" распределение отрезков по файлам. Для этого некоторые файлы можно дополнить фиктивными отрезками нулевой длины. Точное фибоначчиево распределение можно получить, прокручивая рассмотренную схему в обратном порядке, циклически переставляя содержимое файлов и игнорируя выходной файл. При N=6 имеем следующее распределение отрезков:
| Уровень | F1 | F2 | F3 | F4 | F5 | Сумма |
| . | . | . | . | . | . | . |
| n | an | bn | cn | dn | en | tn |
| n+1 | an+bn | an+cn | an+dn | an+en | an | tn+4an |
Из приведенной таблицы следует, что
en=an-1
dn=an-1+en-1=an-1+an-2
cn=an-1+dn-1=an-1+an-2+an-3
bn=an-1+cn-1=an-1+an-2+an-3+an-4
an=an-1+bn-1= an-1+an-2+an-3+an-4+an-5,
где a0=1 и an=0 при n<0.
Числа Фибоначчи порядка р 
определяются правилами:
при n ³ p,
при 0 £ n £ p-2, 
=1.
В общем случае, если положить p=N-1, распределения отрезков по лентам в многофазном слиянии для N файлов аналогичным образом соответствуют числам Фибоначчи порядка р. В точном распределении n-го уровня в k-ом файле будет
начальных отрезков для 1 £ k £ p, а общее количество начальных отрезков во всех файлах составит
Дата добавления: 2014-12-02; просмотров: 908;