Chơng 2 Sắp xếp trên bộ nhớ ngoài
2.5. Sắp xếp trên đĩa từ (Phơng pháp lựa chọn có thay thế)
Khác với băng từ, đối với đĩa từ thời gian truy nhập vào các khối khác nhau trên đĩa là không chênh lệch nhau bao nhiêu (vì vậy có khi ngời ta coi đĩa từ là phơng tiện truy nhập trực tiếp). Cho nên vấn phân bố khối không phải đặt ra.
Sắp xếp trên đĩa từ chỉ còn phải chú ý tới việc giảm bớt số lợng truy nhập khối.
Một giải pháp thích hợp để giải quyết vấn đề này đó là áp dụng kỹ thuật tạo khối mới dựa trên việc lựa chọn có thay thế. Mục đích của giải pháp này đó là tăng độ dài cho khối (hay nói một cách khác là việc phân bố các khối ban đầu).
Giả sử vùng đệm ở bộ nhớ trong cho phép sắp xếp đợc m khoá (mẫu tin) và dữ liệu đang chứa trên đĩa gốc f0. Khối sẽ đợc tạo nh sau:
Đọc m khoá từ f0 vào vùng đêm. Chọn khoá nhỏ h[1] và ghi lên đĩa f[j].
Gọi h[2] là khoá của f0 đang xét tiếp. Nếu h[2]≥ h[1] nó sẽ đợc đa vào thay thế cho h[1] và đợc coi nh thuộc khối đang tạo. Quá trình chọn khoá nhỏ lại tiếp tục và bớc tiếp theo cũng tiến hành tơng tự. Nếu h[2] < h[1], trong một lợt nào đó, nó sẽ vẫn đợc đa vào thay thế h[1] nhng bị coi nh thuộc khối sau và để lại xét sau khi các khoá thuộc khối đang tạo đã đợc xử lý xong. Chừng nào mà các khoá
thay thế bị để lại đã vào đầy vùng đệm cho phép (kích thớc m) hoặc dữ liệu vào
đã hết thì một khối mới sẽ bắt đầu đợc tạo lập.
Ví dụ 2.8: Xét dãy khoá sau với m = 7
A S O R T I N G A N D M E R G I N G E X A M P L E
Nội dung của bộ nhớ trong và các khoá đợc đa ra khối mới sẽ đợc biểu diễn trong bảng sau:
Nội dung bộ nhớ trong Khoá đa ra khối mới A S O R T I N A
G S O R T I N G (A) S O R T I N I
(A) S O R T (A) N N (A) S O R T (A) (D) O (A) S (M) R T (A) (D) R (A) S (M) R T (A) (D) R (A) S (M) (G) T (A) (D) S
(A) (I) (M) (G) T (A) (D) T HÕt khèi cò A I M G N A D A Bắt đầu khối mới G I M G N A D A
G I M G N E D D G I M G N E X E G I M G N (A) X G M I M G N (A) X G M I M P N (A) X I M L M P N (A) X L M (E) M P N (A) X M (E) M P N (A) X M (E) P N (A) X N (E) P (A) X P
(E) (A) X X HÕt khèi cò E A A Bắt đầu khối mới E E
Dấu _ chỉ khoá đợc chọn đa ra khối.
Dấu ( ) chỉ khoá bị giữ lại cho khối tiếp theo.
Với cách này rõ ràng là ta có thể tạo lập đợc các khối có độ dài thờng không phải là m, mà lớn hơn m. Nh ở vị trí trên khối đầu đã có độ dài bằng 9 > 7.
Các kết quả thực nghiệm đã cho thấy: Trung bình độ dài của khối có giá trị là 2m. Nh vậy nếu ta có N khoá thì số khối tạo thành không phải là S = [N/m] mà
thờng là S = [N/2m] nghĩa là giảm đi khoảng một nửa, điều đó sẽ góp phần làm giảm số lợt trộn, nâng cao hơn tốc độ xử lý của toàn bộ quá trình xử lý ngoài.
Để triển khai kỹ thuật này ngời ta thờng sử dụng sắp xếp trong kiểu vun
đống (Heap) với “Khoá cha” nhỏ hơn “Khoá con” nh vậy khoá nhỏ nhất đợc chọn chính là khoá nằm ở đỉnh đống. Mỗi lần khoá này đợc chọn đa ra khối mới, thì khoá thay thế đợc đa vào và đống sẽ đợc “Vun lại”. Lúc đó đống sẽ nh một
“Đờng hầm” mà các khoá đợc đa vào từ f0 nếu “Chui qua” đợc, thì khi ra sẽ trở thành khoá của khối đang đợc tạo, nếu còn đọng lại trong đó thì sẽ đợc xét khi tạo khối tiếp theo. Có thể minh hoạ qua hình sau:
A A N D
A G N D M
Gọi m là độ lớn của heap h, hằng mh để chỉ m/2; l và r là những chỉ số cho h. Phối hợp các kỹ thuật sắp xếp mảng và sắp xếp tập tin. Quá trình thực hiện trên sẽ đợc cụ thể hơn nhờ ý tởng thuật toán sau:
1. Đọc mh phần tử đầu tiên từ f0 vào nửa trên của heap, lúc này ta không cần quan tâm đến thứ tự giữa các phần tử.
2. Đọc mh phần tử khác và đặt vào nửa dới của heap, lần lợt đặt các phần tử vào đúng vị trí của nó (tạo heap).
G
N
I
T R S O
I
N O
T R S A
3. Khởi động l bằng m và lặp lại bớc sau đây đối với tất cả các phần tử còn lại trên f0: Chuyển h[1] đến tập tin xuất (đĩa f[j]) tơng ứng. Nếu nó nhỏ hơn hay bằng phần tử kế trên tập tin nhập (đĩa f0), thì phần tử kế này cũng thuộc cùng khối và có thể đợc đặt vào đúng vị trí của nó. Nếu không thì giảm độ lớn của heap và đặt phần tử mới (khoá mới) vào heap “Trên” thứ hai, đợc tạo để chứa khối kế. Chỉ số l đợc dùng để chỉ ranh giới giữa hai heap. Nh thế heap “Thấp ” nghĩa là hiện tại, chứa các phần tử h[1], ..., h[l], còn heap “Trên” hay heap kế chứa các phần tử h[l+1], ..., h[m]. Nếu l bằng 0 thì ta thay tập tin xuất và lại cho l bằng m.
4. Bây giờ tập tin nhập đã đợc xử lý xong. Đầu tiên cho r bằng m, sau đó chuyển phần thấp đi, và cùng lúc tạo phần trên và từng bớc đặt nó vào vị trí h[l+1], ..., h[r].
5. Khối cuối cùng đợc phát sinh từ các phần tử còn lại trong heap.