Фибоначчиево слияние

Многофазное слияние

Рассмотрим различные методы распределения отрезков по файлам. Предположим сначала, что у нас имеется 3 файла: F1, F2, F3. Можно воспользоваться сбалансированным слиянием:

1. Распределить начальные отрезки на F1 и F2.

2. Слить отрезки с F1, F2 на F3 и остановиться, если F3 содержит только 1 отрезок

3. Скопировать с F3 отрезки попеременно на F1, F2 и вернуться к шагу 2

Если начальное распределение дало S отрезков, то первый проход слияния даст S/2 отрезков на F3, второй - S/4 и т.д. Если, например, 17 £ S £ 32, то произойдет:

- 1 проход распределения,

- 5 проходов слияния,

- 4 прохода копирования,

всего 2log2S проходов по данным.

Можно обойтись половиной копирований, если использовать двухфазную процедуру:

1. Распределить начальные отрезки попеременно на F1, F2.

2. Слить отрезки с F1, F2 на F3 и остановиться, если F3 содержит один отрезок

3. Скопировать половину отрезков с F3 на F1

4. Слить отрезки с F1, F3 на F2, остановиться, если получен единственный отрезок

5. Скопировать половину отрезков с F2 на F1 и вернуться к шагу 2

Заметим, что много времени тратится на копирование, которое не улучшает структуру данных.

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