View Full Version : Có bồ nào biết thuật toán Shear Sort không ?
Mình nghe nói thuật toán này sắp xếp rất nhanh ( độ phúc tạp là căn n ).Có ai biết rõ về nó chỉ giúp mình với ( có cả code càng tốt ).Cám ơn.
Đọc xong câu hỏi của aabbc tui rất lấy làm lạ: O(căn bậc 2 của n) !?!? Sao nhỏ dữ vậy ta !?
Tìm trên mạng:
http://www.math-info.univ-paris5.fr/~ycart/mst/mst041/Group2/shear.html
http://www.google.com/search?hl=en&q=shear+sort
(thuật toán này có độ phức tạp thấp như vậy là nhờ làm song song.
Nếu tui nhớ không thì nếu không làm song song thì không thể tốt hơn O(n))
(những điều mình biết đúng là hạt cát, nội sắp xếp không thôi mà học thêm được vài giải thuật mới rồi (Flash-Sort, Shear-Sort) :( => cám ơn aaabbc rất nhiều: nhờ bạn đặt câu hỏi mới có dịp tìm tòi để biết thêm!)
-thân
StarGhost
02-05-2005, 17:26
to aaabbc: Bạn đừng tin, bọn này chúng nó nói láo đấy. Làm quái có thuật toán sắp xếp nào độ phức tạp < n. Bản thân nó đã là nghịch lý rồi, không duyệt hết các phần tử thì làm sao mà sắp xếp được.
sqrt(1000000)=1000. Chả lẽ sắp xếp 1000000 phần tử chỉ cần duyệt vài nghìn lần thôi sao. That's www.potay.com
SG.
to StarGhost: bạn đọc cái algorithm chưa, mà nói là "nói láo" :kiss
Họ nói thiệt đó chớ, mà có điều cái algorithm này là parallel algorithm, và cái độ phức tạp tối ưu O(sqrt(n)log(n)) chỉ đạt được trong một trường hợp "hy hữu" nào đó (số processor là sqrt(n)log(n)). Tóm lại, độ phức tạp của algorithm này là nlog(n)/p, với p là số processor.
=> Nếu làm sequential thì forget nó đi là vừa
Mình đã thử cài đặt thằng cu này bằng sequential rồi.Với 500.000 ptử thì sắp trong 7-8 s. Nói chung cũng tạm được. Đó là mình thực hiện Insertion Sort trong các hàng và cột của nó.Nếu bằng Quick Sort thì chắc nhanh hơn đó, nhưng mà cũng rắc rối hơn. Mình thấy cái này nó giống một fần của Bubble Sort,1 fần giống Merge Sort. Cái hay chủ yếu của nó là làm cho các fần tử nhỏ "nổi" lên trên đầu mảng rất ấn tượng, rõ ràng hơn cả bubble sort. Nhưng cái này có nhược điểm là chỉ xếp với các mảng có số pt là chính phương. Có thể khắc phục bằng một số cách khá đơn giản như tách phần dư ra và trộn vào lúc cuối, hoặc là thêm một số phần tử vào sau mảng để tạo nên một mảng có số p tử là bội của sqrt(n).Phần tử thêm vào này nên là ptử lớn nhất trong mảng.Mà sắp xếp với mảng một chiều thì tiện lợi hơn nhiều.
StarGhost
04-05-2005, 18:14
to poly:ờ hé, tui đọc rùi, nhưng mà chẳng hiểu gì ráo. Bạn có thể giải thích rõ hơn 1 chút được hông. Đành rằng là cho chúng nó vào 1 cái square, rồi sort các lines&columns, nhưng rùi làm sao để sort các columns&lines đây?
SG.
Tôi đã tìm một số tài liệu về các thuật toán sắp xếp song song ,, thực ra để đạt được độ phức tạp tốt như vậy thì phải có những cài đặt hết sưc phức tạp và hầu như chỉ mang tính lí thuyết . Một số tài liệu họ đưa ra phương thức cài đặt dựa vào các thuật toán Radix Sort , Block Merge Sort ... trên tư tưởng của thuật toán sắp song song theo từng hàng và từng cột . Thực tế không cần phải sử dụng những thuật toán phức tạp như vậy để cài đăt .
Tôi dẫ thử cài đặt thuật toán này dựa vào 2 cách là dùng một trong hai thuật toán insertion sort , quick sort và tốc độ thực thi khi sắp 1 triệu phần tử : 7s khi thử dùng quicksort . đối với selection sort thì lâu hơn một chút . Tuy nhiên nếu dùng quick sort vào shear sort mà lại chậm hơn quick sort thì thật là ......
Theo tôi nếu cài đặt đúng tư tưởng của nhiều tài liệu có lẽ sẽ có tốc độ thực thi tốt hơn nhiều .
Có bồ nào thử cài đặt nó và có tốc độ tương đối chưa ??
to poly:ờ hé, tui đọc rùi, nhưng mà chẳng hiểu gì ráo. Bạn có thể giải thích rõ hơn 1 chút được hông. Đành rằng là cho chúng nó vào 1 cái square, rồi sort các lines&columns, nhưng rùi làm sao để sort các columns&lines đây?
Sort trong col, row thì dùng bất cứ thuật toán sort nào bạn thích, vì đó là sort trong 1 processor mà...
Tôi dẫ thử cài đặt thuật toán này dựa vào 2 cách là dùng một trong hai thuật toán insertion sort , quick sort và tốc độ thực thi khi sắp 1 triệu phần tử : 7s khi thử dùng quicksort . đối với selection sort thì lâu hơn một chút . Tuy nhiên nếu dùng quick sort vào shear sort mà lại chậm hơn quick sort thì thật là ......
Cái này tôi nghĩ giải thích cũng dễ, bạn cứ giả sử sort các subgroup trong shear sort dùng quick sort đạt best complexity O(n*logn), vậy giải thuật shear sort của bạn có complexity xấp xỉ kO(n*logn), với kn=N. So sánh với best complexity của quick sort là O(N*logN) thì thua (bạn có thể prove k*O(n*logn)>O(N*logN) dễ dàng).
Bạn code parallel hay sequential? Dùng sequential thì nó chậm hơn các giải thuật khác là đúng rồi. Nếu dùng parallel thì có thể sẽ nhanh hơn nếu các điều kiện nó đòi thỏa mãn.Thật ra Shear Sort chỉ là giải thuật lý thuyết để sort (vì nó đòi hỏi khá nhiều) nên chẳng ai dùng nó để sort cả.
Hơn nữa việc timing trong parallel là rất khó (bạn nào làm rồi thì biết), thời gian ko tăng tuyến tính với số processor đâu :) nên chỉ có ý nghĩa thực dụng (tức là người ta có thể chấp nhận dùng 16 processor để tốc độ chỉ tăng gần gấp đôi) chứ ko phải dùng để "đấu" algorithms...
rockman88v
22-05-2009, 11:43
to aaabbc: Bạn đừng tin, bọn này chúng nó nói láo đấy. Làm quái có thuật toán sắp xếp nào độ phức tạp < n. Bản thân nó đã là nghịch lý rồi, không duyệt hết các phần tử thì làm sao mà sắp xếp được.
sqrt(1000000)=1000. Chả lẽ sắp xếp 1000000 phần tử chỉ cần duyệt vài nghìn lần thôi sao. That's www.potay.com
SG.
Trên đời này người ta nói "thiên ngoại hữu thiên", núi cao còn có núi cao hơn vậy mà tên này nói "đừng tin" nghe ngu vật. :))
Tớ đang thực tập về Parallel Programming nên thấy cái đó là bình thường mà. Bạn gì nói mà vừa giống bubble sort vừa giống merge sort là thực ra đó là bubble nhưng đc song song hóa. Lúc nào rảnh tớ post code lên cho mọi người tham khảo luôn.
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.