Pour faire suite à la réponse de Don en 2010, sur GHC 8.0.2, nous pouvons faire beaucoup mieux. Essayons d'abord sa version.
module Main (main) where
import System.CPUTime.Rdtsc (rdtsc)
import Text.Printf (printf)
import qualified Data.Vector.Unboxed as U
data Pair = Pair {-# UNPACK #-}!Int {-# UNPACK #-}!Double
mean' :: U.Vector Double -> Double
mean' xs = s/fromIntegral n
where
Pair n s = U.foldl' k (Pair 0 0) xs
k (Pair n s) x = Pair (n+1) (s+x)
main :: IO()
main = do
s <- rdtsc
let r = mean' (U.enumFromN 1 30000000)
e <- seq r rdtsc
print (e - s, r)
Cela nous donne
[nix-shell:/tmp]$ ghc -fforce-recomp -O2 MeanD.hs -o MeanD && ./MeanD +RTS -s
[1 of 1] Compiling Main (MeanD.hs, MeanD.o)
Linking MeanD ...
(372877482,1.50000005e7)
240,104,176 bytes allocated in the heap
6,832 bytes copied during GC
44,384 bytes maximum residency (1 sample(s))
25,248 bytes maximum slop
230 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 1 colls, 0 par 0.000s 0.000s 0.0000s 0.0000s
Gen 1 1 colls, 0 par 0.006s 0.006s 0.0062s 0.0062s
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.087s ( 0.087s elapsed)
GC time 0.006s ( 0.006s elapsed)
EXIT time 0.006s ( 0.006s elapsed)
Total time 0.100s ( 0.099s elapsed)
%GC time 6.2% (6.2% elapsed)
Alloc rate 2,761,447,559 bytes per MUT second
Productivity 93.8% of total user, 93.8% of total elapsed
Cependant, le code est simple: il ne devrait idéalement pas besoin de vecteur: code optimal devrait être possible de simplement inline la génération de liste. Heureusement, GHC peut le faire pour nous [0].
module Main (main) where
import System.CPUTime.Rdtsc (rdtsc)
import Text.Printf (printf)
import Data.List (foldl')
data Pair = Pair {-# UNPACK #-}!Int {-# UNPACK #-}!Double
mean' :: [Double] -> Double
mean' xs = v/fromIntegral l
where
Pair l v = foldl' f (Pair 0 0) xs
f (Pair l' v') x = Pair (l' + 1) (v' + x)
main :: IO()
main = do
s <- rdtsc
let r = mean' $ fromIntegral <$> [1 :: Int .. 30000000]
-- This is slow!
-- r = mean' [1 .. 30000000]
e <- seq r rdtsc
print (e - s, r)
Cela nous donne:
[nix-shell:/tmp]$ ghc -fforce-recomp -O2 MeanD.hs -o MeanD && ./MeanD +RTS -s
[1 of 1] Compiling Main (MeanD.hs, MeanD.o)
Linking MeanD ...
(128434754,1.50000005e7)
104,064 bytes allocated in the heap
3,480 bytes copied during GC
44,384 bytes maximum residency (1 sample(s))
17,056 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 0 colls, 0 par 0.000s 0.000s 0.0000s 0.0000s
Gen 1 1 colls, 0 par 0.000s 0.000s 0.0000s 0.0000s
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.032s ( 0.032s elapsed)
GC time 0.000s ( 0.000s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 0.033s ( 0.032s elapsed)
%GC time 0.1% (0.1% elapsed)
Alloc rate 3,244,739 bytes per MUT second
Productivity 99.8% of total user, 99.8% of total elapsed
[0]: Remarquez comment je devais carte fromIntegral: sans cela, GHC ne parvient pas à éliminer [Double] et la solution est beaucoup plus lente. C'est un peu triste: je ne comprends pas pourquoi GHC ne parvient pas à intégrer/décide qu'il n'a pas besoin de cela sans cela. Si vous avez une véritable collection de fractions, alors ce hack ne fonctionnera pas pour vous et le vecteur peut toujours être nécessaire.
Il est bon de garder à l'esprit que toute solution à ce problème qui équivaut à une division simple produira NaN pour la liste vide. Pas nécessairement un problème, juste quelque chose que je pensais mériter d'être noté. – Chuck
duplication possible de [La paresse et la récursivité queue dans Haskell, pourquoi est-ce s'écraser?] (Http://stackoverflow.com/questions/1618838/laziness-and-tail-recursion-in-haskell-why-is-this-crashing) –
Duplicata de http://stackoverflow.com/questions/1618838/laziness-and-tail-recursion-in-haskell-why-is-this-crashing/1618864#1618864 –