cách sắp xếp hợp nhất nhanh hơn so với các câu đố sắp xếp chèn tôi

Question

Chỉ cần có đôi chân của tôi ướt trong thuật toán phân loại với Haskell. Tôi đã thực hiện chèn-sort và merge-sort

insert_sort :: (Ord a, Show a) => [a] -> [a] 
insert_sort keys = foldr f [] keys 
      where f key []  = [key] 
       f key acc  = insert key acc 
       insert y []  = [y] 
       insert y (x:xs) 
        | x < y  = x : insert y xs 
        | otherwise = y : x : xs 

merge_sort :: (Ord a, Show a) => [a] -> [a] 
merge_sort (x:[]) = [x] 
merge_sort keys = merge (merge_sort (take len keys)) (merge_sort (drop len keys)) 
     where len   = length keys `div` 2 
      merge :: [a] -> [a] -> [a] 
      merge (x:xs) []  = (x:xs) 
      merge []  (y:ys) = (y:ys) 
      merge (x:xs) (y:ys) = if x <= y 
            then x : merge (xs) (y:ys) 
            else y : merge (x:xs) ys 

Đây là cách tôi so hiệu quả của họ:

insert_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int] 
merge_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int] 

Cả hai người bắt đầu để in ra kết quả sau một thời gian ngắn nhưng merge-sort in nhiều nhanh hơn. Như chúng ta đã biết, sắp xếp hợp nhất nhanh hơn nhiều so với việc chèn sắp xếp cho các tập dữ liệu lớn. Tôi nghĩ rằng điều đó sẽ được thể hiện bằng cách họ đưa ra kết quả (như một sự trì hoãn lâu dài so với một kết quả ngắn) không phải cách họ in kết quả. Có phải vì tôi sử dụng foldr khi chèn sắp xếp không? Có gì đằng sau hiện trường?

EDIT: Thx guys. Tôi đã nghe nói về đánh giá lười biếng kể từ khi tôi bắt đầu tìm hiểu Haskell nhưng chưa nhận được hang của nó. Ai sẽ minh họa thêm một chút với một tập dữ liệu nhỏ, nói [5,2,6,3,1,4]? Làm thế nào là nó có thể xuất kết quả trước khi kết thúc phân loại với foldr kể từ khi các yếu tố đầu tiên đến cuối cùng?

Answer 1

Hậu trường là đánh giá lười biếng. Sự bắt đầu của các danh sách được sắp xếp được xác định trước khi sắp xếp hoàn tất, vì vậy nó có thể được xuất ra trước khi công việc kết thúc. Kể từ khi một mergesort nhanh hơn, danh sách sắp xếp hợp nhất được in ra nhanh hơn.

Theo yêu cầu: cách phân loại số tiền thu được [5,2,6,3,1,4]. Tôi sử dụng insert_sort = foldr ins [] để ngắn gọn.

insert_sort [5,2,6,3,1,4] 
    = foldr ins [] [5,2,6,3,1,4] 
    = 5 `ins` foldr ins [] [2,6,3,1,4] 
    = 5 `ins` 2 `ins` [6,3,1,4] ... 
    = 5 `ins` 2 `ins` 6 `ins` 3 `ins` 1 `ins` 4 `ins` [] 
    = 5 `ins` 2 `ins` 6 `ins` 3 `ins` 1 `ins` (4:[]) 
    = 5 `ins` 2 `ins` 6 `ins` 3 `ins` (1:4:[]) 
    = 5 `ins` 2 `ins` 6 `ins` (1 : (3 `ins` (4:[]))) 
    = 5 `ins` 2 `ins` (1 : (6 `ins` (3 `ins` (4:[])))) 
    = 5 `ins` (1 : (2 `ins` (6 `ins` (3 `ins` (4:[]))))) 
    = 1 : (5 `ins` (2 `ins` (6 `ins` (3 `ins` (4:[]))))) -- now 1 can be output 
    = 1 : (5 `ins` (2 `ins` (6 `ins` (3:4:[])))) 
    = 1 : (5 `ins` (2 `ins` (3 : (6 `ins` (4:[]))))) 
    = 1 : (5 `ins` (2 : (3 : (6 `ins` (4:[]))))) 
    = 1 : 2 : (5 `ins` (3 : (6 `ins` (4:[]))))   -- now 2 can be output 
    = 1 : 2 : 3 : (5 `ins` (6 `ins` (4:[])))    -- now 3 
    = 1 : 2 : 3 : (5 `ins` (4:6:[])) 
    = 1 : 2 : 3 : 4 : (5 `ins` (6:[]))     -- now 4 
    = 1 : 2 : 3 : 4 : 5 : 6 : []       -- done 

Và merge sort (viết tắt: merge = mg, merge_sort = ms):

merge_sort [5,2,6,3,1,4] 
    = mg (ms [5,2,6]) (ms [3,1,4]) 
    = mg (mg (ms [5]) (ms [2,6])) (mg (ms [3]) (ms [1,4])) 
    = mg (mg [5] (mg [2] [6])) (mg [3] (mg [1] [4])) 
    = mg (mg [5] [2,6]) (mg [3] [1,4]) 
    = mg (2 : mg [5] [6]) (1 : mg [3] [4]) 
    = 1 : mg (2 : mg [5] [6]) (mg [3] [4])    -- now 1 can be output 
    = 1 : mg (2 : mg [5] [6]) [3,4] 
    = 1 : 2 : mg (mg [5] [6]) [3,4]      -- now 2 can be output 
    = 1 : 2 : mg [5,6] [3,4] 
    = 1 : 2 : 3 : mg [5,6] [4]       -- now 3 
    = 1 : 2 : 3 : 4 : mg [5,6] []       -- now 4 
    = 1 : 2 : 3 : 4 : 5 : 6 : []       -- now 5 and 6 

Phải thừa nhận rằng tôi đã thực hiện một vài vết cắt ngắn, nhưng Haskell không phải là người duy nhất lười biếng.

Answer 2

OK đây là sự cố. Bạn muốn tôi in ra:

merge_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int] 

Tôi biết rằng đây là danh sách. Vì vậy, đầu tiên tôi sẽ in ra một cú đúp mở

[ 

Sau đó, tôi sẽ tìm phần tử đầu tiên của danh sách, in ra và sau đó là dấu phẩy. Điều đó có nghĩa là tôi phải bắt đầu đánh giá biểu thức đó cho đến khi tôi có thể tìm ra yếu tố đầu tiên của danh sách là gì.

merge_sort THUNK0 

Bây giờ tôi cần phải khớp mẫu. THUNK phù hợp với (x:[]) hoặc không. Nhưng tôi chưa biết. Vì vậy, tôi sẽ đánh giá thunk một chút. Tôi làm cho thunk sản xuất hai số ngẫu nhiên đầu tiên (trong số 100000). Bây giờ tôi biết rằng nó không phù hợp với định nghĩa đầu tiên, vì vậy tôi lấy định nghĩa thứ hai là merge_sort.

merge_sort keys = merge THUNK1 THUNK2 -- keys = THUNK0 

Cũng đủ dễ dàng ... đó chỉ là cuộc gọi để hợp nhất. Tôi sẽ mở rộng định nghĩa đó. Rất tiếc, có ba các mẫu khác nhau này có thể khớp với nhau.Tôi đoán tôi nên đánh giá THUNK1 một chút và xem nếu nó phù hợp với mô hình định nghĩa đầu tiên, (x:xs)

merge_sort (take THUNK3 THUNK0) 

Về merge_sort một lần nữa, chúng ta? Điều đó có nghĩa là tôi cần đánh giá (take THUNK3 THUNK0) vừa đủ để biết liệu nó có phù hợp với (x:[]) hay không. Chết tiệt. take là nghiêm ngặt trong đối số đầu tiên ... có nghĩa là tôi phải đánh giá đầy đủ THUNK3. Ok ... hơi thở sâu ...

len = length THUNK0 `div` 2 

Bây giờ đây là trường hợp khó chịu. Để tính toán length trên THUNK0 (đây là danh sách), tôi phải mở rộng SPINE SPINE. Tôi không phải tính toán các giá trị bên trong, nhưng tôi cần phải xác định cấu trúc của toàn bộ danh sách. Điều này, tất nhiên, được thực hiện một mẫu phù hợp tại một thời điểm, xác định xem nó là [] hoặc (x:xs). Nhưng nói chung, length là "cột sống nghiêm ngặt".

tạm dừng ngắn trong khi tôi xác thịt ra cột sống của một danh sách 100000-yếu tố

Phew, có mà làm. Bây giờ tôi biết chiều dài, có nghĩa là tôi biết len = 500000. THUNK0 là cuối cùng là được đánh giá đầy đủ! Phew! Tôi đã ở đâu?

merge_sort (take 500000 THUNK3) 

---

Và vân vân. merge_sort sẽ tiếp tục cố gắng càng lười càng tốt. Các cuộc gọi đệ quy đến merge_sort sẽ càng lười càng tốt. Cuối cùng, để xác định phần tử đầu tiên của ngoài cùng merge_sort, chúng ta sẽ cần phải biết phần tử đầu tiên của cả hai cuộc gọi đệ quy đến merge_sort. Và để biết phần tử đầu tiên của những người ... chúng tôi sẽ cần những yếu tố đầu tiên của cuộc gọi đệ quy tiếp theo, vv Vì vậy, sẽ có khoảng O (n) công việc thực hiện, bởi vì tất cả các yếu tố cần phải được đánh giá (thực hiện ngẫu nhiên hệ số cho mỗi người).

Sau đó, hãy nghĩ về nó như một giải đấu. Mỗi phần tử được ghép nối với một phần tử khác. Các yếu tố "thắng" (thấp nhất) chuyển sang vòng tiếp theo (trở thành phần tử đầu tiên của cuộc gọi đệ quy đến mức thấp nhất merge_sort s). Còn có một cuộc cạnh tranh với 1/2 như nhiều chiến binh, và 1/2 của những (1/4 của tổng số) chuyển sang vòng tiếp theo, vv Điều này cũng hóa ra là O (n) công việc , kể từ khi (n/2) so sánh được thực hiện trong vòng đầu tiên, và vòng tiếp theo phát triển nhỏ hơn quá nhanh để có ý nghĩa. (Tổng số 1/2 + 1/4 + 1/8 ... hội tụ ở mức 1, nghĩa là tổng số các so sánh n được thực hiện.)

Tất cả trong tất cả, O (n) công việc cần được thực hiện để cuối cùng tạo ra phần tử đầu tiên. Công việc bổ sung cần phải được thực hiện cho các yếu tố tiếp theo, nhưng tổng khối lượng công việc kết thúc lên được O (n log (n)).

---

Bây giờ, hãy tương phản với insert_sort. Chỉ cần suy nghĩ về cách nó hoạt động: nó đi qua danh sách và "chèn" từng phần tử vào danh sách được sắp xếp.Điều đó có nghĩa là bạn không thể biết chắc chắn yếu tố đầu tiên được sắp xếp là cho đến khi bạn đã thực hiện bit cuối cùng của công việc và chèn phần tử cuối cùng (có thể là phần tử thấp nhất) vào danh sách được sắp xếp.

Tôi hy vọng điều này minh họa rõ ràng cách merge_sort không cần thực hiện tất cả công việc để bắt đầu tạo kết quả, trong khi insert_sort.