Sắp xếp tăng dần dãy số có 4*10^8 phần tử trong vòng 30 giây

Chúng ta đều biết: Thuật toán O(n) tính tổng các số từ 1 tới 10^8 được thực hiện trong vòng 0.6 giây trên 1 processor.

Vậy: Thuật toán sắp xếp QuickSort có độ phức tạp O(nlogn) thực hiện bao với n bằng bao nhiêu trong vòng 0.6 giây?

(Ở đây, chúng ta bỏ qua thời gian nhập/xuất dữ liệu. Thực tế, việc nhập xuất dữ liệu được thực hiện trên đĩa cứng nên tốc độ rất chậm)

Trả lời: Chúng ta giải bất phương trình: nlog(n) < 10^8. Kết quả là: n = 4*10^6.

Như vậy: Với n = 4*10^8 thì thời gian thực hiện của chương trình sẽ là:

4*10^8log(4*10^8) / [4*10^6log(4*10^6)] * 0.6 = 100*(8log10+2)/(6log10 + 2) * 0.6 ≈ 60 giây

Nhưng ta lại muốn sắp xếp dãy với n = 4*10^8 phần tử trong thời gian ngắn hơn. Vậy phải làm thế nào?

Một cách tự nhiên: Người ta nghĩ: Nếu 1 processor chạy dữ liệu với n = 4*10^6 trong vòng 0.6 giây, vậy nếu giờ ta có 10 processors thì sẽ sao nhỉ?

Câu trả lời là: Nếu ta chạy dữ liệu n = 4*10^8 với 10 processors thì mỗi processor đảm nhiệm việc sắp xếp cho  4*10^8/10 = 4*10^7 số hạng. Thời gian để sắp xếp 4*10^7 trên mỗi processor là: 4*10^7log(4*10^7) / [4*10^6log(4*10^6)] * 0.6 = 10*(7log10+2)/(6log10 + 2) * 0.6 ≈ 10*0.6 giây

Mặt khác, sau khi sắp xếp trên 10 processors xong, cần phải tổng hợp kết quả lại. Việc tổng hợp kết quả được truyền về cho 1 processor (processor này được gọi là máy master). Việc tổng hợp kết quả này giống hệt hàm Merge trong thuật toán MergeSort. Do có n phần tử và 10 processors nên mỗi phần tử của mảng trong lúc tổng hợp kết quả được xét tối đa 10 lần. Vậy độ phức tạp của việc tổng hợp này là O(10*n). Mà n = 4*10^8. Nên thời gian tổng hợp sẽ là: 10*[4*10^8]/10^8 * 0.6 = 40*0.6 giây.

Vậy: tổng thời gian thực hiện thuật toán QuickSort song song trên 10 processors là: 10*0.6 + 40*0.6 = 50*0.6 = 30 giây.

Như vậy với n = 4*10^8, mặc dù chúng ta sử dụng đến 10 processors nhưng thời gian thực hiện thuật toán chỉ giảm đi một nửa (thời gian thực hiện với n = 4*10^8 trên 1 processor là 60 giây)

P/S: Nếu không thực hiện thuật toán QuickSort mà thuật toán sắp xếp chọn (độ phức tạp O(n^2)) với n = 4*10^8 trên 1 processor thì thời gian chạy chương trình sẽ là:

[4*10^8]^2 / 10^8 * 0.6= 16*10^8 * 0.6 giây ≈ 30 năm

4 Responses to “Sắp xếp tăng dần dãy số có 4*10^8 phần tử trong vòng 30 giây”

  1. tosonnguyen Says:

    Nếu bạn sử dụng 100 processors thì thời gian chạy chương trình sẽ là: 0.6 + 100*4*0.6 ≈ 240 giây > 60 giây ???
    (60 giây là thời gian chạy thuật toán QuickSort trên 1 processor)

    Điều đó có nghĩa: Không phải có nhiều processors thì lợi thế hơn😀

  2. tosonnguyen Says:

    Thường người ta nghĩ song song là cho chương trình chạy nhanh lên. Nhưng như ví dụ về song song hóa thuật toán QuickSort ở trên. Nếu quá trình tổng hợp kết quả từ các processors thiếu hiệu quả thì tác dụng song song lại đi ngược lại với mong muốn của chúng ta. Thậm chí khi khai báo càng nhiều processors, nó còn tốn nhiều thời gian hơn so khi chạy trên 1 processor.

  3. tosonnguyen Says:

    Một số người viết chương trình song song nhưng chỉ cho chạy với số lượng phần tử n = 100. Như vậy, việc song song chương trình không có ý nghĩa gì cả vì một chương trình tuần tự trên 1 processor thừa sức chạy được với n = 4*10^6 trong vòng 0.6 giây

    Việc thử nghiệm với n = 100 hay n = 10 chỉ dành cho mục đích xác định xem chương trình chạy có chính xác theo yêu cầu đề ra hay không mà thôi.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: