Cấu trúc dữ liệu và giải thuật lưu trữ ngoài
Trong các giải thuật mà chúng ta đã đề cập từ trước tới nay, chúng ta đã giả sử rằng số lượng các dữ liệu vào là khá nhỏ để có thể chứa hết ở bộ nhớ trong (main memory). Nhưng điều gì sẽ xảy ra nếu ta muốn xử lý phiếu điều tra dân số toàn ...
Trong các giải thuật mà chúng ta đã đề cập từ trước tới nay, chúng ta đã giả sử rằng số lượng các dữ liệu vào là khá nhỏ để có thể chứa hết ở bộ nhớ trong (main memory). Nhưng điều gì sẽ xảy ra nếu ta muốn xử lý phiếu điều tra dân số toàn quốc hay thông tin về quản lý đất đai cả nước chẳng hạn? Trong các bài toán như vậy, số lượng dữ liệu vượt quá khả năng lưu trữ của bộ nhớ trong. Ðể có thể giải quyết các bài toán đó chúng ta phải dùng bộ nhớ ngoài để lưu trữ và xử lý. Các thiết bị lưu trữ ngoài như băng từ, đĩa từ đều có khả năng lưu trữ lớn nhưng đặc điểm truy nhập hoàn toàn khác với bộ nhớ trong. Chúng ta cần tìm các cấu trúc dữ liệu và giải thuật thích hợp cho việc xử lý dữ liệu lưu trữ trên bộ nhớ ngoài.
Kiểu dữ liệu tập tin là kiểu thích hợp nhất cho việc biểu diễn dữ liệu được lưu trong bộ nhớ ngoài. Hệ điều hành chia bộ nhớ ngoài thành các khối (block) có kích thước bằng nhau, kích thước này thay đổi tùy thuộc vào hệ điều hành nhưng nói chung là từ 512 bytes đến 4096 bytes.
Trong quá trình xử lý, việc chuyển giao dữ liệu giữa bộ nhớ trong và bộ nhớ ngoài được tiến hành thông qua vùng nhớ đệm (buffer). Bộ đệm là một vùng dành riêng của bộ nhớ trong mà kích thước bằng với kích thước của một khối của bộ nhớ ngoài.
Có thể xem một tập tin bao gồm nhiều mẩu tin được lưu trong các khối . Mỗi khối lưu một số nguyên vẹn các mẩu tin, không có mẩu tin nào bị chia cắt để lưu trên hai khối khác nhau.
Trong thao tác đọc, nguyên một khối của tập tin được chuyển vào trong bộ đệm và lần lượt đọc các mẩu tin có trong bộ đệm cho tới khi bộ đệm rỗng thì lại chuyển một khối từ bộ nhớ ngoài vào bộ đệm.
Ðể ghi thông tin ra bộ nhớ ngoài, các mẩu tin lần lượt được xếp vào trong bộ đệm cho đến khi đầy bộ đệm thì nguyên một khối được chuyển ra bộ nhớ ngoài. Khi đó bộ đệm trở nên rỗng và lại có thể xếp tiếp các mẩu tin vào trong đó.
Mô hình giao tiếp giữa bộ nhớ trong, bộ nhớ ngoài và vùng nhớ đệm
Như vậy đơn vị giao tiếp giữa bộ nhớ trong và bộ đệm là mẩu tin còn giữa bộ đệm và bộ nhớ ngoài là khối.
Hình trên mô tả họat động của bộ nhớ trong, bộ đệm và bộ nhớ ngoài trong thao tác đọc và ghi tập tin
Ðối với bộ nhớ ngoài thì thời gian tìm một khối để đọc vào bộ nhớ trong là rất lớn so với thời gian thao tác trên dữ liệu trong khối đó. Ví dụ giả sử ta có một khối có thể lưu 1000 số nguyên được lưu trên đĩa quay với vận tốc 1000 vòng/ phút thì thời gian để đưa đầu từ vào rãnh chứa khối và quay đĩa để đưa khối đến chỗ đầu từ hết khoảng 100 mili giây. Với thời gian này máy có thể thực hiện 100000 lệnh, tức là đủ để sắp xếp các số nguyên này theo giải thuật QuickSort. Vì vậy khi đánh giá các giải thuật thao tác trên bộ nhớ ngoài, chúng ta tập trung vào việc xét số lần đọc khối vào bộ nhớ trong và số lần ghi khối ra bộ nhớ ngoài ta gọi chung là phép truy xuất khối (block access). Vì kích thước các khối là cố định nên ta không thể tìm cách tăng kích thước một khối mà chúng ta phải tìm cách giảm số lần truy xuất khối.
Sắp xếp dữ liệu được tổ chức như một tập tin hoặc tổng quát hơn, sắp xếp dữ liệu được lưu trên bộ nhớ ngoài gọi là sắp xếp ngoài.
Sắp xếp trộn (merge sorting)
Khái niệm về đường
Ðường độ dài k là một tập hợp k mẩu tin đã đựoc sắp thứ tự theo khoá tức là, nếu các mẩu tin r1,r2,...,rk có khoá lần lượt là k1,k2,...,kk tạo thành một đường thì k1≤ k2 ≤ ... ≤ kk.
Cho tập tin chứa các mẩu tin r1,r2,...,rn, ta nói tập tin được tổ chức thành đường có độ dài k nếu ta chia tập tin thành các đoạn k mẩu tin liên tiếp và mỗi đoạn là một đường, đoạn cuối có thể không có đủ k mẩu tin, trong trường hợp này ta gọi đoạn ấy là đuôi (tail).
Ví dụ 4-1: Tập tin gồm 14 mẩu tin có khóa là các số nguyên được tổ chức thành 4 đường độ dài 3 và một đuôi có độ dài 2
| 5 | 6 | 9 | 13 | 26 | 27 | 1 | 5 | 8 | 12 | 14 | 17 | 23 | 25 |
Giải thuật
Ðể sắp xếp tập tin F có n mẩu tin ta sử dụng 4 tập tin F1, F2, G1 và G2.
Khởi đầu ta phân phối các mẩu tin của tập tin đã cho F luân phiên vào trong hai tập tin F1 F2. Như vậy hai tập tin này được xem như được tổ chức thành các đường độ dài 1.
Bước 1: Ðọc 2 đường, mỗi đường độ dài 1 từ hai tập tin F1, F2 và trộn hai đường này thành đường độ dài 2 và ghi luân phiên vào trong hai tập tin G1, G2. Ðổi vai trò của F1 cho G1, F2 cho G2.
Bước 2: Ðọc 2 đường, mỗi đường độ dài 2 từ hai tập tin F1, F2 và trộn hai đường này thành đường độ dài 4 và ghi luân phiên vào trong hai tập tin G1, G2. Ðổi vai trò của F1 cho G1, F2 cho G2.
Quá trình trên cứ tiếp tục và sau i bước thì độ dài của một đường là 2I. Nếu 2I ( n thì giải thuật kết thúc, lúc đó tập tin G2 sẽ rỗng và tập tin G1 chứa các mẩu tin đã được sắp.
Ðánh giá giải thuật sắp xếp trộn
Ta thấy giải thuật kết thúc sau i bước với i ≥ logn. Mỗi bước phải đọc từ 2 tập tin và ghi vào 2 tập tin, mỗi tập tin có trung bình n/2 mẩu tin. Giả sử mỗi một khối lưu trữ được b mẩu tin thì mỗi bước cần đọc và ghi 2*2*n2*b=2nb size 12{ { {"2*2*n"} over {"2*b"} } = { {"2n"} over {b} } } {} khối mà chúng ta cần logn bước vậy tổng cộng chúng ta cần 2nblogn size 12{ { {"2n"} over {b} } "logn"} {} phép truy xuất khối.
Ví dụ 4-2: Cho tập tin F có 23 mẩu tin với khóa là các số nguyên như sau:
2 31 13 5 98 96 10 40 54 85 65 9 30 39 90 13 10 8 69 77 8 10 22.
Ðể bắt đầu ta phân phối các mẩu tin của F luân phiên vào hai tập tin F1 và F2 được tổ chức thành các đường có độ dài 1
| 2 | 13 | 98 | 10 | 54 | 65 | 30 | 90 | 10 | 69 | 8 | 22 | F1 |
| 31 | 5 | 96 | 40 | 85 | 9 | 39 | 13 | 8 | 77 | 10 | F2 |
Bước 1: Trộn các đường độ dài 1 của F1 và F2 được các đường độ dài 2 và ghi luân phiên vào trong hai tập tin G1, G2:
| G1 | 2 | 31 | 96 | 98 | 54 | 85 | 30 | 39 | 8 | 10 | 8 | 10 | F1 |
| G2 | 5 | 13 | 10 | 40 | 9 | 65 | 13 | 90 | 69 | 77 | 22 | F2 |
Bước 2: Ðổi vai trò của F1 và G1, F2 và G2 cho nhau. Trộn các đường độ dài 2 trong hai tập tin F1 và F2 được các đường độ dài 4 rồi ghi luân phiên vào trong hai tập tin G1 và G2:
| G1 | 2 | 5 | 13 | 31 | 9 | 54 | 65 | 85 | 8 | 10 | 69 | 77 | F1 |
| G2 | 10 | 40 | 96 | 98 | 13 | 30 | 39 | 90 | 8 | 10 | 22 | F2 |
Bước 3: Ðổi vai trò của F1 và G1, F2 và G2 cho nhau. Trộn các đường độ dài 4 trong hai tập tin F1 và F2 được các đường độ dài 8 rồi ghi luân phiên vào trong hai tập tin G1 và G2:
| G1 | 2 | 5 | 10 | 13 | 31 | 40 | 96 | 98 | 8 | 8 | 10 | 10 | 22 | 69 | 77 | F1 |
| G2 | 9 | 13 | 30 | 39 | 54 | 65 | 85 | 90 | F2 |
Bước 4: Ðổi vai trò của F1 và G1, F2 và G2 cho nhau. Trộn các đường độ dài 8 trong hai tập tin F1 và F2 được các đường độ dài 16 rồi ghi luân phiên vào trong 2 tập tin G1 và G2.
| G1 | 2 | 5 | 9 | 10 | 13 | 13 | 30 | 31 | 39 | 40 | 54 | 65 | 85 | 90 | 96 | 98 | F1 |
| G2 | 8 | 8 | 10 | 10 | 22 | 69 | 77 | F2 |
Bước 5: Ðổi vai trò của F1 và G1, F2 và G2 cho nhau. Trộn các đường độ dài 16 trong hai tập tin F1 và F2 được 1 đường độ dài 23 rồi ghi vào trong tập tin G1.
| G1 | 2 | 5 | 8 | 8 | 9 | 10 | 10 | 10 | 13 | 13 | 22 | 30 | 31 | 39 | 40 | 54 | 65 | 69 | 77 | 85 | 90 | 96 | 98 |
Tập tin G1 chứa các mẩu tin đã được sắp còn tập tin G2 rỗng.
Chương trình
procedure Merge(k:integer; f1,f2,g1,g2: File of RecordType);
{Thủ tục này trộn các đường độ dài k và trong hai tập tin f1 và f2 thành các đường đọ dài 2k và ghi luân phiên vào trong hai tập tin g1 và g2}
var
OutSwithh : boolean; {Nếu OutSwitch = TRUE thì ghi vào tập tin g1, ngược lại ghi vào g2}
Winner: integer; {Ðể chỉ định mẩu tin hiện hành nào trong hai tập tin f1 và f2 sẽ được ghi ra tập tin g1 hoặc g2}
Used: array[1..2] of integer; { Used[ij] ghi số mẩu tin đã được đọc trong đường hiện tại của tập tin fj }
Fin : array[1..2] Of boolean; {Fin[j] sẽ có giá trị TRUE nếu đã đọc hết các mẩu tin trong đường hiện hành của fj họac đx dến cuối tập tin fj }
Current: array[1..2] Of RecordType; { Current[j] để lưu mẩu tin hiện hành của tập tin f[j]}
procedure GetRecord(i:integer);
{Nếu đã đọc hết các mẩu tin trong đường hiện hành của tập tin fi hoặc đã đến cuối tập tin fi thì đặt fin[i] = TRUE nếu không thì đọc một mẩu tin của tập tin fi vào trong current[i]}
begin
Used[i] := Used[i] + 1;
if (Used[i] = k+1 ) or (i = 1) and ( eof(f1)) or (i = 2 and ( eof(f2)) then fin[i] := TRUE
else if i=1 then Read(f1, current[1])
else read(f2, current[2]);
end;
begin
{ Khởi tạo }
OutSwitch := TRUE;
ReSet(f1);
ReSet(f2);
ReWrite(g1);
ReWrite(g2);
while (not eof(f1)) or (not eof(f2)) do begin
{Bắt đầu đọc các mẩu tin từ trong hai đường hiện hành của hai tập tin f1,f2 }
Used[1] := 0; Used[2] := 0;
Fin[1] := FALSE ; Fin[2] := FALSE ;
GetRecord(1) ; GetRecord(2);
while ( not fin[1] ) or (not fin[2]) do begin
{Trộn hai đường }
{ Chọn Winner }
if Fin[1] then Winner := 2
else if Fin[2] then Winner := 1
else if current[1].key < Current[2].key then
Winner := 1
else Winner := 2;
if OutSwitch then Write(g1, Current[winner] )
else Write(g2, current[winner] );
GetRecord(Winner);
end;
OutSwitch := Not OutSwitch;
end;
end;
Cải tiến sắp xếp trộn
Ta thấy quá trình sắp xếp trộn nói trên bắt đầu từ các đường độ dài 1 cho nên phải sau logn bước giải thuật mới kết thúc. Chúng ta có thể tiết kiệm thời gian bằng cách chọn một số k thích hợp sao cho k mẩu tin có thể đủ chứa trong bộ nhớ trong. Mỗi lần đọc vào bộ nhớ trong k mẩu tin, dùng sắp xếp trong (chẳng hạn dùng QuickSort) để sắp xếp k mẩu tin này và ghi luân phiên vào hai tập tin F1 và F2. Như vậy chúng ta bắt đầu sắp xếp trộn với các tập tin được tổ chức thành các đường độ dài k.
Sau i bước thì độ dài mỗi đường là k.2i. Giải thuật sẽ kết thúc khi k2i ≥ n hay i ≥ lognk size 12{ { {n} over {k} } } {}. Do đó số phép truy xuất khối sẽ là 2nblognk size 12{ { {"2n"} over {b} } "log" { {n} over {k} } } {}. Dễ thấy 2nblognk size 12{ { {"2n"} over {b} } "log" { {n} over {k} } } {} < 2nblogn size 12{ { {"2n"} over {b} } "logn"} {} tức là ta tăng được tốc độ sắp xếp trộn.
Ví dụ 4-3: Lấy tập tin F có 23 mẩu tin với khóa là các số nguyên như trong ví dụ 4-2:
2 31 13 5 98 96 10 40 54 85 65 9 30 39 90 13 10 8 69 77 8 10 22.
Ta giả sử bộ nhớ trong có thể chứa được 3 mẩu tin, ta đọc lần lượt 3 mẩu tin của F vào bộ nhớ trong , dùng một sắp xếp trong để sắp xếp chúng và ghi phiên vào 2 tập tin F1 và F2.
| 2 13 31 | 10 40 54 | 30 39 90 | 8 69 77 | F1 |
| 5 96 98 | 9 65 85 | 8 10 13 | 10 22 | F2 |
Bước 1:Trộn các đường độ dài 3 của F1 và F2 được các đường độ dài 6 và ghi luân phiên vào trong hai tập tin G1, G2:
| G1 | 2 5 13 31 96 98 | 8 10 13 30 39 90 | F1 |
| G2 | 9 10 40 54 65 85 | 8 10 22 69 77 | F2 |
Bước 2: Ðổi vai trò của F1 và G1, F2 và G2 cho nhau. Trộn các đường độ dài 6 trong 2 tập tin F1 và F2 được các đường độ dài 12 rồi ghi luân phiên vào trong 2 tập tin G1 và G2:
| G1 | 2 5 9 10 13 31 40 54 65 85 96 98 | F1 |
| G2 | 8 8 10 10 13 22 30 39 69 77 90 | F2 |
Bước 3: Ðổi vai trò của F1 và G1, F2 và G2 cho nhau. Trộn các đường độ dài 12 trong 2 tập tin F1 và F2 được 1 đường ghi vào trong tập tin G1, còn G2 rỗng
| G1 | 2 5 8 8 9 10 10 10 13 13 22 30 31 39 40 54 65 77 85 90 96 98 |
Tập tin G1 chứa các mẩu tin đã được sắp còn tập tin G2 rỗng.
Trộn nhiều đường (multiway merge)
Giải thuật
Ðể sắp xếp tập tin F có n mẩu tin ta sử dụng m tập tin (m là một số chẵn) F[1], F[2],... , F[m]. Trong trường hợp m=4 ta có giải thuật sắp xếp trộn bình thường.
Gọi h = m/2, ta có nội dung của phương pháp như sau (ta vẫn giả sử bộ nhớ trong có thể chứa k mẩu tin).
Khởi đầu: Mỗi lần đọc từ tập tin F vào bộ nhớ trong k mẩu tin, sử dụng một sắp xếp trong để sắp xếp k mẩu tin này thành một đường rồi ghi luân phiên vào các tập tin F[1], F[2], ... , F[h].
Bước 1: Trộn các đường độ dài k của h tập tin F[1], F[2], ..., F[h] thành một đường độ dài k.h và ghi luân phiên vào trong h tập tin F[h+1], F[h+2], ... , F[m]. Ðổi vai trò của F[i] và F[h+i]] cho nhau (với 1≤ i ≤ h).
Bước 2: Trộn các đường độ dài kh của h tập tin F[1], F[2], ..., F[h] thành một đường độ dài k.h2 và ghi luân phiên vào trong h tập tin F[h+1], F[h+2], ... , F[m]. Ðổi vai trò của F[i] và F[h+i]] cho nhau (với 1 ≤ i ≤ h).
Sau i bước thì độ dài mỗi đường là k.hi và giải thuật kết thúc khi k.hi ≥ n và khi đó tập tin đã được sắp chính là một đường ghi trong F[h+1].
Ðánh giá giải thuật sắp xếp trộn nhiều đường
Theo trên thì giải thuật kết thúc sau i bước, với khi ≥ n hay i ≥ loghnk size 12{ { {n} over {k} } } {}. Mỗi bước ta phải đọc từ h tập tin và ghi vào trong h tập tin, trung bình mỗi tập tin có nh size 12{ { {n} over {h} } } {} mẩu tin. Ta vẫn giả sử mỗi khối lưu được b mẩu tin thì mỗi bước phải truy xuất 2*h*nh*b=2nb size 12{ { {"2*h*n"} over {"h*b"} } = { {"2n"} over {b} } } {} khối. Do chúng ta cần loghnk size 12{ { {n} over {k} } } {} bước nên tổng cộng ta chỉ cần 2nbloghnk size 12{ { {"2n"} over {b} } "log" rSub { size 8{h} } rSup { size 8{ { {n} over {k} } } } } {} phép truy xuất khối.Ta thấy rõ ràng 2nbloghnk size 12{ { {"2n"} over {b} } "log" rSub { size 8{h} } rSup { size 8{ { {n} over {k} } } } } {} < 2nblognk size 12{ { {"2n"} over {b} } "log" { {n} over {k} } } {} và thủ tục mergeSort nói trên là một trường hợp đặc biêt khi h = 2.
Ví dụ 4-4: Lấy tập tin F có 23 mẩu tin với khóa là các số nguyên như trong ví dụ 4-2
2 31 13 5 98 96 10 40 54 85 65 9 30 39 90 13 10 8 69 77 8 10 22.
Sử dụng 6 tập tin để sắp xếp tập tin F. Ta giả sử bộ nhớ trong có thể chứa được 3 mẩu tin, ta đọc lần lượt 3 mẩu tin của F vào bộ nhớ trong , dùng một sắp xếp trong để sắp xếp chúng và ghi phiên vào 3 tập tin F[1], F[2] và F[3] như sau:
| F[1] | 2 | 13 | 31 | 9 | 65 | 85 | 8 | 69 | 77 |
| F[2] | 5 | 96 | 98 | 30 | 39 | 90 | 10 | 22 |
| F[3] | 10 | 40 | 54 | 8 | 10 | 13 |
Bước 1: Trộn các đường độü dài 3 trong các tập tin F[1], F[2], F[3] thành các đường độ dài 9 và ghi vào trong các tập tin F[4], F[5] và F[6].
| F[4] | 2 | 5 | 10 | 13 | 31 | 40 | 54 | 96 | 98 | F[1] |
| F[5] | 8 | 9 | 10 | 13 | 30 | 39 | 65 | 85 | 90 | F[2] |
| F[6] | 8 | 10 | 22 | 69 | 77 | F[3] |
Bước 2: Ðổi vai trò của F[1] cho F[4], F[2] cho F[5] và F[3] cho F[6]. Trộn các đường độ dài 9 trong các tập tin F[1], F[2], F[3] thành 1 đường độ dài 23 và ghi vào trong tập tin F[4].
| F[4] | 2 5 8 8 9 10 10 10 13 13 22 30 31 39 40 54 65 69 77 85 90 96 98 |
Tập tin F[4] chứa các mẩu tin đã được sắp còn F[5] và F[6] rỗng.
