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ả.

[StarGhost]

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ả.

Bạn viết bằng ngôn ngữ gì vậy? Có thể post code lên cho tôi coi 1 chút được không? Thanks

SG.

[doc_hanh_dai_dao]

ngôn ngữ 512MB RAM, P4 Extreme Edition, Cache L1 64KB, L2 4MB, HDD 120GB ATA200...

[StarGhost]

ngôn ngữ 512MB RAM, P4 Extreme Edition, Cache L1 64KB, L2 4MB, HDD 120GB ATA200...

He he. Tưởng gì, ngôn ngữ đó thì có gì là nhanh đâu, bên này ngôn ngữ của nó toàn 2 GB Ram, P4 3.06 thôi. Cái quan trọng là chạy Quicksort 8 triệu phần tử mà trong 3s thì quả thật, trên quan điểm của tôi là brilliant, chỉ có nước dùng computer language.

Nếu quả thật bạn làm được như vậy thì rất giỏi đấy. Cứ viết 1 cái mail cho bọn Volfram Research bảo với chúng nó rằng function Sort của tôi nhanh gấp nhiều lần của quí vị, đề nghị được tối ưu hoá Mathematica, có khi được tí money đấy. Tuy nhiên tôi dám cược rằng nếu áp dụng với Flash Sort thì: nếu Quick Sort cần 3s để Sort 8 triệu phần tử thì Flash Sort cần không đến 1 s đâu. Hãy thử install đi, rồi bạn sẽ thấy.

[bete]

StarGhost cho tui thắc mắc 1 chút:

K[i]=1+Floor[ (m-1)(A[i]-minval)(A[nmax]-minval) ]

=> FlashSort chỉ áp dụng cho kiểu số. Muốn áp dụng cho kiểu khác (kiểu string chẳng hạn) thì phải định nghĩa hàm "khoảng cách" (để phép '-' có nghĩa) !?!?!?

-thân

[StarGhost]

To bete: Đây thực ra chỉ là bước thực hiện việc phân lớp, mà bạn muốn sort ký tự trong string hay set of strings. Mà dù thế nào, bạn thử nghĩ xem, thế làm sao bạn biết là ký tự B thì lớn hơn ký tự A, đơn giản là vì A thì có số thứ tự ASCII là 65 còn B là 66, mà 66>65 => B>A. Đó, kiểu gì chả phải chuyển về kiểu số --> Giang sơn qui về một mối mà bạn.

Anyway, very good question. Thanks.

SG.

[bete]

StarGhost cho tui thắc mắc thêm 1 chút:

(quoted): "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."

1) quoted: "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."

=> Straight-Insertion Sort có 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" ư !?!? Tui nhìn vô phần cài đặt Straight-Insertion Sort mà không thấy nó chia nhỏ mảng A thành các phân lớp chỗ nào !?

2) Giả sử Straight-Insertion Sort có 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 thì tui vẫn thắc mắc là như vậy thì có lợi điểm gì !? Mảng A đã được phân hoạch thành các lớp con ngay từ bước trước đó rồi => mình đâu có cần chia nhỏ ra các phân lớp nữa làm gì, mà chỉ cần sắp xếp các phân lớp thôi

Tui nghĩ sỡ dĩ Straight-Insertion Sort được chọn là vì nó đơn giản và đủ hiệu quả. Vì cách lựa chọn m ở đây là rất khéo: m=O(n) (vì n=kn) => kích thước trung bình của các phân lớp là k => chọn k đủ nhỏ thì Straight-Insertion Sort là đủ sức sắp xếp các phân lớp rồi

Tui thấy ý tưởng của Flash-Sort tương tự như Quick-Sort: chia để trị. Điểm khác nhau là: Quick-Sort chia mảng làm 2 phần con, còn Flash-Sort chia mảng làm O(n) phần con (nhờ vậy mới đẩy được độ phức tạp xuống O(n), chứ nếu chia làm O(1) phần con thì độ phức tạp sẽ là O(n^2)).

3) Điểm thắc mắc cuối cùng của tui là sắp xếp kiểu dữ liệu chuỗi. Cho 2 chuỗi ký tự s1 và s2. Với các giải thuật sắp xếp thông thường khác thì mình chỉ gặp vấn đề "định tính": s1 có nhỏ hơn hơn s2 => xài mã ASCII là được rồi. Nhưng với Flash-Sort thì mình lại gặp vấn đề "định lượng": nếu s1 nhỏ/lớn hơn s2 thì nhỏ/lớn hơn bao nhiêu ? Trở lại công thức:
K[i]=1+Floor[ (m-1)(A[i]-minval)(A[nmax]-minval) ]
=> nếu hướng giải quyết là đổi A[i] (và A[nmax]) thành 1 giá trị số tương ứng thì tui thấy có 1 chỗ khúc mắc: theo thứ tự từ điển thì "2" lớn hơn "1111.....111" vậy thì "2" sẽ có giá trị số tương ứng là dương vô cùng hay sao (vì chuỗi "1111.....111" có thể dài bao nhiêu cũng được) !? Nếu vậy thì "3" có giá trị số tương ứng là bao nhiêu (lưu ý là "3" lớn hơn "2")
Nếu được thì StarGhost có thể thử sửa chương trình của bạn để sắp xếp các chuỗi ký tự không !?!?

Tui thấy Flash-Sort có 1 lợi điểm là nhờ chia làm nhiều phân lớp con => rất đẹp để tính toán song song.

(có gì sai sót xin các bạn chỉ giúp cho, cám ơn rất nhiều)

-thân

[StarGhost]

Cảm ơn bạn bete đã nhắc đến string, nhờ thế tôi tìm ra 1 nhược điểm của Flash Sort.

Cũng như hầu hết các thuật toán, hiệu suất của một thuật toán chỉ đạt đến mức tối đa khi input được cho hoàn toàn ngẫu nhiên. Ngược lại, mỗi một thuật toán đều có các nhược điểm riêng của nó mà có thể khiến cho thuật toán chạy với tốc độ cực kỳ chậm hay thậm chí là cho ra kết quả sai với thực tế. Và Flash Sort cũng không phải là ngoại lệ, sau đây là 1 testing input có thể làm cho Flash Sort có tốc độ n^2:
List{ Random[0->1] (10000 số), 100000}

Đây cũng là một trong những vấn đề về cái chuỗi có độ dài vô cùng của bete. Về vấn đề này, đáng buồn là nếu có chuỗi 1111....111 trong set thì 2 sẽ có giá trị vô cùng thật. Nếu đổi chuỗi ra số thì tức là phải đổi từ base 256 ra base 10, số vô cùng lớn. Thông cảm nhé, tui đang bận thi, chưa nghĩ ra được 1 phương pháp nào hay để định nghĩa cái này. Chắc phải nhờ đến anh em thôi. Vài hôm nữa mới rảnh để nghĩ tiếp.

SG.

[bete]

Thân gửi StarGhost:

1) quoted: "Sau đây là 1 testing input có thể làm cho Flash Sort có tốc độ n^2:
List{ Random[0->1] (10000 số), 100000}"

=> tui đồng ý với bạn: Flash-Sort có 1 nhược điểm tương tự như Quick-Sort: nếu số phân lớp suy biến về O(1) (khi dữ liệu không phân tán ngẫu nhiên mà bị "tập trung" (skewed)) thì độ phức tạp trở thành O(n^2)

2) quoted: "nếu có chuỗi 1111....111 trong set thì 2 sẽ có giá trị vô cùng thật. Nếu đổi chuỗi ra số thì tức là phải đổi từ base 256 ra base 10, số vô cùng lớn"

=> tui đồng ý với bạn. Vừa mới thấy có 1 cách giải quyết: đừng đổi về số nguyên mà đổi về số thực (cơ số 256): giả sử mình làm ở hệ 10 cho dễ thấy: "2" trở thành 0.2, "1111...111" trở thành 0.1111....111. Tuy nhiên do hạn chế từ độ chính xác của dấu phẩy động: nếu chuỗi đủ dài thì "1111...111" có thể bằng "2"; nhưng điều này có thể không gây trở ngại gì vì mình đang chỉ cần chia phân lớp ("2" và "1111....111" sẽ vô cùng 1 phân lớp). Một cách giải quyết khác là chỉ cần dùng mã ASCII của ký tự đầu làm giá trị số tương ứng: "1" hay "12" hay "1111.....111" đều có giá trị là 1, "2" hay "21" hay "29999.........99999" đều có giá trị là 2 => vẫn chia được thành các phân lớp. Tuy nhiên nếu ký tự đầu của dữ liệu không phân tán ngẫu nhiên (ví dụ hầu hết các chuỗi đều bắt đầu bằng cùng 1 ký tự) thì số phân lớp sẽ suy biến về O(1) => độ phức tạp trở thành O(n^2). Mình có thể thử: nếu k ký tự đầu không phân tán đủ ngẫu nhiên thì bỏ qua (khi tính toán giá trị số tương ứng)

Tui thấy một điều khó chịu khác khi sắp xếp dữ liệu kiểu chuỗi ký tự là mình phải liên tục đổi các chuỗi ra giá trị số tương ứng (khi tính biểu thức: K[i]=1+Floor[ (m-1)(A[i]-minval)(A[nmax]-minval) ]) => có thể phải sửa lại dữ liệu: đính kèm 1 giá trị số cho mỗi phần tử (chuỗi ký tự) => chỉ tính giá trị số 1 lần cho mỗi chuỗi: khi phân lớp thì xài giá trị số tương ứng; còn khi gọi Straight-Insertion Sort thì xài chuỗi ký tự ban đầu

(có gì sai sót xin các bạn chỉ giúp, cám ơn rất nhiều)

-thân

[StarGhost]

Good job bete.

Nói chung về vấn đề string, một thực tế là nó dường như có nhiều ứng dụng trong thực tế hơn là chuỗi. Nhưng mà bạn yên tâm, tui tin là chúng ta sẽ không bao giờ phải đối mặt với việc sắp xếp những strings như thế để kiếm tiền hay tồn tại gì gì đó đâu.

Dường như bete là người rất am hiểu về thuật toán, và nếu như tui ko nhầm thì lối suy nghĩ của bạn luôn có chỗ cho heuristic thì phải. Bạn bao nhiêu tuổi rồi, tự học thuật toán hay có trường lớp hẳn hoi? Bản thân tui thì luôn muốn cái gì cũng phải perfect, chính vì vậy đã bỏ lỡ nhiều cơ hội thành công.

Anyway, thanks.

SG.

[Pateheo]

Chào Star Ghost
Mình đã thử cài đặt và thực thi Flash Sort. Kết quả khá là khả quan. Xem nào, sắp xếp 1000000 ptử mất 1,125 giây. Cấu hìn máy là 1,7 GHz, 386 MB. Tuy nhiên mình cũng không hiểu sao là với phân tích O() của FlashSort là O(n), Quuick Sort là O(nlogn) mà chương trình chạy với Quick Sort cho thời gian là 432 miliseconds. Đã kiểm tra các thuật toán hoàn toàn đúng. Post lên cho bạn xem nhé.

Hình như mình không upload lên được. Nếu bạn có mail thì cho mình biết.
Ai có quan tâm đến thuật giải Flash Sort thì vào trang web sau:
http://www.neubert.net
À còn một điểm nữa SG chưa giải thích rõ là nên chọn m là bao nhiêu để được tối ưu. Thông thường thì là 0,1n.
Các bạn thực thi trên C++ hoặc Java nên chú ý công thức tính phân lớp như sau:
K(i)=floor((m-1.0)*(a[i]-min)/(max-min));
K thuộc [1,m-1]
bởi vì có sự khác biệt về mảng trong Pascal và C++( bắt đầu từ phần tử 0)
Mình cũng mới tìm thấy một số phương pháp sắp mới trên mạng là Shear Sort với O(sqrt(n)). Khá ấn tượng.

[StarGhost]

Bạn cho mình biết luôn là bạn sử dụng ngôn ngữ nào vậy? mail của mình là bellerophonsoldier@yahoo.com. Về vấn đề running time, nó tùy thuộc vào cách thức trình biên dịch biên dịch mã và tuỳ thuộc vào cách thức sử dụng vùng nhớ của ngôn ngữ. Chắc là bạn cũng biết Flash sort sử dụng nhiều vùng nhớ hơn quicksort phải không

SG.

[Pateheo]

Đúng là thời gian chạy phụ thuộc vào trình biên dịch. Mình sử dụng C++, và nhiều thuật toán hiện nay cũng thực thi trên nó. Tuy Flash Sort sử dụng thêm mảng phụ, nhưng chỉ là để lưu trong quá trình phân lớp như bạn đã nói. Kích thước chỉ bằng khoảng m=0,1n. Việc chọn kích thước cho mảng này là khó khăn, Bởi vì nếu m nhỏ thì phân lớp sẽ chính xác hơn->sắp xếp trong tưng lớp tốt hơn. m lớn thì fân lớp sẽ ít chính xác hơn ->..Merge Sort cũngdùng mảng phụ nhưng tốc độ cũng nhanh chán. Tuy nhiên Flash Sort là đán tìm hiểu. Ở kích thước trung bình, nó chạy ngang ngửa với Quick Sort. Vậy cũng đáng nể lắm.

[StarGhost]

Well, bây giờ hãy tạm thời gác cái real running time sang 1 bên đi, vì nó còn phụ thuộc vào nhiều thứ, chứ không phải chỉ là thiết kế của thuật toán. Cái mà tôi muốn nói đến ở đây là độ phức tạp O(n) của thuật toán.

Còn việc chọn giá trị của m mình cũng đã nói ở trên rồi. Thực ra việc chọn m tối ưu cũng tùy thuộc vào tốc độ trình biên dịch đối với từng loại câu lệnh, cái này mình chưa nghiên cứu kỹ, đây chỉ là kết quả khảo sát của ông N.Wirth, người viết Borland Pascal. Còn nếu chọn m theo độ phức tạp thì còn đơn giản hơn.

Bạn có thể kiểm tra bằng cách cho thêm bộ đếm để đếm số vòng lặp. Như thế bạn sẽ thấy rõ ràng rằng về cơ bản Flash Sort là O(n) còn Quicksort là O(n logn). Vậy là Flash Sort nhanh hơn Quicksort.

SG.