5

以下のコードでは、Bucket Sort の実装をベンチマークしています。

このbucketsort関数は からの結果を使用します_bucketsortが、単一のリストにフラット化します。驚いたことに、このプロセス ( Map.toList) にはかなりの時間がかかります。

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])]

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

私のbucketsort関数がより良く、できればより速く記述できたとしても、私は驚かないでしょう。しかし、今のところ、私はその方法を理解していません。

また、Haskell コードの改善やコメントは大歓迎です。

4

1 に答える 1

6

2 番目のベンチマークでは完全には適用_bucketsortされていないため、部分的に適用された関数を WHNF に評価しているだけですが、これは当然のことながら非常に高速です。

関連する行を次のように変更します

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

利回り（私のマシン上）：

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

whnfさらに、リストではトップレベルのコンストラクターのみが評価されるため、このベンチマークはリストを完全に強制しているわけではないことに注意してください。これは、現在両方のベンチマークのパフォーマンスがほぼ同じである理由を説明しています。両方のベンチマークを切り替えるnfと、時間がそれぞれ 369.3022ms と 354.3513ms に変わり、bucketsort再びやや遅くなります。

于 2013-03-06T11:31:49.930 に答える