Flash sort - công cụ mới để tối ưu tốc độ giải thuật

[StarGhost]

(Bài viết tham khảo từ bài viết trong Dr. Dobb’s Journal về Flash Sort vào tháng 2 1998)
Thấy mọi người có vẻ ít quan tâm đến các thuật toán sắp xếp, tôi mạn phép nói một chút về cái này - một trong những công cụ hay trong lập trình thuật toán. (Nếu bài toán này đã xuất hiện đâu đó trên ddth thì các mod cứ việc del, tui thì không hay dò tìm xét hỏi trong này lắm)

Như các bạn đã biết, cho đến ngày nay, để giải một bài toán phức tạp, trong hầu hết các trường hợp, người ta chia bài toán đó ra làm các bài toán nhỏ hơn đã được giải bằng các thuật toán cho trước, chỉ có một số ít là sáng tác (đúng hơn là phát minh) một thuật toán mới cho bài toán đó và bài toán đó sẽ trở thành bài toán cơ bản. Phương pháp thứ hai thì hơi khó, thường dành cho các nhà nghiên cứu nhiều hơn.

Còn về phương pháp thứ nhất, tôi xin nói đến một trong những vấn đề cơ bản nhất mà các bài toán về quản lý dữ liệu đòi hỏi, đó là sắp xếp dữ liệu. Như nhiều (thậm chí hầu hết) các bạn đã biết, phổ biến trên thế giới hiện nay là một số các thuật toán điển hình như Bubble sort, Insertion Sort, Shell Sort với độ phức tạp O(n2), hay nhanh hơn và cũng khó hơn là Quick Sort, Heap Sort với độ phức tạp O(n ln(n)). Có lẽ tôi cũng không cần phải nói nhiều về ý tưởng của các thuật toán này vì các bạn đã biết quá rõ rồi.

Bây giờ tôi xin trình bày một thuật toán mới (cũng không phải mới lắm, hình như là từ năm chín mấy ấy, không nhớ nữa) với một ý tưởng hoàn toàn mới, đi ngược lại với ý tưởng chính của tất cả các thuật toán trước đó và quan trọng nhất: LÀ THUẬT TOÁN NHANH NHẤT CÓ THỂ (ĐẠT ĐẾN TỐC ĐỘ TỚI HẠN). Thuật toán này có tên là FLASH SORT, được phát minh bới 1 guy named Karl-Dietrich Neubert .

Như các bạn có thể nhận thấy dễ dàng từ các thuật toán trước, mỗi khi muốn đổi chỗ 2 phần từ bất kỳ nào đó của mảng, các bạn đều phải dùng câu lệnh IF (một số ngôn ngữ diễn tả câu lệnh khác) để so sánh giá trị của 2 phần tử đó. Chính vì vậy, tôi có thể nói là ý tưởng chính của các thuật toán trước đây là dựa trên so sánh phần tử (Elements Comparison - EC). Bây giờ nói đến Flash sort, mặc dù trong thuật toán có sử dụng EC nhưng ý tưởng chính lại là phân lớp các phần tử (Subclasses Arrangement - SA).

Bây giờ tôi đi vào chi tiết hơn. Toàn bộ quá trình xử lý của thuật toán này được chia làm 3 giai đoạn (không kể giai đoạn nhập dữ liệu và in kết quả) bao gồm 2 giai đoạn phân lớp và 1 giai đoạn sắp xếp. Ta có mảng dữ liệu A[0..n]

1. Phân loại các phần tử (Elements Classification):

Như đã nói, ý tưởng chính là phân lớp, vì thế đây là giai đoạn chuẩn bị cho việc phân lớp (giống như procedure Ready trong cái form bài giải của mấy người thi đội tuyển tin học ấy, ^_^). Các yếu tố cần thiết để ready là:
- Số phân lớp m
- Một mảng m ghi vị trí của bắt đầu của mỗi phân lớp

Vấn đề 1: Xác định giá trị phần tử nhỏ nhất (minval) và vị trí phần tử lớn nhất (nmax) -> duyệt O(n)
Vấn đề 2: Để xác định xem phần tử nào thuộc phân lớp nào, ta dùng công thức sau:
K[i]=1+Floor[ (m-1)(A[i]-minval)(A[nmax]-minval) ]

Từ công thức trên, K[i] sẽ cho biết phân lớp chứa phần tử I của mảng A. Nhìn kỹ một chút, các bạn sẽ thấy là giá trị của K sẽ nằm trong khoảng [1,m]. Các bạn nhớ dùng hàm Floor chứ đừng dùng hàm Round, vì giá trị có thể sẽ bị sai lệch, Floor luôn cho giá trị nguyên gần nhất thấp hơn giá trị thực (trong Pascal bạn có thể dùng div).

Vấn đề 3: Ta lập một mảng L ghi vị trí xuất phát của các phân lớp trong mảng A. Ta tưởng tượng (imagine) một qui tắc rằng: một phân lớp I được coi là đã đầy khi mà L[I] nằm đúng ở vị trí xuất phát của phân lớp đó trong mảng A. Chính vì vậy ta coi như một phân lớp là rỗng khi nó nằm ở vị trí cuối của vị trí chính xác của nó trong phân lớp A, để mỗi khi ta bỏ một phần tử vào phân lớp đó, ta lùi L[I] lại 1 cho đến khi về đến đúng vị trí của nó thì nghĩa là đầy. Vậy để xác định được vị trí xuất phát cũng như vị trí kết thúc của từng phân lớp, ta phải biết được kích thước của từng phân lớp. Sau đó, để coi như các phân lớp là rỗng, vị trí bắt đầu của mỗi phân lớp phải nằm ở vị trí lẽ ra là kết thúc của nó trong mảng A. Vậy ta có công thức sau:

L[I]=L[I-1]+ kích thước của lớp I

Từ trên ta suy ra, vị trí ban đầu của phân lớp 1 sẽ là kích thước của nó, còn của phân lớp m sẽ là n (số phần tử).

2. Hoán vị các phần tử (Elements Permutation):

Sau khi đã sẵn sàng, chúng ta bắt đầu việc sắp xếp các phần tử vào đúng phân lớp của nó. Việc này sẽ hình thành các chu trình hoán vị: mỗi khi ta đem một phẩn tử ở đâu đó đến một vị trí nào đó thì ta phải nhấc phần tử hiện tại đang chiếm chỗ ra, và tiếp tục với phần tử bị nhấc ra và đưa đến chỗ khác cho đến khi quay lại vị trí ban đầu thì hoàn tất vòng lặp.

Vấn đề 1: Vậy làm thế nào để khi cầm trong tay 1 phần tử nào đó, ta biết phải bỏ nó vào chỗ nào cho phù hợp? Câu trả lời thật đơn giản, ta tính xem nó phải nằm ở phân lớp nào, rồi bỏ nó vào cái vị trí hiện tại của phân lớp đó, và vì ta bỏ vào phân lớp đó 1 phần tử nên phải lùi vị trí của phân lớp lại 1 đơn vị.

Vấn đề 2: Mặc dù ta đã đi qua 1 chu trình nhưng vẫn còn những phần tử chưa ở đúng chỗ thì phải làm thế nào? Cũng đơn giản, tiến hành 1 chu trình khác cho đến khi không còn con thỏ nào trong chuồng bò và ngược lại nữa thì thôi.

Vấn đề 3: Vậy là ta có một số các chu trình cần phải xử lý, vậy tại mỗi chu trình ta phải bắt đầu từ phần tử nào của mảng (Cycle leaders searching)? Đây cũng là một trong những điều đơn giản: ta chỉ việc duyệt từ đầu đến cuối mảng và tìm xem phần tử nào không nằm trong phân lớp (I<L[K[I]]), và bắt đầu bằng phần tử đó.


3. Sắp xếp các phần tử trong từng phân lớp theo đúng thứ tự (Elements Ordering)

Phù, đến đây thì mọi việc dường như trở nên quá đơn giản rồi, hai giai đoạn trên đã giúp chúng ta chia nhỏ 1 mảng to thành nhiều mảng nhỏ để việc sắp xếp trở nên nhanh hơn.

Vấn đề duy nhất: Chọn thuật toán nào để sắp xếp các phân lớp? Câu trả lời cho vấn đề này tương đối khó, nhưng nếu các bạn tính toán 1 chút, các bạn sẽ thấy rằng Straight-Insertion Sort là lựa chọn tối ưu vì chỉ có nó mới thực sự chia nhỏ mảng A ra các phân lớp và sắp xếp từng phân lớp.


4. Cài đặt (Installation)

Như vậy, tôi đã trình bày xong toàn bộ quá trình xử lý của thuật toán FLASH SORT. Dưới đây là cách cài đặt chương trình bằng PASCAL (nếu các bạn có Free Pascal thì càng tốt vì có thể thử nghiệm với mảng lớn):

Const
N=;
M=;
Var
L: array[1..m] of Integer;
A: array[1..n] of Integer;
Minval, nmax, nho, ban_dau: integer;
Program Flash_sort;

Procedure Ready;
Var i: integer;
Begin
For i:=1 to n do
A[i]:=Random(n*2);
End;

Procedure Classification;
Var
hang_so: integer;
i: integer;
Begin
Nmax:=1;
Minval:=A[1];
For i:=1 to n do
Begin
If (A[i]>A[nmax]) then nmax:=I;
If (Minval<A[i]) then Minval:=A[i];
End;
Hang_so:= (m-1)/(A[nmax]-Minval);
For i:=1 to n do
Inc(L[1+Trunc((A[i]-Minval )*Hang_so)]);
For i:=2 to m do
L[i]:=L[i-1]+L[i];
Nho:=A[nmax];
A[nmax]:=A[1];
A[1]:=nho;

End;

Procedure Permutation;
Var
Dem, I, k: integer;
Begin
Dem:=0;
I:=1;
K:=m;
While (dem<(n-1)) do
Begin
While (i>L[k]) do
Begin
Inc(i);
K:=1+Trunc((A[i]-minval)*hang_so);
End;
Bandau:=A[i];
While (i<>L[k]+1) do
Begin
K:=1+Trunc((bandau-minval)*hang_so);
Nho=A[L[k]];
A[L[k]]:=bandau;
Bandau:=nho;
Dec(L[k]);
Inc(dem);
End;
End;

Procedure Straight_Insertion_Sort;
Var
I,j: integer;
Begin
For i:=n-2 downto 1 do
If (A[i+1]<A[i]) then
Begin
Nho:=A[i];
J:=I;
While (A[j+1]<nho)
Begin
A[j]:=A[j+1];
Inc(j);
End;
A[j]:=nho;
End;
End;

Begin
Ready;

Classification;

Permutation;

Straight_Insertion_Sort;
End.

Chương trình trên sở dĩ tôi viết bằng PASCAL là vì tôi cho rằng đây là ngôn ngữ phổ biến nhất dùng trong việc học lập trình thuật toán, sẽ dễ dàng hơn cho việc đọc, hiểu (vì sử dụng modules) và translate ra các ngôn ngữ khác. Tuy nhiên vì máy tôi không có PASCAL nên mới chỉ là Primary version, chưa test được, nếu bạn nào dùng mà thấy lỗi thì cố gắng sửa hoặc không thì post lỗi lên rồi tôi sửa cũng được.


5. Thời gian chạy (Running time complexity)

Nhìn lại toàn bộ các giai đoạn của thuật toán, ta thấy như sau:
- Giai đoạn Classification đòi hỏi độ phức tạp O(n) và O(m)
- Giai đoạn Permutation đòi hỏi độ phức tạp O(n) ( vì mỗi phần tử chỉ phải đổi chỗ đúng một lần, và n lần cho n phần tử)
- Giai đoạn Straight_Insertion_Sort đỏi hỏi độ phức tạp O(n2/m) ( mỗi 1 phân lớp đòi hỏi độ phức tạp O((n/m)2) và m phân lớp đòi hỏi O(m*(n/m)2) )

Vấn đề ở đây là làm sao chọn số phân lớp để cho thời gian tối ưu. Ta có công thức tính độ phức tạp tổng cộng cho toàn bộ quá trình là :

F(m)= a1*n+a2*m+a3*n2/m.

F’(m)=a2-a3(n/m)2=0 => m=n*(a3/a2)1/2.

Theo một số khảo sát dưạ trên nghiên cứu về tốc độ chạy của chương trình (của một số nhà nghiên cứu), a2 xấp xỉ 2 và a3 xấp xỉ 3/8, như vậy ta có m xấp xỉ 0.43n là số phân lớp tối ưu đề cho thời gian chạy nhanh nhất. Tuy nhiên đây chỉ là con số dựa trên lý thuyết, còn trên thực tế thời gian thực để chạy chương trình còn phụ thuộc vào tốc độ hiện tại của máy tính (lúc nhanh lúc chậm, ì à ì ạch).

Còn một điều nữa, thuật toán này cài đặt trên các ngôn ngữ khác nhau sẽ cho thời gian chạy khác nhau vì còn tuỳ vào tốc độ của trình biên dịch (nếu bạn viết được trên ngôn ngữ máy thì nhanh nhất). Nói chung, cái chương trình sắp xếp mà tôi thấy nhanh nhất bây giờ là Mathematica, sắp xếp 1 mảng 1 triệu phần tử trong vòng 1.25s (không biết dùng thuật toán gì nữa???).

End. Have fun.

SG.

[Vinhie47]

Thế có nhanh hơn thuật Heap sort không hả bác.

[StarGhost]

Thế có nhanh hơn thuật Heap sort không hả bác.

He he, bạn làm ơn đọc kỹ bài của tôi trước khi hỏi nhé. Trong bài tôi có nói là độ phức tạp của Quick Sort và Heap Sort là O (n Ln(n)) (trong nhiều trường hợp thì Heap Sort chạy ổn định hơn là Quick Sort). Còn Flash Sort có độ phức tạp là O(n). Bây giờ thì cái nào nhanh hơn chắc bạn biết rồi chứ?

SG.

[bete]

Thân gửi StarGhost: chỉ mới đọc lướt qua cái thuật toán chưa hiểu rõ lắm nhưng O(n) thì thiệt là đáng nể !!!!

Xin cám ơn bạn đã đăng 1 bài bổ ích như vậy !!!

-thân

[bichduyen_nt]

Không hiểu từ cái chỗ xài hàm Floor, đó là cái hàm gì vậy ?

[mapleleaf]

Tôi chưa hiểu rõ lắm về algorithm đó nhưng có cảm giác nó hơi giống Counting Sort. Runtime của counting sort cũng là 0(n).

Trong số các algorithm có O(n) cần phải kể đến Radix sort. Như vậy radix sort cũng khá nhanh nếu chỉ xét theo 0(n).

[StarGhost]

Thân gửi StarGhost: chỉ mới đọc lướt qua cái thuật toán chưa hiểu rõ lắm nhưng O(n) thì thiệt là đáng nể !!!!

Thuật toán này công nhận là hay thật, nhưng nếu bạn hiểu nó thì sẽ thấy rằng đây là một thuật toán absolutely stable, chính vì vậy kể cả input có là dãy được Sort rồi đi chăng nữa thì thời gian chạy của thuật toán vẫn hầu như không giảm (trừ phi bạn bỏ thêm 1 số checkpoint vào, cái này có thể tốt nhưng cũng có thể làm giảm tốc độ thực của thuật toán). Nói chung, chẳng có cái gì tối ưu cả.

Không hiểu từ cái chỗ xài hàm Floor, đó là cái hàm gì vậy ?

Chà chà, lại có người không chịu đọc kỹ đã hỏi rồi. Nếu bạn đọc lui xuống dưới khoảng 2 dòng sẽ thấy giải thích của tôi về function Floor. Chú ý: tôi không nói là chính xác function này cho tất cả các ngôn ngữ, bạn phải hiểu ý nghĩa của function và tự tìm lấy hàm phù hợp trong ngôn ngữ mà bạn sử dụng.

Tôi chưa hiểu rõ lắm về algorithm đó nhưng có cảm giác nó hơi giống Counting Sort. Runtime của counting sort cũng là 0(n).

Trong số các algorithm có O(n) cần phải kể đến Radix sort. Như vậy radix sort cũng khá nhanh nếu chỉ xét theo 0(n).

Hoan hô. Kiến thức của bạn về các thuật toán O(n) khá rộng, nhưng bạn quên mất phạm vi của các thuật toán này.

1. Counting Sort chỉ dùng được cho số nguyên. Kể cả cho trường hợp số nguyên, nếu giả dụ tôi cho số 1 tỉ chẳng hạn, lập tức Counting Sort hỏng ngay vì chẳng thể nào có được 1 mảng 1 tỉ phần tử (ít nhất là với các ngôn ngữ bây giờ). Còn về ý tưởng, Flash Sort khác xa hoàn toàn với Counting Sort.

2. Radix Sort sử dụng khoá nhị phân để Sort--> cũng chỉ dùng được cho số nguyên, hơn nữa, độ phức tạp của Radix Sort không phải là O(n) mà là O(n*logBase2N ), tức là còn chậm hơn nhiều so với O(nlogn)

Nếu bạn hiểu rõ về 2 thuật toán trên, tôi recommend bạn post hướng dẫn sử dụng lên cho anh em, nếu không 1 vài hôm nữa tôi post lên cũng được.

SG.

[mapleleaf]

Giá mà tôi hiểu rõ thì tốt quá. Sắp phải thi môn algo rồi.

Counting sort nếu sử dụng số quá lớn thì đúng là die thật nhưng nó có thể được sử dụng để hỗ trợ các sorting algo khác.

Đây là algorithm tôi được dạy về Radix sort, dựa trên sách "Algorithms" của 2 tác giả R. Johnsonbaugh, M. Schaefer; Pearson. ( book website: http://condor.depaul.edu/~rjohnson/algorithm/index.html)

radix_sort( a, k ) { // k is the number of digits
for i = 0 to k-1
// key is 10^i-th digit position
counting_sort( a, 9, i )
}

 The time for counting sort is O(n + 9) = O(n).
 Thus the time is O(kn).
 If k is bounded by a constant, then the time is O (n).

Radix sort sử dụng counting sort với từng chữ số (digit). Trong code ở trên có lẽ counting sort đã được thay đổi 1 chút để lấy digit i-th của a nhưng cũng không ảnh hưởng đến runtime của radix sort.

[StarGhost]

 Thus the time is O(kn).

Đây chính là vấn đề đó bạn ạ. Nếu mảng có khoảng 1 triệu phần tử và mỗi phần tử có thể lên đến 1 tỉ, như vậy độ phức tạp của thuật toán sẽ là 10 triệu, còn như Flash Sort vẫn chỉ cần đến khoảng 4 triệu thôi. Mới lại cái này cũng chỉ dùng được cho số nguyên, chứ với số thập phân có đuôi khoảng 100 chữ số sau dấu phẩy thỉ cho bạn ngồi đợi đến tết luôn.

Anyway, tôi thấy mấy cái này cũng dễ hiểu thôi, chúc bạn thi tốt.

[Pateheo]

Có thể là mình chưa biết tốc độ của thuật toán Flash Sort nhanh cỡ nào nhưng cái mà bạn nói trong Mathematica sắp xếpa một mảng kích thước 1 tr4iệu phần tử trong 1,25 s thì chưa có gì là không hiểu được. Mình đã thử dùng Quick Sort xếp 8 triệu pt thì chỉ chạy trong 3s. Không có gì là bí hiểm cả.