Hiệu suất Map.toList trong Haskell

Question

Trong mã bên dưới, tôi đang đo điểm chuẩn thực hiện Sắp xếp nhóm.

Chức năng bucketsort sử dụng kết quả từ _bucketsort nhưng san phẳng nó thành một danh sách duy nhất. Để tôi ngạc nhiên quá trình này (Map.toList) mất rất nhiều thời gian.

module Main where 
import System.Random 
import Criterion.Main 
import qualified Data.List as List 
import qualified Data.Map as Map 
import Data.Maybe 

insert :: (Ord a) => a -> [a] -> [a] 
insert x [] = [x] 
insert x (y:xs) 
    | x <= y = x:y:xs 
    | otherwise = y : insert x xs 

bucketsort :: (Integral a) => [a] -> [a] 
bucketsort xs = List.concatMap (snd) . Map.toList $ _bucketsort xs Map.empty 

_bucketsort :: (Integral k) => [k] -> Map.Map k [k] -> Map.Map k [k] 
_bucketsort [] map = map 
_bucketsort (x:xs) map = 
    let bucket = x `div` 3 
     bucketlist = maybeToList $ Map.lookup bucket map 
     bucketInsert x [] = [x] 
     bucketInsert x xs = insert x $ head xs 
     ys = bucketInsert x bucketlist 
     newMap = Map.insert bucket ys map 
    in _bucketsort xs newMap 

dataset n = List.take n $ randomRs (0, 9999) (mkStdGen 42) 

main = defaultMain [ bench "bucketsort 96080" $ whnf bucketsort ((dataset 96080) :: [Int]) 
        , bench "_bucketsort 96080" $ whnf _bucketsort ((dataset 96080):: [Int])] 

Và đây là kết quả của sự chuẩn bởi Criterion:

C:\>benchmark_bucketsort.exe 
warming up 
estimating clock resolution... 
mean is 1.353299 us (640001 iterations) 
found 1278266 outliers among 639999 samples (199.7%) 
    638267 (99.7%) low severe 
    639999 (100.0%) high severe 
estimating cost of a clock call... 
mean is 105.8728 ns (8 iterations) 
found 14 outliers among 8 samples (175.0%) 
    7 (87.5%) low severe 
    7 (87.5%) high severe 

benchmarking bucketsort 96080 
collecting 100 samples, 1 iterations each, in estimated 24.35308 s 
Warning: Couldn't open /dev/urandom 
Warning: using system clock for seed instead (quality will be lower) 
mean: 187.2037 ms, lb 182.7181 ms, ub 191.3842 ms, ci 0.950 
std dev: 22.15054 ms, lb 19.47241 ms, ub 25.64983 ms, ci 0.950 
variance introduced by outliers: 84.194% 
variance is severely inflated by outliers 

benchmarking _bucketsort 96080 
mean: 8.823789 ns, lb 8.654692 ns, ub 9.049314 ns, ci 0.950 
std dev: 952.9240 ps, lb 723.0241 ps, ub 1.154097 ns, ci 0.950 
found 13 outliers among 100 samples (13.0%) 
    13 (13.0%) high severe 
variance introduced by outliers: 82.077% 
variance is severely inflated by outliers 

Tôi sẽ không ngạc nhiên nếu chức năng bucketsort của tôi có thể được viết tốt hơn rất nhiều và hy vọng nhanh hơn. Nhưng tôi chưa tìm ra cách nào.

Ngoài ra, mọi cải tiến/nhận xét trên mã Haskell của tôi đều được hoan nghênh.

Answer 1

Bạn không áp dụng đầy đủ _bucketsort trong điểm chuẩn thứ hai của mình và do đó chỉ đánh giá hàm được áp dụng một phần cho WHNF, điều không ngạc nhiên là khá nhanh.

Thay đổi dòng liên quan đến

main = defaultMain [ bench "bucketsort 96080" $ whnf bucketsort ((dataset 96080) :: [Int]) 
        , bench "_bucketsort 96080" $ whnf (flip _bucketsort Map.empty) ((dataset 96080):: [Int])] 

năng suất (trên máy tính của tôi):

warming up 
estimating clock resolution... 
mean is 2.357120 us (320001 iterations) 
found 2630 outliers among 319999 samples (0.8%) 
    2427 (0.8%) high severe 
estimating cost of a clock call... 
mean is 666.7750 ns (14 iterations) 
found 1 outliers among 14 samples (7.1%) 
    1 (7.1%) high severe 

benchmarking bucketsort 96080 
collecting 100 samples, 1 iterations each, in estimated 34.66980 s 
mean: 244.3280 ms, lb 238.0601 ms, ub 250.6725 ms, ci 0.950 
std dev: 32.37658 ms, lb 28.02356 ms, ub 38.10187 ms, ci 0.950 
found 3 outliers among 100 samples (3.0%) 
    3 (3.0%) low mild 
variance introduced by outliers: 87.311% 
variance is severely inflated by outliers 

benchmarking _bucketsort 96080 
collecting 100 samples, 1 iterations each, in estimated 24.65911 s 
mean: 244.9425 ms, lb 239.1011 ms, ub 251.0300 ms, ci 0.950 
std dev: 30.68877 ms, lb 26.48151 ms, ub 36.20961 ms, ci 0.950 
variance introduced by outliers: 86.247% 
variance is severely inflated by outliers 

Chú ý hơn nữa mà chuẩn này không được buộc đầy đủ danh sách, vì whnf trên một danh sách sẽ chỉ đánh giá hàm tạo đầu tiên. Điều này giải thích lý do tại sao cả hai điểm chuẩn có hiệu suất gần như giống nhau ngay bây giờ. Chuyển cả hai điểm chuẩn thành nf thay đổi thời gian thành 369,3022ms và 354,351ms, tương ứng, làm cho bucketsort hơi chậm lại.