Làm thế nào tôi có thể nhận được một accumArray nghiêm ngặt?

Question

Tôi có một danh sách các cặp khóa-giá trị và tôi muốn đếm số lần mỗi khóa xuất hiện và giá trị nó xảy ra với, nhưng khi tôi thử, tôi nhận được tràn ngăn xếp. Dưới đây là một phiên bản đơn giản của mã Tôi đang chạy:

import Array 
add (n, vals) val = n `seq` vals `seq` (n+1,val:vals) 
histo = accumArray add (0,[]) (0,9) [(0, n) | n <- [0..5000000]] 
main = print histo 

Khi tôi biên dịch này với '-O GHC' và chạy nó, tôi nhận được "Stack không gian tràn: kích thước hiện tại 8.388.608 byte."

Tôi nghĩ rằng tôi biết những gì đang xảy ra: accumArray có cùng tính chất như foldl, và vì vậy tôi cần một phiên bản nghiêm ngặt của accumArray. Thật không may, chỉ có một tôi đã tìm thấy trong Data.Array.Unboxed, mà không làm việc cho một mảng các danh sách.

Tài liệu nói rằng khi hàm tích lũy nghiêm ngặt, thì accumArray cũng nên, nhưng tôi không thể làm việc này, và thảo luận here tuyên bố rằng tài liệu sai (ít nhất là cho GHC).

Có phiên bản nghiêm ngặt của accumArray khác với phiên bản trong Data.Array.Unboxed không? Hay là có cách nào tốt hơn để làm những gì tôi muốn?

Answer 1

Vâng, nghiêm ngặt không nhất thiết có nghĩa là không có khối được tạo ra, nó chỉ có nghĩa là nếu một đối số là dưới cùng, kết quả là dưới quá. Nhưng accumArray không phải là nghiêm ngặt, nó chỉ viết đáy cho mảng nếu chúng xảy ra. Nó không thể thực sự làm bất cứ điều gì khác, vì nó phải cho phép các chức năng không nghiêm ngặt có thể tạo ra các giá trị được xác định từ đáy trung gian. Và máy phân tích độ chính xác không thể ghi lại nó sao cho hàm tích lũy được đánh giá thành WHNF trên mỗi ghi nếu nó là nghiêm ngặt, bởi vì điều đó sẽ thay đổi ngữ nghĩa của chương trình theo một cách khá quyết liệt (một mảng chứa một số đáy so với đáy) .

Điều đó nói rằng, tôi đồng ý rằng có một sự thiếu hụt đáng tiếc về các chức năng nghiêm ngặt và háo hức ở một số khu vực.

Đối với vấn đề của bạn, bạn có thể sử dụng một chồng lớn hơn (+RTS -K128M không đủ ở đây, nhưng 256M đã làm), hoặc bạn có thể sử dụng

import Data.Array.Base (unsafeRead, unsafeWrite) 
import Data.Array.ST 
import GHC.Arr 

strictAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(i,a)] -> Array i e 
strictAccumArray fun ini (l,u) ies = case iar of 
             Array _ _ m barr -> Array l u m barr 
    where 
    iar = runSTArray $ do 
     let n = safeRangeSize (l,u) 
      stuff = [(safeIndex (l,u) n i, e) | (i, e) <- ies] 
     arr <- newArray (0,n-1) ini 
     let go ((i,v):ivs) = do 
       old <- unsafeRead arr i 
       unsafeWrite arr i $! fun old v 
       go ivs 
      go [] = return arr 
     go stuff 

Với ghi nghiêm ngặt, các thunks được giữ nhỏ, vì vậy không có tràn ngăn xếp. Nhưng hãy cẩn thận, danh sách mất rất nhiều không gian, vì vậy nếu danh sách của bạn quá dài, bạn có thể bị cạn kiệt.

Một lựa chọn khác là sử dụng một Data.Map (hoặc Data.IntMap, nếu phiên bản của containers là 0.4.1.0 hoặc mới hơn) thay vì một mảng, vì đó đi kèm với insertWith', trong đó lực lượng kết quả của hàm kết hợp về sử dụng. Mã này có thể ví dụ được

import qualified Data.Map as M -- or Data.IntMap 
import Data.List (foldl') 

histo :: M.Map Int (Int,[Int]) -- M.IntMap (Int,[Int]) 
histo = foldl' upd M.empty [(0,n) | n <- [0 .. 15000000]] 
    where 
    upd mp (i,n) = M.insertWith' add i (1,[n]) mp 
    add (j,val:_) (k,vals) = k `seq` vals `seq` (k+j,val:vals) 
    add _ pr = pr -- to avoid non-exhaustive pattern warning 

Nhược điểm của việc sử dụng một Map là

• chức năng kết hợp phải có loại a -> a -> a, vì vậy nó cần phải được phức tạp hơn một chút trong trường hợp của bạn.
• bản cập nhật là O (kích thước nhật ký) thay vì O (1), vì vậy đối với các biểu đồ lớn, nó sẽ chậm hơn đáng kể.
• Map s và IntMap s có một số chi phí lưu giữ sách, do đó sẽ sử dụng nhiều không gian hơn mảng. Nhưng nếu danh sách các cập nhật lớn so với số chỉ mục, sự khác biệt sẽ không đáng kể (chi phí là k từ cho mỗi khóa, độc lập với kích thước của các giá trị) trong trường hợp này, khi kích thước của các giá trị tăng lên với nhau cập nhật.