{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE OverloadedStrings #-}
{-# OPTIONS_GHC -Wall #-}

-- | Order of complexity calculations.
--
-- <https://en.wikibooks.org/wiki/Optimizing_Code_for_Speed/Order_of_Complexity_Optimizations#:~:text=of%2DComplexity%20Reduction-,What%20is%20order%20of%20complexity%3F,*log(N))%20etc What is Order of Complexity> .
--
-- <https://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-working-at-a-high-altitude-for-low-level-performance/ donsbot blog>
--
-- <https://www.fpcomplete.com/haskell/tutorial/profiling/ profiling>
--
-- <https://www.reddit.com/r/haskell/comments/nl0rkl/looking_for_good_rules_of_thumbs_on_what_haskell/ rules of thumb>
module Perf.BigO
  ( O (..),
    olist,
    promote,
    promote1,
    promote_,
    demote,
    demote1,
    spectrum,
    Order (..),
    bigO,
    runtime,
    BigOrder (..),
    fromOrder,
    toOrder,
    order,
    mcurve,
    dcurve,
    tcurve,
    diffs,
    bestO,
    estO,
    estOs,
    estOrder,
  )
where

import Data.Bool
import qualified Data.List as List
import qualified Data.Map.Strict as Map
import Data.Maybe
import Data.Monoid
import qualified Data.Vector as V
import GHC.Generics
import Perf.Stats
import Perf.Time
import Perf.Types
import Prelude

-- $setup
-- >>> import qualified Data.List as List
-- >>> o = Order [0.0,1.0,100.0,0.0,0.0,0.0,0.0,0.0]
-- >>> ms = [2805.0,3476.0,9989.0,92590.0,1029074.6947660954]
-- >>> ns = [1,10,100,1000,10000]

-- | order type
data O
  = -- | cubic
    N3
  | -- | quadratic
    N2
  | -- | ^3/2
    N32
  | -- | N * log N
    NLogN
  | -- | linear
    N1
  | -- | sqrt N
    N12
  | -- | log N
    LogN
  | -- | constant
    N0
  deriving (O -> O -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: O -> O -> Bool
$c/= :: O -> O -> Bool
== :: O -> O -> Bool
$c== :: O -> O -> Bool
Eq, Eq O
O -> O -> Bool
O -> O -> Ordering
O -> O -> O
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: O -> O -> O
$cmin :: O -> O -> O
max :: O -> O -> O
$cmax :: O -> O -> O
>= :: O -> O -> Bool
$c>= :: O -> O -> Bool
> :: O -> O -> Bool
$c> :: O -> O -> Bool
<= :: O -> O -> Bool
$c<= :: O -> O -> Bool
< :: O -> O -> Bool
$c< :: O -> O -> Bool
compare :: O -> O -> Ordering
$ccompare :: O -> O -> Ordering
Ord, Int -> O -> ShowS
[O] -> ShowS
O -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [O] -> ShowS
$cshowList :: [O] -> ShowS
show :: O -> String
$cshow :: O -> String
showsPrec :: Int -> O -> ShowS
$cshowsPrec :: Int -> O -> ShowS
Show, forall x. Rep O x -> O
forall x. O -> Rep O x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cto :: forall x. Rep O x -> O
$cfrom :: forall x. O -> Rep O x
Generic, Int -> O
O -> Int
O -> [O]
O -> O
O -> O -> [O]
O -> O -> O -> [O]
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
enumFromThenTo :: O -> O -> O -> [O]
$cenumFromThenTo :: O -> O -> O -> [O]
enumFromTo :: O -> O -> [O]
$cenumFromTo :: O -> O -> [O]
enumFromThen :: O -> O -> [O]
$cenumFromThen :: O -> O -> [O]
enumFrom :: O -> [O]
$cenumFrom :: O -> [O]
fromEnum :: O -> Int
$cfromEnum :: O -> Int
toEnum :: Int -> O
$ctoEnum :: Int -> O
pred :: O -> O
$cpred :: O -> O
succ :: O -> O
$csucc :: O -> O
Enum)

-- | enumeration of O types
--
-- >>> olist
-- [N3,N2,N32,NLogN,N1,N12,LogN,N0]
olist :: [O]
olist :: [O]
olist = [O
N3 .. O
N0]

-- | functions to compute performance measure
--
-- >>> fmap ($ 0) promote_
-- [0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0]
--
-- >>> fmap ($ 1) promote_
-- [1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0]
--
-- Ordering makes sense around N=10
--
-- >>> fmap ($ 10) promote_
-- [1000.0,100.0,31.622776601683793,23.02585092994046,10.0,3.1622776601683795,2.302585092994046,1.0]
--
-- Having NP may cause big num problems
--
-- >>> fmap ($ 1000) promote_
-- [1.0e9,1000000.0,31622.776601683792,6907.755278982137,1000.0,31.622776601683793,6.907755278982137,1.0]
promote_ :: [Double -> Double]
promote_ :: [Double -> Double]
promote_ =
  [ -- \n -> min maxBound (bool (2**n) zero (n<=zero)),
    (forall a b. (Num a, Integral b) => a -> b -> a
^ (Integer
3 :: Integer)),
    (forall a b. (Num a, Integral b) => a -> b -> a
^ (Integer
2 :: Integer)),
    (forall a. Floating a => a -> a -> a
** Double
1.5),
    \Double
n -> forall a. a -> a -> Bool -> a
bool (forall a. a -> a -> Bool -> a
bool (Double
n forall a. Num a => a -> a -> a
* forall a. Floating a => a -> a
log Double
n) Double
1 (Double
n forall a. Ord a => a -> a -> Bool
<= Double
1)) Double
0 (Double
n forall a. Ord a => a -> a -> Bool
<= Double
0),
    forall a. a -> a
id,
    (forall a. Floating a => a -> a -> a
** Double
0.5),
    \Double
n -> forall a. a -> a -> Bool -> a
bool (forall a. a -> a -> Bool -> a
bool (forall a. Floating a => a -> a
log Double
n) Double
1 (Double
n forall a. Ord a => a -> a -> Bool
<= Double
1)) Double
0 (Double
n forall a. Ord a => a -> a -> Bool
<= Double
0),
    \Double
n -> forall a. a -> a -> Bool -> a
bool Double
1 Double
0 (Double
n forall a. Ord a => a -> a -> Bool
<= Double
0)
  ]

-- | a set of factors for each order, which represents a full Order specification.
newtype Order a = Order {forall a. Order a -> [a]
factors :: [a]} deriving (Order a -> Order a -> Bool
forall a. Eq a => Order a -> Order a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Order a -> Order a -> Bool
$c/= :: forall a. Eq a => Order a -> Order a -> Bool
== :: Order a -> Order a -> Bool
$c== :: forall a. Eq a => Order a -> Order a -> Bool
Eq, Order a -> Order a -> Bool
Order a -> Order a -> Ordering
Order a -> Order a -> Order a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall {a}. Ord a => Eq (Order a)
forall a. Ord a => Order a -> Order a -> Bool
forall a. Ord a => Order a -> Order a -> Ordering
forall a. Ord a => Order a -> Order a -> Order a
min :: Order a -> Order a -> Order a
$cmin :: forall a. Ord a => Order a -> Order a -> Order a
max :: Order a -> Order a -> Order a
$cmax :: forall a. Ord a => Order a -> Order a -> Order a
>= :: Order a -> Order a -> Bool
$c>= :: forall a. Ord a => Order a -> Order a -> Bool
> :: Order a -> Order a -> Bool
$c> :: forall a. Ord a => Order a -> Order a -> Bool
<= :: Order a -> Order a -> Bool
$c<= :: forall a. Ord a => Order a -> Order a -> Bool
< :: Order a -> Order a -> Bool
$c< :: forall a. Ord a => Order a -> Order a -> Bool
compare :: Order a -> Order a -> Ordering
$ccompare :: forall a. Ord a => Order a -> Order a -> Ordering
Ord, Int -> Order a -> ShowS
forall a. Show a => Int -> Order a -> ShowS
forall a. Show a => [Order a] -> ShowS
forall a. Show a => Order a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Order a] -> ShowS
$cshowList :: forall a. Show a => [Order a] -> ShowS
show :: Order a -> String
$cshow :: forall a. Show a => Order a -> String
showsPrec :: Int -> Order a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Order a -> ShowS
Show, forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (Order a) x -> Order a
forall a x. Order a -> Rep (Order a) x
$cto :: forall a x. Rep (Order a) x -> Order a
$cfrom :: forall a x. Order a -> Rep (Order a) x
Generic, forall a b. a -> Order b -> Order a
forall a b. (a -> b) -> Order a -> Order b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> Order b -> Order a
$c<$ :: forall a b. a -> Order b -> Order a
fmap :: forall a b. (a -> b) -> Order a -> Order b
$cfmap :: forall a b. (a -> b) -> Order a -> Order b
Functor)

-- | create an Order
--
-- >>> order N2 1
-- Order {factors = [0,1,0,0,0,0,0,0]}
order :: (Num a) => O -> a -> Order a
order :: forall a. Num a => O -> a -> Order a
order O
o a
a = forall a. [a] -> Order a
Order forall a b. (a -> b) -> a -> b
$ forall a. Int -> a -> [a]
replicate Int
n a
0 forall a. Semigroup a => a -> a -> a
<> [a
a] forall a. Semigroup a => a -> a -> a
<> forall a. Int -> a -> [a]
replicate (Int
7 forall a. Num a => a -> a -> a
- Int
n) a
0
  where
    n :: Int
n = forall a. Enum a => a -> Int
fromEnum O
o

-- | Calculate the expected performance measure
--
-- >>> promote (order N2 1) 10
-- 100.0
promote :: Order Double -> Double -> Double
promote :: Order Double -> Double -> Double
promote (Order [Double]
fs) Double
n = forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum (forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith forall a. Num a => a -> a -> a
(*) [Double]
fs ((forall a b. (a -> b) -> a -> b
$ Double
n) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Double -> Double]
promote_))

-- | Calculate the expected performance measure per n
--
-- >>> promote (order N2 1) 10
-- 100.0
promote1 :: Order Double -> Double
promote1 :: Order Double -> Double
promote1 Order Double
o = Order Double -> Double -> Double
promote Order Double
o Double
1

-- | Calculate an Order from a given O, an n, and a total performance measurement
--
-- A measurement of 1e6 for n=1000 with an order of N2 is:
--
-- >>> demote N2 1000 1000000
-- Order {factors = [0.0,1.0,0.0,0.0,0.0,0.0,0.0,0.0]}
--
-- > promote (demote N2 n m) n m == m
demote :: O -> Double -> Double -> Order Double
demote :: O -> Double -> Double -> Order Double
demote O
o Double
n Double
m = forall a. Num a => O -> a -> Order a
order O
o (Double
m forall a. Fractional a => a -> a -> a
/ ([Double -> Double]
promote_ forall a. [a] -> Int -> a
List.!! forall a. Enum a => a -> Int
fromEnum O
o) Double
n)

-- | Calculate an Order from a measure, and an O
--
-- >>> demote1 N2 1000
-- Order {factors = [0.0,1000.0,0.0,0.0,0.0,0.0,0.0,0.0]}
--
-- > demote1 N2 m == demote o 1 m
demote1 :: O -> Double -> Order Double
demote1 :: O -> Double -> Order Double
demote1 O
o Double
m = O -> Double -> Double -> Order Double
demote O
o Double
1 Double
m

-- | find the dominant order, and it's factor
--
-- >>> bigO o
-- (N2,1.0)
bigO :: (Ord a, Num a) => Order a -> (O, a)
bigO :: forall a. (Ord a, Num a) => Order a -> (O, a)
bigO (Order [a]
os) = (forall a. Enum a => Int -> a
toEnum Int
b, [a]
os forall a. [a] -> Int -> a
List.!! Int
b)
  where
    b :: Int
b = forall a. a -> Maybe a -> a
fromMaybe Int
7 forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> Maybe Int
List.findIndex (forall a. Ord a => a -> a -> Bool
> a
0) [a]
os

-- | compute the runtime component of an Order, defined as the
-- difference between the dominant order and the total for a single run.
--
-- >>> runtime o
-- 100.0
runtime :: Order Double -> Double
runtime :: Order Double -> Double
runtime (Order [Double]
os) = Order Double -> Double -> Double
promote (forall a. [a] -> Order a
Order [Double]
r) Double
1
  where
    b :: Int
b = forall a. a -> Maybe a -> a
fromMaybe Int
7 forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> Maybe Int
List.findIndex (forall a. Ord a => a -> a -> Bool
> Double
0) [Double]
os
    r :: [Double]
r = forall a. Int -> [a] -> [a]
take Int
b [Double]
os forall a. Semigroup a => a -> a -> a
<> [Double
0] forall a. Semigroup a => a -> a -> a
<> forall a. Int -> [a] -> [a]
drop (Int
b forall a. Num a => a -> a -> a
+ Int
1) [Double]
os

instance (Num a) => Num (Order a) where
  -- 0 = Order $ replicate 9 0
  + :: Order a -> Order a -> Order a
(+) (Order [a]
o) (Order [a]
o') =
    forall a. [a] -> Order a
Order (forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith forall a. Num a => a -> a -> a
(+) [a]
o [a]
o')
  negate :: Order a -> Order a
negate (Order [a]
o) = forall a. [a] -> Order a
Order forall a b. (a -> b) -> a -> b
$ forall a. Num a => a -> a
negate forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a]
o
  * :: Order a -> Order a -> Order a
(*) (Order [a]
o) (Order [a]
o') =
    forall a. [a] -> Order a
Order (forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith forall a. Num a => a -> a -> a
(*) [a]
o [a]
o')
  abs :: Order a -> Order a
abs = forall a. HasCallStack => a
undefined
  signum :: Order a -> Order a
signum = forall a. HasCallStack => a
undefined
  fromInteger :: Integer -> Order a
fromInteger Integer
x = forall a. [a] -> Order a
Order forall a b. (a -> b) -> a -> b
$ forall a. Int -> a -> [a]
replicate Int
9 (forall a. Num a => Integer -> a
fromInteger Integer
x)

-- | A set of factors consisting of the dominant order, the dominant order factor and a constant factor
data BigOrder a = BigOrder {forall a. BigOrder a -> O
bigOrder :: O, forall a. BigOrder a -> a
bigFactor :: a, forall a. BigOrder a -> a
bigConstant :: a} deriving (BigOrder a -> BigOrder a -> Bool
forall a. Eq a => BigOrder a -> BigOrder a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: BigOrder a -> BigOrder a -> Bool
$c/= :: forall a. Eq a => BigOrder a -> BigOrder a -> Bool
== :: BigOrder a -> BigOrder a -> Bool
$c== :: forall a. Eq a => BigOrder a -> BigOrder a -> Bool
Eq, BigOrder a -> BigOrder a -> Bool
BigOrder a -> BigOrder a -> Ordering
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall {a}. Ord a => Eq (BigOrder a)
forall a. Ord a => BigOrder a -> BigOrder a -> Bool
forall a. Ord a => BigOrder a -> BigOrder a -> Ordering
forall a. Ord a => BigOrder a -> BigOrder a -> BigOrder a
min :: BigOrder a -> BigOrder a -> BigOrder a
$cmin :: forall a. Ord a => BigOrder a -> BigOrder a -> BigOrder a
max :: BigOrder a -> BigOrder a -> BigOrder a
$cmax :: forall a. Ord a => BigOrder a -> BigOrder a -> BigOrder a
>= :: BigOrder a -> BigOrder a -> Bool
$c>= :: forall a. Ord a => BigOrder a -> BigOrder a -> Bool
> :: BigOrder a -> BigOrder a -> Bool
$c> :: forall a. Ord a => BigOrder a -> BigOrder a -> Bool
<= :: BigOrder a -> BigOrder a -> Bool
$c<= :: forall a. Ord a => BigOrder a -> BigOrder a -> Bool
< :: BigOrder a -> BigOrder a -> Bool
$c< :: forall a. Ord a => BigOrder a -> BigOrder a -> Bool
compare :: BigOrder a -> BigOrder a -> Ordering
$ccompare :: forall a. Ord a => BigOrder a -> BigOrder a -> Ordering
Ord, Int -> BigOrder a -> ShowS
forall a. Show a => Int -> BigOrder a -> ShowS
forall a. Show a => [BigOrder a] -> ShowS
forall a. Show a => BigOrder a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [BigOrder a] -> ShowS
$cshowList :: forall a. Show a => [BigOrder a] -> ShowS
show :: BigOrder a -> String
$cshow :: forall a. Show a => BigOrder a -> String
showsPrec :: Int -> BigOrder a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> BigOrder a -> ShowS
Show, forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (BigOrder a) x -> BigOrder a
forall a x. BigOrder a -> Rep (BigOrder a) x
$cto :: forall a x. Rep (BigOrder a) x -> BigOrder a
$cfrom :: forall a x. BigOrder a -> Rep (BigOrder a) x
Generic, forall a b. a -> BigOrder b -> BigOrder a
forall a b. (a -> b) -> BigOrder a -> BigOrder b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> BigOrder b -> BigOrder a
$c<$ :: forall a b. a -> BigOrder b -> BigOrder a
fmap :: forall a b. (a -> b) -> BigOrder a -> BigOrder b
$cfmap :: forall a b. (a -> b) -> BigOrder a -> BigOrder b
Functor)

-- | compute the BigOrder
--
-- >>> fromOrder o
-- BigOrder {bigOrder = N2, bigFactor = 1.0, bigConstant = 100.0}
fromOrder :: Order Double -> BigOrder Double
fromOrder :: Order Double -> BigOrder Double
fromOrder Order Double
o' = forall a. O -> a -> a -> BigOrder a
BigOrder O
o Double
f Double
r
  where
    (O
o, Double
f) = forall a. (Ord a, Num a) => Order a -> (O, a)
bigO Order Double
o'
    r :: Double
r = Order Double -> Double
runtime Order Double
o'

-- | convert a BigOrder to an Order.
--
-- toOrder . fromOrder is not a round trip iso.
--
-- >>> toOrder (fromOrder o)
-- Order {factors = [0.0,1.0,0.0,0.0,0.0,0.0,0.0,100.0]}
toOrder :: BigOrder Double -> Order Double
toOrder :: BigOrder Double -> Order Double
toOrder (BigOrder O
o Double
f Double
r) = forall a. Num a => O -> a -> Order a
order O
o Double
f forall a. Num a => a -> a -> a
+ forall a. Num a => O -> a -> Order a
order O
N0 Double
r

-- | The factor for each O given an n, and a measurement.
--
-- >>> spectrum 100 10000
-- Order {factors = [1.0e-2,1.0,10.0,21.71472409516259,100.0,1000.0,2171.4724095162587,10000.0]}
spectrum :: Double -> Double -> Order Double
spectrum :: Double -> Double -> Order Double
spectrum Double
n Double
m = forall a. [a] -> Order a
Order ((Double
m forall a. Fractional a => a -> a -> a
/) forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall a b. (a -> b) -> a -> b
$ Double
n) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Double -> Double]
promote_)

-- | The errors for a list of n's and measurements, based on the spectrum of the last measurement.
diffs :: [Double] -> [Double] -> [[Double]]
diffs :: [Double] -> [Double] -> [[Double]]
diffs [Double]
ns [Double]
ms = forall a. [[a]] -> [[a]]
List.transpose forall a b. (a -> b) -> a -> b
$ forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\Double
n Double
m -> forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\O
o' Double
f -> Double
m forall a. Num a => a -> a -> a
- Order Double -> Double -> Double
promote (forall a. Num a => O -> a -> Order a
order O
o' Double
f) Double
n) [O]
olist [Double]
fs) [Double]
ns [Double]
ms
  where
    fs :: [Double]
fs = forall a. Order a -> [a]
factors (Double -> Double -> Order Double
spectrum (forall a. [a] -> a
List.last [Double]
ns) (forall a. [a] -> a
List.last [Double]
ms))

-- | minimum error order for a list of measurements
--
-- >>> bestO ns ms
-- N1
bestO :: [Double] -> [Double] -> O
bestO :: [Double] -> [Double] -> O
bestO [Double]
ns [Double]
ms =
  forall a. Enum a => Int -> a
toEnum forall a b. (a -> b) -> a -> b
$
    forall a. Ord a => Vector a -> Int
V.minIndex forall a b. (a -> b) -> a -> b
$
      forall a. [a] -> Vector a
V.fromList
        (forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Num a => a -> a
abs) ([Double] -> [Double] -> [[Double]]
diffs [Double]
ns [Double]
ms))

-- | fit the best order for the last measurement and return it, and the error terms for the measurements
--
-- >>> estO ns ms
-- (Order {factors = [0.0,0.0,0.0,0.0,102.90746947660953,0.0,0.0,0.0]},[2702.0925305233905,2446.9253052339045,-301.7469476609531,-10317.469476609534,0.0])
estO :: [Double] -> [Double] -> (Order Double, [Double])
estO :: [Double] -> [Double] -> (Order Double, [Double])
estO [] [Double]
_ = (Order Double
0, [])
estO [Double]
ns [Double]
ms = (Order Double
lasto, [Double]
diff)
  where
    diff :: [Double]
diff = [Double] -> [Double] -> [[Double]]
diffs [Double]
ns [Double]
ms forall a. [a] -> Int -> a
List.!! forall a. Enum a => a -> Int
fromEnum O
o
    o :: O
o = [Double] -> [Double] -> O
bestO [Double]
ns [Double]
ms
    lasto :: Order Double
lasto = O -> Double -> Double -> Order Double
demote O
o (forall a. [a] -> a
List.last [Double]
ns) (forall a. [a] -> a
List.last [Double]
ms)

-- | fit orders from the last measurement to the first, using the residuals at each step.
--
-- >>> estOs ns ms
-- [Order {factors = [0.0,0.0,0.0,0.0,102.90746947660953,0.0,0.0,0.0]},Order {factors = [0.0,0.0,-0.32626703235351473,0.0,0.0,0.0,0.0,0.0]},Order {factors = [0.0,0.0,0.0,0.0,0.0,0.0,0.0,24.520084692561625]},Order {factors = [0.0,0.0,0.0,0.0,0.0,0.0,0.0,2432.722690017952]},Order {factors = [0.0,0.0,0.0,0.0,0.0,0.0,0.0,245.1760228452299]}]
estOs :: [Double] -> [Double] -> [Order Double]
estOs :: [Double] -> [Double] -> [Order Double]
estOs [Double]
ns [Double]
ms = [Order Double] -> [Double] -> [Double] -> [Order Double]
go [] [Double]
ns [Double]
ms
  where
    go :: [Order Double] -> [Double] -> [Double] -> [Order Double]
go [Order Double]
os [Double]
_ [] = [Order Double]
os
    go [Order Double]
os [Double]
_ [Double
m] = [Order Double]
os forall a. Semigroup a => a -> a -> a
<> [forall a. Num a => O -> a -> Order a
order O
N0 Double
m]
    go [Order Double]
os [Double]
ns' [Double]
ms' = let (Order Double
o', [Double]
res) = [Double] -> [Double] -> (Order Double, [Double])
estO [Double]
ns' [Double]
ms' in [Order Double] -> [Double] -> [Double] -> [Order Double]
go ([Order Double]
os forall a. Semigroup a => a -> a -> a
<> [Order Double
o']) (forall a. [a] -> [a]
List.init [Double]
ns') (forall a. [a] -> [a]
List.init [Double]
res)

-- | performance curve for a Measure.
mcurve :: (Semigroup a) => Measure IO a -> (Int -> b) -> [Int] -> IO [a]
mcurve :: forall a b.
Semigroup a =>
Measure IO a -> (Int -> b) -> [Int] -> IO [a]
mcurve Measure IO a
m Int -> b
f [Int]
ns = forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM (\Int
n -> (forall k a. Ord k => Map k a -> k -> a
Map.! Text
"") forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (m :: * -> *) t a.
Monad m =>
Measure m t -> PerfT m t a -> m (Map Text t)
execPerfT Measure IO a
m (Int -> b
f forall t a b. Semigroup t => (a -> b) -> a -> PerfT IO t b
|$| Int
n)) [Int]
ns

-- | repetitive Double Meaure performance curve.
dcurve :: (Int -> Measure IO [Double]) -> StatDType -> Int -> (Int -> a) -> [Int] -> IO [Double]
dcurve :: forall a.
(Int -> Measure IO [Double])
-> StatDType -> Int -> (Int -> a) -> [Int] -> IO [Double]
dcurve Int -> Measure IO [Double]
m StatDType
s Int
sims Int -> a
f [Int]
ns = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Sum a -> a
getSum forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a b.
Semigroup a =>
Measure IO a -> (Int -> b) -> [Int] -> IO [a]
mcurve (forall a. a -> Sum a
Sum forall b c a. (b -> c) -> (a -> b) -> a -> c
. StatDType -> [Double] -> Double
statD StatDType
s forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> Measure IO [Double]
m Int
sims) Int -> a
f [Int]
ns

-- | time performance curve.
tcurve :: StatDType -> Int -> (Int -> a) -> [Int] -> IO [Double]
tcurve :: forall a. StatDType -> Int -> (Int -> a) -> [Int] -> IO [Double]
tcurve = forall a.
(Int -> Measure IO [Double])
-> StatDType -> Int -> (Int -> a) -> [Int] -> IO [Double]
dcurve (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (Integral a, Num b) => a -> b
fromIntegral) forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Measure IO [Cycles]
times)

-- | BigOrder estimate
--
-- > estOrder (\x -> sum [1..x]) 100 [1,10,100,1000,10000]
-- BigOrder {bigOrder = N1, bigFactor = 76.27652961460446, bigConstant = 0.0}
estOrder :: (Int -> b) -> Int -> [Int] -> IO (BigOrder Double)
estOrder :: forall b. (Int -> b) -> Int -> [Int] -> IO (BigOrder Double)
estOrder Int -> b
f Int
sims [Int]
ns = do
  [Double]
xs <- forall a. StatDType -> Int -> (Int -> a) -> [Int] -> IO [Double]
tcurve StatDType
StatBest Int
sims Int -> b
f [Int]
ns
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a b. (a -> b) -> a -> b
$ Order Double -> BigOrder Double
fromOrder forall a b. (a -> b) -> a -> b
$ forall a b. (a, b) -> a
fst forall a b. (a -> b) -> a -> b
$ [Double] -> [Double] -> (Order Double, [Double])
estO (forall a b. (Integral a, Num b) => a -> b
fromIntegral forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Int]
ns) [Double]
xs