Tổng quát hơn parfoldr hơn

Question

Mục tiêu của tôi là có chức năng gấp nếp song song. Lúc đầu, có vẻ như khá thẳng về phía trước để đạt được và đây là những gì tôi đã nghĩ:

Đầu tiên chia danh sách đầu vào thành các phân vùng dựa trên số lượng lõi (numCapabilities). Sau đó áp dụng foldr cho mỗi phân vùng, trong đó sẽ dẫn đến một danh sách các giá trị gấp cho mỗi phân vùng. Sau đó, hãy thực hiện lại một lần nữa trong danh sách đó để có được giá trị cuối cùng .

listChunkSize = numCapabilities 

    chunk n [] = [] 
    chunk n xs = ys : chunk n zs 
     where (ys,zs) = splitAt n xs 

    parfoldr f z [] = z 
    parfoldr f z xs = res 
     where 
      parts = chunk listChunkSize xs 
      partsRs = map (foldr f z) parts `using` parList rdeepseq 
      res = foldr f z partsRs 

Đoạn mã trên không hoạt động bởi vì rõ ràng định nghĩa của foldr, (a -> b -> b) -> b -> [a] -> b, ngụ ý rằng danh sách đầu vào loại là (tốt, có thể) khác với ắc và kết quả loại.

Ví dụ,

1) foldr (+) 0 [1..10] => danh sách type = ắc loại (Integer)

2) foldr (\i acc -> (i>5) && acc) True [1..10] => danh sách loại (Integer)! = loại ắc (Bool)

Vì vậy, nhìn vào mã của tôi ở trên, bản đồ sẽ tạo ra một danh sách các loại b mà sau đó được thông qua như là đối số cho foldr thứ hai. Nhưng lần thứ hai foldr chấp nhận danh sách loại a. Vì vậy, điều đó sẽ không hoạt động.

Giải pháp xấu xí là cung cấp chữ ký loại khác cho thư mục, ví dụ: parfoldr :: (NFData a) => (a -> a -> a) -> a -> [a] -> a

Điều này sẽ hoạt động nhưng sau đó nó không chính xác tương đương với foldr. Ví dụ 1 ở trên sẽ làm tốt, nhưng không phải ví dụ 2. Vì vậy, câu hỏi 1 là: làm thế nào để xác định parfoldr để có cùng một chữ ký như foldr?

So sánh 2 nếp gấp:

input = [1..1000000] 
    seqfold = foldr (+) 0 
    parfold = parfoldr (+) 0 

tôi nhận được foll. lần trên một máy lõi kép: (không cờ -threaded)

$ ./test 
    seqfold: 4.99s 
    parfold: 25.16s 

(cờ -threaded trên)

$ ./test 
    seqfold: 5.32s 
    parfold: 25.55s 
    $ ./test +RTS -N1 
    seqfold: 5.32s 
    parfold: 25.53s 
    $ ./test +RTS -N2 
    seqfold: 3.48s 
    parfold: 3.68s 
    $ ./test +RTS -N3 
    seqfold: 3.57s 
    parfold: 2.36s 
    $ ./test +RTS -N4 
    seqfold: 3.03s 
    parfold: 1.70s 

Quan sát từ các phép đo:

• foldr dường như cung cấp thời gian chạy thấp hơn khi số lõi được tăng lên. tại sao vậy?

• parfold cho runtimes tốt hơn cho N => 3.

Mọi góp ý và ý tưởng để cải thiện được đánh giá cao :)

Answer 1

foldr không nói chung song song, vì giao diện của nó cho phép phụ thuộc tuần tự. Để có thể sắp xếp lại các tính toán theo cách bạn mô tả, bạn sẽ cần phải giới hạn mình với các toán tử kết hợp với một phần tử nhận dạng. Điều này được gọi là monoid và những gì bạn đã triển khai thực chất là một song song mconcat.

Answer 2

Bạn có thể không, không chính xác, bởi vì bạn phải phụ thuộc vào tài sản mà bạn có thể chia nhỏ khối. Điều này có nghĩa là, tất nhiên, bạn phải thêm hạn chế loại bổ sung ...Trường hợp đặc biệt là nếu bạn có f :: a -> a -> a làm hàm tích lũy của mình và f là kết hợp.

Do đó, bạn sẽ phải cung cấp hai chức năng, một chức năng được sử dụng trong các khối, và một được sử dụng để gấp các kết quả đoạn. Phiên bản gốc của bạn sẽ chỉ là một tham gia vào chức năng này.

parfoldr :: NFData a => (a -> a -> a) -> a -> [a] -> a 
parfoldr f = join $ parfoldr' f f 

parfoldr' :: NFData b => (a -> b -> b) -> (b -> c -> c) -> b -> c -> [a] -> c 
parfoldr' f g y z [] = z 
parfoldr' f g y z xs = foldr g z partsRs 
    where parts = chunk listChunkSize xs 
     partsRs = map (foldr f y) parts `using` parList rdeepseq 

Ví dụ 2 sau đó sẽ là

parfoldr' (\i acc -> (i>5) && acc) (&&) True True [1..10] 

Tất cả trong tất cả, đây không phải rằng xấu xí hơn nhiều.