Thuật toán trực tuyến Haskell tuyến tính thời gian

Question

Hãy tha thứ cho tôi nếu tôi lạm dụng các từ lớn trong tiêu đề; Tôi không quá hiểu biết về họ nhưng hy vọng họ mô tả vấn đề của tôi. Tôi đã viết một sơ đồ phức tạp để thử và mã hóa các chuỗi theo yêu cầu these. Đối với các chuỗi có độ dài từ 10^4 trở lên, mã tôi viết khá chậm và tôi tự hỏi - vì nó xử lý các khối 200 tại một thời điểm (mặc dù chỉ di chuyển một ký tự về phía trước để lấy đoạn tiếp theo), có thể không được sửa đổi để xuất kết quả nhanh hơn hoặc theo kiểu thời trang tuyến tính hơn (ví dụ, ngay lập tức xuất kết quả cho mỗi 200 ký tự được xử lý). Bất kỳ trợ giúp nào về việc đó hoặc các tối ưu hóa đáng chú ý khác sẽ được đánh giá cao.

mỗi gợi ý tel, tôi đơn giản hóa ví dụ của tôi:

encode xs = encode' xs [] where 
    encode' []  result = result 
    encode' (z:zs) result 
    | null test = encode' zs (result ++ [z]) 
    | otherwise = encode' (drop numZsProcessed zs) (result ++ processed) 
    where test = ..some test 
     toProcess = take 200 (z:zs) 
     processed = ..do something complicated with toProcess 
     numZsProcessed = ..number of z's processed 

Answer 1

Haskell và đuôi đệ quy không hòa hợp cũng như ngôn ngữ chức năng khác và đuôi đệ quy. Hãy làm một số hướng dẫn sử dụng giảm trên một số mã rất đơn giản để xem những gì đang xảy ra với đệ quy đuôi. Đây là triển khai đệ quy có đuôi của map (1+).

go [] r = r 
go (x:xs) r = go xs (r ++ [1+x]) 

Ngoài ra chúng tôi phải ghi nhớ định nghĩa của (++):

[] ++ ys = ys 
(x:xs) ++ ys = x : (xs ++ ys) 

Bây giờ chúng ta hãy giảm go [1,2,3,4,5] []. Hãy nhớ rằng [x,y,z] là ký hiệu cho x:(y:(z:[])) hoặc cho ngắn x:y:z:[].

go [1,2,3,4,5] [] 
go [2,3,4,5] ([] ++ [2]) -- 2 here is actually the thunk 1+1, but 
          -- for compactness I am reducing earlier 
go [3,4,5] (([] ++ [2]) ++ [3]) 
go [4,5] ((([] ++ [2]) ++ [3]) ++ [4]) 
go [5] (((([] ++ [2]) ++ [3]) ++ [4]) ++ [5]) 
go [] ((((([] ++ [2]) ++ [3]) ++ [4]) ++ [5]) ++ [6]) 
(((([] ++ [2]) ++ [3]) ++ [4]) ++ [5]) ++ [6] 
((([2] ++ [3]) ++ [4]) ++ [5]) ++ [6] 
(((2:([] ++ [3]) ++ [4]) ++ [5]) ++ [6] 
((2:(([] ++ [3]) ++ [4]) ++ [5]) ++ [6] 
(2:((([] ++ [3]) ++ [4]) ++ [5]) ++ [6] 
2:(((([] ++ [3]) ++ [4]) ++ [5]) ++ [6]) -- first observable output 
2:((([3] ++ [4]) ++ [5]) ++ [6]) 
2:((3:([] ++ [4]) ++ [5]) ++ [6]) 
2:(3:(([] ++ [4]) ++ [5]) ++ [6]) 
2:3:((([] ++ [4]) ++ [5]) ++ [6])   -- second observable output 
2:3:(([4] ++ [5]) ++ [6]) 
2:3:(4:([] ++ [5]) ++ [6]) 
2:3:4:(([] ++ [5]) ++ [6])     -- third observable output 
2:3:4:([5] ++ [6]) 
2:3:4:5:([] ++ [6])       -- fourth observable output 
2:3:4:5:6:[]        -- final output 

Xem cách mỗi mục trong đầu ra cần làm việc theo cách của nó ra ngoài từ chuỗi lồng nhau sâu? Điều này làm cho nó mất thời gian bậc hai trong kích thước của đầu vào để có được tất cả các đầu ra. Bạn cũng sẽ thấy một hành vi mà một vài mục đầu tiên được mang lại từ từ và nó sẽ nhanh hơn và nhanh hơn khi bạn đến cuối danh sách. Sự giảm này giải thích điều đó.

Vấn đề hiệu suất chính ở đây là gắn phần tử mới vào cuối danh sách, điều này cần thời gian tỷ lệ thuận với kích thước của danh sách bạn đang thêm vào. Một cách tốt hơn là chống lại ở mặt trước, đó là một hoạt động tant-time cons. Điều này sẽ làm cho đầu ra bị đảo ngược, vì vậy bạn cần đảo ngược kết quả.

go [] r = reverse r 
go (x:xs) r = go xs ((1+x):r) 

reverse xs = rev xs []  -- roughly from the report prelude 
rev [] r = r 
rev (x:xs) r = rev xs (x:r) 

Và, chúng ta hãy giảm:

go [1,2,3,4,5] [] 
go [2,3,4,5] [2] 
go [3,4,5] [3,2] 
go [4,5] [4,3,2] 
go [5] [5,4,3,2] 
go [] [6,5,4,3,2] 
reverse [6,5,4,3,2] 
rev [6,5,4,3,2] [] 
rev [5,4,3,2] [6] 
rev [4,3,2] [5,6] 
rev [3,2] [4,5,6] 
rev [2] [3,4,5,6] 
rev [] [2,3,4,5,6] 
[2,3,4,5,6]   -- first and all observable output! 

Vì vậy, đây rõ ràng là làm việc ít hơn so với phiên bản đầu tiên. Đây là phong cách được sử dụng trong các ngôn ngữ nghiêm ngặt như Scheme và ML, bởi vì nó có hiệu suất bộ nhớ tốt. Tuy nhiên, nó có một số nhược điểm:

• Tất cả đầu vào phải được tiêu thụ trước khi có thể tạo bất kỳ đầu ra nào. Thật vậy, toàn bộ tính toán được thực hiện trước khi bất kỳ kết quả nào được tạo ra.
• Bởi vì điều này, nó không bao giờ mang lại bất kỳ đầu ra khi đưa ra một danh sách vô hạn.
• Nó liên quan đến reverse, mất thêm một thời gian O(n) và không liên quan gì đến những gì chúng tôi đang thực hiện (việc đảo ngược phải làm gì với việc thêm một thành phần và bảo toàn thứ tự?).

Bằng ngôn ngữ lười như Haskell, chúng tôi có thể làm tốt hơn. Kỳ lạ thay, và đẹp mắt, cách chúng ta làm là bằng cách viết nó thậm chí còn ngây thơ hơn.

go [] = [] 
go (x:xs) = (1+x):go xs 

và giảm:

go [1,2,3,4,5] 
2:(go [2,3,4,5])  -- first observable output 
2:3:(go [3,4,5])  -- second observable output 
2:3:4:(go [4,5])  -- third observable output 
2:3:4:5:(go [6])  -- fourth observable output 
2:3:4:5:6:(go []) -- fifth observable output 
2:3:4:5:6:[]   -- final output 

Phải mất thậm chí còn ít làm việc, và nó bắt đầu năng suất sản lượng trước khi thậm chí nhìn vào phần còn lại của danh sách, vì vậy nó có hiệu suất tốt trong tính toán dòng và hoạt động trên đầu vào vô hạn. Và việc thực hiện là đơn giản và rõ ràng như bạn có thể hy vọng.

Tôi hy vọng điều này sẽ cho bạn một số trực giác về cách đệ quy đuôi hoạt động trong Haskell. Ví dụ của bạn, tôi đề nghị loại bỏ đuôi đệ quy và viết lại theo kiểu ngây thơ tương tự như go cuối cùng của chúng tôi, sử dụng trực giác mà tôi hy vọng tôi đề xuất từ ​​bài đăng này để mang lại "tiền tố đầu vào càng lớn càng tốt, càng sớm càng tốt" (thông báo trả lại x:xs ngay lập tức mang lại x, ngay cả khi có thêm một số công việc cần thực hiện để tính xs - đó là sự lười biếng trong hành động (không).