Lập trình động với Data.Map trong Haskell?

Question

Tôi đang cố triển khai một thuật toán dp đơn giản trong Haskell (đây là vấn đề phỏng đoán Collatz từ Dự án Euler); đây là tương đương với C++:

map<int,int> a; 
int solve(int x) { 
    if (a.find(x) != a.end()) return a[x]; 
    return a[x] = 1 + /* recursive call */; 
} 

Vì vậy, các mã mà tôi đã viết trong Haskell đã kết thúc tìm kiếm như thế này:

solve :: (Memo, Int) -> (Memo, Int) 
solve (mem, x) = 
case Map.lookup x mem of 
    Just l -> (mem, l) 
    Nothing -> let (mem', l') = {- recursive call -} 
       mem'' = Map.insert x (1+l') mem' 
      in (mem'', 1+l') 

(Tôi nghĩ rằng tôi chỉ reimplementing một đơn nguyên nhà nước ở đây, nhưng không bao giờ nhớ rằng cho thời điểm này) mã trong đó kêu gọi giải quyết cố gắng để tìm giá trị lớn nhất nó có thể cung cấp cho một tham số tối đa là K = 1e6:.

foldl' 
(\(mem,ss) k -> 
    let (mem',x') = solve (mem, k) 
    in (mem', (x', k):ss)) 
(Map.singleton 1 1, [(1,1)]) [2..100000] 

các mã như viết ở trên không thành công với một chồng tràn. Điều này là để được mong đợi, tôi hiểu, bởi vì nó xây dựng một thunk thực sự lớn chưa được đánh giá cao. Vì vậy, tôi đã thử sử dụng

x' `seq` (mem', (x',k):ss) 

bên trong nếp gấp 'và tính toán câu trả lời đúng cho K = 1e5. Nhưng điều này không thành công cho K = 1e6 (ngăn xếp tràn trong 12 giây). Sau đó, tôi đã thử sử dụng

mem'' `seq` l' `seq` (mem'', 1+l') 

trong dòng giải quyết cuối cùng, nhưng điều này không có sự khác biệt (ngăn xếp tràn). Sau đó, tôi cố gắng sử dụng

mem'' `deepseq` l' `seq` (mem'', 1+l') 

này là cực kỳ chậm, có lẽ vì deepseq đi qua toàn bộ bản đồ mem '', làm phức tạp thời gian của thuật toán bậc hai thay vì n * log (n).

Cách chính xác để triển khai điều này là gì? Tôi bị mắc kẹt bởi vì tôi không thể tìm ra cách để làm cho toàn bộ tính toán nghiêm ngặt, và tôi không hoàn toàn chắc chắn mà một phần của tính toán cho tràn ngăn xếp, nhưng tôi nghi ngờ đó là bản đồ. Tôi có thể sử dụng, ví dụ, mảng, nhưng tôi muốn hiểu những gì tôi đang làm sai ở đây.

Answer 1

Ngăn xếp ngăn xếp sẽ không biến mất khi bạn sử dụng loại số nguyên có ký 32 bit. Đối với một số giá trị khởi đầu, chuỗi rời khỏi dải 32 bit và đi vào một vòng lặp vô hạn các số âm. Sử dụng Integer hoặc Int64 hoặc Word64.