PHƯƠNG PHÁP TRỘN ĐA PHA

(Polyphase Merge)

Phương pháp trộn đa lối cân bằng đã loại bỏ các phép sao chép thuần túy thông qua việc gộp quá trình phân phối và quá trình trộn trong cùng một giai đoạn. Tuy nhiên các tập tin các tập tin chưa được sử dụng một cách có hiệu quả bởi vì trong cùng một lần duyệt thì phân nửa số tập tin luôn luôn giữ vai trò trộn (nguồn) và phân nửa số tập tin luôn luôn giữ vai trò phân phối (đích). Ta có thể cải tiến phương pháp trên bằng cách giải quyết thay đổi vai trò của các tập tin trong cùng một lần duyệt phương pháp này gọi là phương pháp trộn đa pha.

Ta xét ví dụ sau với 3 tập tin f₁, f₂, f₃

Bước 1: Phân phối luân phiên các run ban đầu của f₀ vào f₁ và f₂

Bước 2: Trộn các run của f₁, f₂ vào f₃ . Giải thuật kết thúc nếu f₃ chỉ có một run

Bước 3: Chép nửa run của f₃ vào f₁

Bước 4: Trộn các run của f₁ và f₃ vào f₂. Giải thuật kết thúc nếu f₂ chỉ có một run.

Bước 5: Chép nửa số run của f₂ vào f₁. Lặp lại bước 2.

Phương pháp này còn có nhược điểm là mất thời gian sao chép nửa số run của tập tin này vào tập tin kia. Việc sao chép này có thể loại bỏ nếu ta bắt đầu với Fn run của tập tin f₁ và Fn_-1 run của tập tin f₂, với Fn và Fn_-1 là các số liên tiếp trong dãy Fibonacci.

Chúng ta xem xét các ví dụ sau:

Ví dụ 1: Trường hợp n=7, tổng số run ban đầu là 13+8=21 run

Phase	F 1	F2	F3
0	1, 1, 1, 1, 1, 1, 1, 1	1, 1, 1, 1, 1		Sort
1	1, 1, 1,		2, 2, 2, 2, 2	Merge 1
2		3, 3, 3	2, 2	Merge 2
3	5, 5	3		Merge 3
4	5		8	Merge4
5		13		Merge 5
6	21			Merge 6

Phase 0: Phân phối các run ban đầu

Phase 1: Trộn 8 run của f1 và f2 vào f3

Phase 2: Trộn 5 run của f1 và f3 vào f2

Phase 3: Trộn 3 run của f2 và f3 vào f1

Phase 4: Trộn 2 run của f1 và f2 vào f3

Phase 5: Trộn 1 run của f1 và f3 vào f2

Phase 6: Trộn 1 run của f2 và f3 vào f1

Ví dụ 2:

Phase	T6	T5	T4	T3	T2	T1	Tổng số runs được xữ lý
Phase 0	131	130	128	124	116	-	129
Phase 1	115	114	112	18	-	516	80
Phase 2	17	16	14	-	98	58	72
Phase 3	13	12	-	174	94	54	68
Phase 4	11	-	332	172	92	52	66
Phase 5	-	651	331	171	91	51	65
Phase 6	1291	-	-	-	-	-	129

Phase 0: Phân phối các run ban đầu

Phase 1: Trộn 16 run từ T2 đến T6 vào T1

Phase 2: Trộn 8 run của T1, T3, T4, T5, T6 vào T2

Phase 3: Trộn 4 run của T1, T2, T4, T5, T6 vào T3

Phase 4: Trộn 2 run của T6, T5, T3, T1, T6 vào T4

Phase 5: Trộn 1 run của T1, T2, T3, T4, T6 vào T5

Phase 6: Trộn 1 run từ T1 đến T5 vào T6.

Xem xét bảng trên ( từ dưới lên) chúng ta thấy có 7 bước phân bố theo dãy Fibonacci bậc 4 là: {1,0,0,0,0}, {1,1,1,1,1}, {2,2,2,2,1}, {4,4,4,3,2}, {8,8,7,6,4}, {16,15,14,12,8}, và {31,30,28,24,16}.

Với Số tập tin T=6 bảng sau cho thấy số run ban đầu được phân bố thích hợp:

Phân bố Fibonacci hoàn hảo với T=6
Level	T6	T5	T4	T3	T2	Total Runs
0	1	0	0	0	0	1
1	1	1	1	1	1	5
2	2	2	2	2	1	9
3	4	4	4	3	2	17
4	8	8	7	6	4	33
5	16	15	14	12	8	65
6	31	30	28	24	16	129
7	61	59	55	47	31	253
8	120	116	108	92	61	497
-	-	-	-	-	-	-
n	an	bn	cn	dn	en	tn
n+1	an+bn	an+cn	an+dn	an+en	an	tn+4an

Trong ví dụ 1, số run phân phối ban đầu cho các tập tin là 2 số Fibonacci kế tiếp nhau của dãy Fibonacci bậc 1: 0, 1, 1, 2, 3, 5, 8 . . .

Trong ví dụ 2 số run ban đầu phân bố cho các tập tin theo dãy Fibonacci bậc 4: 0, 0, 0, 0, 1, 1, 2, 4, 8, 16 . . .

Dãy Fibonacci bậc P tổng quát được định nghĩa như sau:

F^(p)_n = F^(p)_n-1 + ... + F^(p)_n-2 + ... + F^(p)_n-p , với n>=p

Và F^(p)_n = 0, với 0 <= n <= p-2; F^(p)_p-1 = 1

Dãy Fibonacci thông thường là dãy Fibonacci bậc 1.

Thông thường nếu chúng ta lấy p= T-1, phân bố trộn đa pha đối với P tập tin sẽ tương ứng với số Fibonacci bậc P.

Sưu tầm