-- | Simple statistics code. module ParkBench.Statistics ( Timed (..), Estimate (..), initialEstimate, updateEstimate, stdev, variance, goodness, Roll (..), ) where import ParkBench.Prelude -- | A value that took a certan time to compute. data Timed a = Timed { Timed a -> Rational nanoseconds :: {-# UNPACK #-} !Rational, Timed a -> a value :: !a } deriving stock (a -> Timed b -> Timed a (a -> b) -> Timed a -> Timed b (forall a b. (a -> b) -> Timed a -> Timed b) -> (forall a b. a -> Timed b -> Timed a) -> Functor Timed forall a b. a -> Timed b -> Timed a forall a b. (a -> b) -> Timed a -> Timed b forall (f :: * -> *). (forall a b. (a -> b) -> f a -> f b) -> (forall a b. a -> f b -> f a) -> Functor f <$ :: a -> Timed b -> Timed a $c<$ :: forall a b. a -> Timed b -> Timed a fmap :: (a -> b) -> Timed a -> Timed b $cfmap :: forall a b. (a -> b) -> Timed a -> Timed b Functor, Int -> Timed a -> ShowS [Timed a] -> ShowS Timed a -> String (Int -> Timed a -> ShowS) -> (Timed a -> String) -> ([Timed a] -> ShowS) -> Show (Timed a) forall a. Show a => Int -> Timed a -> ShowS forall a. Show a => [Timed a] -> ShowS forall a. Show a => Timed a -> String forall a. (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a showList :: [Timed a] -> ShowS $cshowList :: forall a. Show a => [Timed a] -> ShowS show :: Timed a -> String $cshow :: forall a. Show a => Timed a -> String showsPrec :: Int -> Timed a -> ShowS $cshowsPrec :: forall a. Show a => Int -> Timed a -> ShowS Show) instance Monoid a => Monoid (Timed a) where mempty :: Timed a mempty = Rational -> a -> Timed a forall a. Rational -> a -> Timed a Timed Rational 0 a forall a. Monoid a => a mempty mappend :: Timed a -> Timed a -> Timed a mappend = Timed a -> Timed a -> Timed a forall a. Semigroup a => a -> a -> a (<>) instance Semigroup a => Semigroup (Timed a) where Timed Rational n0 a x0 <> :: Timed a -> Timed a -> Timed a <> Timed Rational n1 a x1 = Rational -> a -> Timed a forall a. Rational -> a -> Timed a Timed (Rational n0 Rational -> Rational -> Rational forall a. Num a => a -> a -> a + Rational n1) (a x0 a -> a -> a forall a. Semigroup a => a -> a -> a <> a x1) data Estimate a = Estimate { Estimate a -> Rational kvariance :: {-# UNPACK #-} !Rational, Estimate a -> Timed a mean :: {-# UNPACK #-} !(Timed a), Estimate a -> Word64 samples :: {-# UNPACK #-} !Word64 } deriving stock (a -> Estimate b -> Estimate a (a -> b) -> Estimate a -> Estimate b (forall a b. (a -> b) -> Estimate a -> Estimate b) -> (forall a b. a -> Estimate b -> Estimate a) -> Functor Estimate forall a b. a -> Estimate b -> Estimate a forall a b. (a -> b) -> Estimate a -> Estimate b forall (f :: * -> *). (forall a b. (a -> b) -> f a -> f b) -> (forall a b. a -> f b -> f a) -> Functor f <$ :: a -> Estimate b -> Estimate a $c<$ :: forall a b. a -> Estimate b -> Estimate a fmap :: (a -> b) -> Estimate a -> Estimate b $cfmap :: forall a b. (a -> b) -> Estimate a -> Estimate b Functor, Int -> Estimate a -> ShowS [Estimate a] -> ShowS Estimate a -> String (Int -> Estimate a -> ShowS) -> (Estimate a -> String) -> ([Estimate a] -> ShowS) -> Show (Estimate a) forall a. Show a => Int -> Estimate a -> ShowS forall a. Show a => [Estimate a] -> ShowS forall a. Show a => Estimate a -> String forall a. (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a showList :: [Estimate a] -> ShowS $cshowList :: forall a. Show a => [Estimate a] -> ShowS show :: Estimate a -> String $cshow :: forall a. Show a => Estimate a -> String showsPrec :: Int -> Estimate a -> ShowS $cshowsPrec :: forall a. Show a => Int -> Estimate a -> ShowS Show) stdev :: Estimate a -> Double stdev :: Estimate a -> Double stdev = Double -> Double forall a. Floating a => a -> a sqrt (Double -> Double) -> (Estimate a -> Double) -> Estimate a -> Double forall b c a. (b -> c) -> (a -> b) -> a -> c . (Fractional Double => Rational -> Double forall a. Fractional a => Rational -> a fromRational @Double) (Rational -> Double) -> (Estimate a -> Rational) -> Estimate a -> Double forall b c a. (b -> c) -> (a -> b) -> a -> c . Estimate a -> Rational forall a. Estimate a -> Rational variance variance :: Estimate a -> Rational variance :: Estimate a -> Rational variance (Estimate Rational kvariance Timed a _ Word64 samples) = if Word64 samples Word64 -> Word64 -> Bool forall a. Eq a => a -> a -> Bool == Word64 1 then Rational 0 else Rational kvariance Rational -> Rational -> Rational forall a. Fractional a => a -> a -> a / Word64 -> Rational w2r (Word64 samples Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - Word64 1) -- | The "goodness" of an estimate, which is just how large its standard deviation is, relative to its mean. -- -- Smaller is better, and the smallest possible value is 0. goodness :: Estimate a -> Double goodness :: Estimate a -> Double goodness Estimate a e = Estimate a -> Double forall a. Estimate a -> Double stdev Estimate a e Double -> Double -> Double forall a. Fractional a => a -> a -> a / Rational -> Double r2d (Timed a -> Rational forall a. Timed a -> Rational nanoseconds (Estimate a -> Timed a forall a. Estimate a -> Timed a mean Estimate a e)) -- | @initialEstimate v@ creates an estimate per thing-that-took-time @v@ that was a run of 1 iteration. initialEstimate :: Timed a -> Estimate a initialEstimate :: Timed a -> Estimate a initialEstimate Timed a mean = Estimate :: forall a. Rational -> Timed a -> Word64 -> Estimate a Estimate { $sel:kvariance:Estimate :: Rational kvariance = Rational 0, Timed a mean :: Timed a $sel:mean:Estimate :: Timed a mean, $sel:samples:Estimate :: Word64 samples = Word64 1 } -- | @updateEstimate n v e@ updates estimate @e@ per thing-that-took-time @v@ that was a run of @n@ iterations. updateEstimate :: Roll a => Word64 -> Timed a -> Estimate a -> Estimate a updateEstimate :: Word64 -> Timed a -> Estimate a -> Estimate a updateEstimate Word64 n (Timed Rational tn a value1) (Estimate Rational kvariance (Timed Rational mean a value0) Word64 samples) = Rational -> Timed a -> Word64 -> Estimate a forall a. Rational -> Timed a -> Word64 -> Estimate a Estimate Rational kvariance' (Rational -> a -> Timed a forall a. Rational -> a -> Timed a Timed Rational mean' a value') Word64 samples' where kvariance' :: Rational kvariance' = Rational kvariance Rational -> Rational -> Rational forall a. Num a => a -> a -> a + Rational nr Rational -> Rational -> Rational forall a. Num a => a -> a -> a * (Rational t1 Rational -> Rational -> Rational forall a. Num a => a -> a -> a - Rational mean) Rational -> Rational -> Rational forall a. Num a => a -> a -> a * (Rational t1 Rational -> Rational -> Rational forall a. Num a => a -> a -> a - Rational mean') mean' :: Rational mean' = Rational -> Rational -> Rational rollmean Rational mean Rational tn samples' :: Word64 samples' = Word64 samples Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a + Word64 n samplesr' :: Rational samplesr' = Word64 -> Rational w2r Word64 samples' t1 :: Rational t1 = Rational tn Rational -> Rational -> Rational forall a. Fractional a => a -> a -> a / Rational nr value' :: a value' = (Rational -> Rational -> Rational) -> a -> a -> a forall a. Roll a => (Rational -> Rational -> Rational) -> a -> a -> a roll Rational -> Rational -> Rational rollmean a value0 a value1 rollmean :: Rational -> Rational -> Rational rollmean Rational u0 Rational u1 = Rational u0 Rational -> Rational -> Rational forall a. Num a => a -> a -> a + ((Rational u1 Rational -> Rational -> Rational forall a. Num a => a -> a -> a - Rational nr Rational -> Rational -> Rational forall a. Num a => a -> a -> a * Rational u0) Rational -> Rational -> Rational forall a. Fractional a => a -> a -> a / Rational samplesr') nr :: Rational nr = Word64 -> Rational w2r Word64 n class Roll a where roll :: (Rational -> Rational -> Rational) -> a -> a -> a