{-# LANGUAGE OverloadedStrings #-}

-- | [Order of complexity](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)) calculations.
module Perf.BigO
  ( O (..),
    olist,
    promote,
    promote1,
    promote_,
    demote,
    demote1,
    spectrum,
    Order (..),
    bigO,
    runtime,
    BigOrder (..),
    fromOrder,
    toOrder,
    order,
    diffs,
    bestO,
    estO,
    estOs,
    makeNs,
    OrderOptions (..),
    defaultOrderOptions,
    parseOrderOptions,
  )
where

import Data.Bool
import Data.FormatN
import Data.List qualified as List
import Data.Maybe
import Data.Monoid
import Data.Vector qualified as V
import GHC.Generics
import Options.Applicative
import Prettyprinter
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
(O -> O -> Bool) -> (O -> O -> Bool) -> Eq O
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: O -> O -> Bool
== :: O -> O -> Bool
$c/= :: O -> O -> Bool
/= :: O -> O -> Bool
Eq, Eq O
Eq O =>
(O -> O -> Ordering)
-> (O -> O -> Bool)
-> (O -> O -> Bool)
-> (O -> O -> Bool)
-> (O -> O -> Bool)
-> (O -> O -> O)
-> (O -> O -> O)
-> Ord 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
$ccompare :: O -> O -> Ordering
compare :: O -> O -> Ordering
$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
>= :: O -> O -> Bool
$cmax :: O -> O -> O
max :: O -> O -> O
$cmin :: O -> O -> O
min :: O -> O -> O
Ord, Int -> O -> ShowS
[O] -> ShowS
O -> String
(Int -> O -> ShowS) -> (O -> String) -> ([O] -> ShowS) -> Show O
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> O -> ShowS
showsPrec :: Int -> O -> ShowS
$cshow :: O -> String
show :: O -> String
$cshowList :: [O] -> ShowS
showList :: [O] -> ShowS
Show, (forall x. O -> Rep O x) -> (forall x. Rep O x -> O) -> Generic O
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
$cfrom :: forall x. O -> Rep O x
from :: forall x. O -> Rep O x
$cto :: forall x. Rep O x -> O
to :: forall x. Rep O x -> O
Generic, Int -> O
O -> Int
O -> [O]
O -> O
O -> O -> [O]
O -> O -> O -> [O]
(O -> O)
-> (O -> O)
-> (Int -> O)
-> (O -> Int)
-> (O -> [O])
-> (O -> O -> [O])
-> (O -> O -> [O])
-> (O -> O -> O -> [O])
-> Enum 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
$csucc :: O -> O
succ :: O -> O
$cpred :: O -> O
pred :: O -> O
$ctoEnum :: Int -> O
toEnum :: Int -> O
$cfromEnum :: O -> Int
fromEnum :: O -> Int
$cenumFrom :: O -> [O]
enumFrom :: O -> [O]
$cenumFromThen :: O -> O -> [O]
enumFromThen :: O -> O -> [O]
$cenumFromTo :: O -> O -> [O]
enumFromTo :: O -> O -> [O]
$cenumFromThenTo :: O -> O -> O -> [O]
enumFromThenTo :: O -> O -> 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)),
    (Double -> Integer -> Double
forall a b. (Num a, Integral b) => a -> b -> a
^ (Integer
3 :: Integer)),
    (Double -> Integer -> Double
forall a b. (Num a, Integral b) => a -> b -> a
^ (Integer
2 :: Integer)),
    (Double -> Double -> Double
forall a. Floating a => a -> a -> a
** Double
1.5),
    \Double
n -> Double -> Double -> Bool -> Double
forall a. a -> a -> Bool -> a
bool (Double -> Double -> Bool -> Double
forall a. a -> a -> Bool -> a
bool (Double
n Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double -> Double
forall a. Floating a => a -> a
log Double
n) Double
1 (Double
n Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
<= Double
1)) Double
0 (Double
n Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
<= Double
0),
    Double -> Double
forall a. a -> a
id,
    (Double -> Double -> Double
forall a. Floating a => a -> a -> a
** Double
0.5),
    \Double
n -> Double -> Double -> Bool -> Double
forall a. a -> a -> Bool -> a
bool (Double -> Double -> Bool -> Double
forall a. a -> a -> Bool -> a
bool (Double -> Double
forall a. Floating a => a -> a
log Double
n) Double
1 (Double
n Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
<= Double
1)) Double
0 (Double
n Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
<= Double
0),
    \Double
n -> Double -> Double -> Bool -> Double
forall a. a -> a -> Bool -> a
bool Double
1 Double
0 (Double
n Double -> Double -> Bool
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
(Order a -> Order a -> Bool)
-> (Order a -> Order a -> Bool) -> Eq (Order a)
forall a. Eq a => Order a -> Order a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$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
/= :: Order a -> Order a -> Bool
Eq, Eq (Order a)
Eq (Order a) =>
(Order a -> Order a -> Ordering)
-> (Order a -> Order a -> Bool)
-> (Order a -> Order a -> Bool)
-> (Order a -> Order a -> Bool)
-> (Order a -> Order a -> Bool)
-> (Order a -> Order a -> Order a)
-> (Order a -> Order a -> Order a)
-> Ord (Order a)
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
$ccompare :: forall a. Ord a => Order a -> Order a -> Ordering
compare :: Order a -> Order a -> Ordering
$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
>= :: Order a -> Order a -> Bool
$cmax :: forall a. Ord a => Order a -> Order a -> Order a
max :: Order a -> Order a -> Order a
$cmin :: forall a. Ord a => Order a -> Order a -> Order a
min :: Order a -> Order a -> Order a
Ord, Int -> Order a -> ShowS
[Order a] -> ShowS
Order a -> String
(Int -> Order a -> ShowS)
-> (Order a -> String) -> ([Order a] -> ShowS) -> Show (Order a)
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
$cshowsPrec :: forall a. Show a => Int -> Order a -> ShowS
showsPrec :: Int -> Order a -> ShowS
$cshow :: forall a. Show a => Order a -> String
show :: Order a -> String
$cshowList :: forall a. Show a => [Order a] -> ShowS
showList :: [Order a] -> ShowS
Show, (forall x. Order a -> Rep (Order a) x)
-> (forall x. Rep (Order a) x -> Order a) -> Generic (Order a)
forall x. Rep (Order a) x -> Order a
forall x. Order a -> Rep (Order a) x
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
$cfrom :: forall a x. Order a -> Rep (Order a) x
from :: forall x. Order a -> Rep (Order a) x
$cto :: forall a x. Rep (Order a) x -> Order a
to :: forall x. Rep (Order a) x -> Order a
Generic, (forall a b. (a -> b) -> Order a -> Order b)
-> (forall a b. a -> Order b -> Order a) -> Functor Order
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
$cfmap :: forall a b. (a -> b) -> Order a -> Order b
fmap :: forall a b. (a -> b) -> Order a -> Order b
$c<$ :: forall a b. a -> Order b -> Order a
<$ :: forall a b. a -> Order b -> Order a
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 = [a] -> Order a
forall a. [a] -> Order a
Order ([a] -> Order a) -> [a] -> Order a
forall a b. (a -> b) -> a -> b
$ Int -> a -> [a]
forall a. Int -> a -> [a]
replicate Int
n a
0 [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> [a
a] [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> Int -> a -> [a]
forall a. Int -> a -> [a]
replicate (Int
7 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n) a
0
  where
    n :: Int
n = O -> Int
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 = [Double] -> Double
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ((Double -> Double -> Double) -> [Double] -> [Double] -> [Double]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Double -> Double -> Double
forall a. Num a => a -> a -> a
(*) [Double]
fs (((Double -> Double) -> Double -> Double
forall a b. (a -> b) -> a -> b
$ Double
n) ((Double -> Double) -> Double) -> [Double -> Double] -> [Double]
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 = O -> Double -> Order Double
forall a. Num a => O -> a -> Order a
order O
o (Double
m Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ ([Double -> Double]
promote_ [Double -> Double] -> Int -> Double -> Double
forall a. HasCallStack => [a] -> Int -> a
List.!! O -> Int
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) = (Int -> O
forall a. Enum a => Int -> a
toEnum Int
b, [a]
os [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
List.!! Int
b)
  where
    b :: Int
b = Int -> Maybe Int -> Int
forall a. a -> Maybe a -> a
fromMaybe Int
7 (Maybe Int -> Int) -> Maybe Int -> Int
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> Maybe Int
forall a. (a -> Bool) -> [a] -> Maybe Int
List.findIndex (a -> a -> Bool
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 ([Double] -> Order Double
forall a. [a] -> Order a
Order [Double]
r) Double
1
  where
    b :: Int
b = Int -> Maybe Int -> Int
forall a. a -> Maybe a -> a
fromMaybe Int
7 (Maybe Int -> Int) -> Maybe Int -> Int
forall a b. (a -> b) -> a -> b
$ (Double -> Bool) -> [Double] -> Maybe Int
forall a. (a -> Bool) -> [a] -> Maybe Int
List.findIndex (Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
> Double
0) [Double]
os
    r :: [Double]
r = Int -> [Double] -> [Double]
forall a. Int -> [a] -> [a]
take Int
b [Double]
os [Double] -> [Double] -> [Double]
forall a. Semigroup a => a -> a -> a
<> [Double
0] [Double] -> [Double] -> [Double]
forall a. Semigroup a => a -> a -> a
<> Int -> [Double] -> [Double]
forall a. Int -> [a] -> [a]
drop (Int
b Int -> Int -> Int
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') =
    [a] -> Order a
forall a. [a] -> Order a
Order ((a -> a -> a) -> [a] -> [a] -> [a]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith a -> a -> a
forall a. Num a => a -> a -> a
(+) [a]
o [a]
o')
  negate :: Order a -> Order a
negate (Order [a]
o) = [a] -> Order a
forall a. [a] -> Order a
Order ([a] -> Order a) -> [a] -> Order a
forall a b. (a -> b) -> a -> b
$ a -> a
forall a. Num a => a -> a
negate (a -> a) -> [a] -> [a]
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') =
    [a] -> Order a
forall a. [a] -> Order a
Order ((a -> a -> a) -> [a] -> [a] -> [a]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith a -> a -> a
forall a. Num a => a -> a -> a
(*) [a]
o [a]
o')
  abs :: Order a -> Order a
abs = Order a -> Order a
forall a. HasCallStack => a
undefined
  signum :: Order a -> Order a
signum = Order a -> Order a
forall a. HasCallStack => a
undefined
  fromInteger :: Integer -> Order a
fromInteger Integer
x = [a] -> Order a
forall a. [a] -> Order a
Order ([a] -> Order a) -> [a] -> Order a
forall a b. (a -> b) -> a -> b
$ Int -> a -> [a]
forall a. Int -> a -> [a]
replicate Int
9 (Integer -> a
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} deriving (BigOrder a -> BigOrder a -> Bool
(BigOrder a -> BigOrder a -> Bool)
-> (BigOrder a -> BigOrder a -> Bool) -> Eq (BigOrder a)
forall a. Eq a => BigOrder a -> BigOrder a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$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
/= :: BigOrder a -> BigOrder a -> Bool
Eq, Eq (BigOrder a)
Eq (BigOrder a) =>
(BigOrder a -> BigOrder a -> Ordering)
-> (BigOrder a -> BigOrder a -> Bool)
-> (BigOrder a -> BigOrder a -> Bool)
-> (BigOrder a -> BigOrder a -> Bool)
-> (BigOrder a -> BigOrder a -> Bool)
-> (BigOrder a -> BigOrder a -> BigOrder a)
-> (BigOrder a -> BigOrder a -> BigOrder a)
-> Ord (BigOrder a)
BigOrder a -> BigOrder a -> Bool
BigOrder a -> BigOrder a -> Ordering
BigOrder a -> BigOrder a -> BigOrder 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 (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
$ccompare :: forall a. Ord a => BigOrder a -> BigOrder a -> Ordering
compare :: BigOrder a -> BigOrder a -> Ordering
$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
>= :: BigOrder a -> BigOrder a -> Bool
$cmax :: forall a. Ord a => BigOrder a -> BigOrder a -> BigOrder a
max :: BigOrder a -> BigOrder a -> BigOrder a
$cmin :: forall a. Ord a => BigOrder a -> BigOrder a -> BigOrder a
min :: BigOrder a -> BigOrder a -> BigOrder a
Ord, Int -> BigOrder a -> ShowS
[BigOrder a] -> ShowS
BigOrder a -> String
(Int -> BigOrder a -> ShowS)
-> (BigOrder a -> String)
-> ([BigOrder a] -> ShowS)
-> Show (BigOrder a)
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
$cshowsPrec :: forall a. Show a => Int -> BigOrder a -> ShowS
showsPrec :: Int -> BigOrder a -> ShowS
$cshow :: forall a. Show a => BigOrder a -> String
show :: BigOrder a -> String
$cshowList :: forall a. Show a => [BigOrder a] -> ShowS
showList :: [BigOrder a] -> ShowS
Show, (forall x. BigOrder a -> Rep (BigOrder a) x)
-> (forall x. Rep (BigOrder a) x -> BigOrder a)
-> Generic (BigOrder a)
forall x. Rep (BigOrder a) x -> BigOrder a
forall x. BigOrder a -> Rep (BigOrder a) x
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
$cfrom :: forall a x. BigOrder a -> Rep (BigOrder a) x
from :: forall x. BigOrder a -> Rep (BigOrder a) x
$cto :: forall a x. Rep (BigOrder a) x -> BigOrder a
to :: forall x. Rep (BigOrder a) x -> BigOrder a
Generic, (forall a b. (a -> b) -> BigOrder a -> BigOrder b)
-> (forall a b. a -> BigOrder b -> BigOrder a) -> Functor BigOrder
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
$cfmap :: forall a b. (a -> b) -> BigOrder a -> BigOrder b
fmap :: forall a b. (a -> b) -> BigOrder a -> BigOrder b
$c<$ :: forall a b. a -> BigOrder b -> BigOrder a
<$ :: forall a b. a -> BigOrder b -> BigOrder a
Functor)

instance Pretty (BigOrder Double) where
  pretty :: forall ann. BigOrder Double -> Doc ann
pretty (BigOrder O
o Double
f) = Text -> Doc ann
forall ann. Text -> Doc ann
forall a ann. Pretty a => a -> Doc ann
pretty (Maybe Int -> Double -> Text
decimal (Int -> Maybe Int
forall a. a -> Maybe a
Just Int
2) Double
f) Doc ann -> Doc ann -> Doc ann
forall a. Semigroup a => a -> a -> a
<> Doc ann
" * O(" Doc ann -> Doc ann -> Doc ann
forall a. Semigroup a => a -> a -> a
<> O -> Doc ann
forall a ann. Show a => a -> Doc ann
viaShow O
o Doc ann -> Doc ann -> Doc ann
forall a. Semigroup a => a -> a -> a
<> Doc ann
")"

-- | compute the BigOrder
--
-- >>> fromOrder o
-- BigOrder {bigOrder = N2, bigFactor = 1.0}
fromOrder :: Order Double -> BigOrder Double
fromOrder :: Order Double -> BigOrder Double
fromOrder Order Double
o' = O -> Double -> BigOrder Double
forall a. O -> a -> BigOrder a
BigOrder O
o Double
f
  where
    (O
o, Double
f) = Order Double -> (O, Double)
forall a. (Ord a, Num a) => Order a -> (O, a)
bigO 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,0.0]}
toOrder :: BigOrder Double -> Order Double
toOrder :: BigOrder Double -> Order Double
toOrder (BigOrder O
o Double
f) = O -> Double -> Order Double
forall a. Num a => O -> a -> Order a
order O
o Double
f

-- | 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 = [Double] -> Order Double
forall a. [a] -> Order a
Order ((Double
m /) (Double -> Double)
-> ((Double -> Double) -> Double) -> (Double -> Double) -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Double -> Double) -> Double -> Double
forall a b. (a -> b) -> a -> b
$ Double
n) ((Double -> Double) -> Double) -> [Double -> Double] -> [Double]
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 = [[Double]] -> [[Double]]
forall a. [[a]] -> [[a]]
List.transpose ([[Double]] -> [[Double]]) -> [[Double]] -> [[Double]]
forall a b. (a -> b) -> a -> b
$ (Double -> Double -> [Double])
-> [Double] -> [Double] -> [[Double]]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\Double
n Double
m -> (O -> Double -> Double) -> [O] -> [Double] -> [Double]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\O
o' Double
f -> Double
m Double -> Double -> Double
forall a. Num a => a -> a -> a
- Order Double -> Double -> Double
promote (O -> Double -> Order Double
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 = Order Double -> [Double]
forall a. Order a -> [a]
factors (Double -> Double -> Order Double
spectrum ([Double] -> Double
forall a. HasCallStack => [a] -> a
List.last [Double]
ns) ([Double] -> Double
forall a. HasCallStack => [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 =
  Int -> O
forall a. Enum a => Int -> a
toEnum (Int -> O) -> Int -> O
forall a b. (a -> b) -> a -> b
$
    Vector Double -> Int
forall a. Ord a => Vector a -> Int
V.minIndex (Vector Double -> Int) -> Vector Double -> Int
forall a b. (a -> b) -> a -> b
$
      [Double] -> Vector Double
forall a. [a] -> Vector a
V.fromList
        ([Double] -> Double
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ([Double] -> Double) -> [[Double]] -> [Double]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ([Double] -> [Double]) -> [[Double]] -> [[Double]]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Double -> Double) -> [Double] -> [Double]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Double -> Double
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 [[Double]] -> Int -> [Double]
forall a. HasCallStack => [a] -> Int -> a
List.!! O -> Int
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 ([Double] -> Double
forall a. HasCallStack => [a] -> a
List.last [Double]
ns) ([Double] -> Double
forall a. HasCallStack => [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 [Order Double] -> [Order Double] -> [Order Double]
forall a. Semigroup a => a -> a -> a
<> [O -> Double -> Order Double
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 [Order Double] -> [Order Double] -> [Order Double]
forall a. Semigroup a => a -> a -> a
<> [Order Double
o']) ([Double] -> [Double]
forall a. HasCallStack => [a] -> [a]
List.init [Double]
ns') ([Double] -> [Double]
forall a. HasCallStack => [a] -> [a]
List.init [Double]
res)

makeNs :: Int -> Double -> Int -> [Int]
makeNs :: Int -> Double -> Int -> [Int]
makeNs Int
n0 Double
d Int
low = [Int] -> [Int]
forall a. [a] -> [a]
reverse ([Int] -> [Int]) -> [Int] -> [Int]
forall a b. (a -> b) -> a -> b
$ Int -> [Int] -> [Int]
go (Int -> Int
forall {b} {a}. (Integral b, Integral a) => a -> b
next Int
n0) [Int
n0]
  where
    next :: a -> b
next a
n = Double -> b
forall b. Integral b => Double -> b
forall a b. (RealFrac a, Integral b) => a -> b
floor (a -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
n Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
d)
    go :: Int -> [Int] -> [Int]
    go :: Int -> [Int] -> [Int]
go Int
n [Int]
acc = [Int] -> [Int] -> Bool -> [Int]
forall a. a -> a -> Bool -> a
bool (Int -> [Int] -> [Int]
go (Int -> Int
forall {b} {a}. (Integral b, Integral a) => a -> b
next Int
n) ([Int]
acc [Int] -> [Int] -> [Int]
forall a. Semigroup a => a -> a -> a
<> [Int
n])) [Int]
acc (Int
low Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n)

data OrderOptions = OrderOptions
  { OrderOptions -> Bool
doOrder :: Bool,
    OrderOptions -> Int
orderLow :: Int,
    OrderOptions -> Double
orderDivisor :: Double
  }
  deriving (OrderOptions -> OrderOptions -> Bool
(OrderOptions -> OrderOptions -> Bool)
-> (OrderOptions -> OrderOptions -> Bool) -> Eq OrderOptions
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: OrderOptions -> OrderOptions -> Bool
== :: OrderOptions -> OrderOptions -> Bool
$c/= :: OrderOptions -> OrderOptions -> Bool
/= :: OrderOptions -> OrderOptions -> Bool
Eq, Int -> OrderOptions -> ShowS
[OrderOptions] -> ShowS
OrderOptions -> String
(Int -> OrderOptions -> ShowS)
-> (OrderOptions -> String)
-> ([OrderOptions] -> ShowS)
-> Show OrderOptions
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> OrderOptions -> ShowS
showsPrec :: Int -> OrderOptions -> ShowS
$cshow :: OrderOptions -> String
show :: OrderOptions -> String
$cshowList :: [OrderOptions] -> ShowS
showList :: [OrderOptions] -> ShowS
Show, (forall x. OrderOptions -> Rep OrderOptions x)
-> (forall x. Rep OrderOptions x -> OrderOptions)
-> Generic OrderOptions
forall x. Rep OrderOptions x -> OrderOptions
forall x. OrderOptions -> Rep OrderOptions x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall x. OrderOptions -> Rep OrderOptions x
from :: forall x. OrderOptions -> Rep OrderOptions x
$cto :: forall x. Rep OrderOptions x -> OrderOptions
to :: forall x. Rep OrderOptions x -> OrderOptions
Generic)

defaultOrderOptions :: OrderOptions
defaultOrderOptions :: OrderOptions
defaultOrderOptions = Bool -> Int -> Double -> OrderOptions
OrderOptions Bool
False Int
10 Double
9

parseOrderOptions :: OrderOptions -> Parser OrderOptions
parseOrderOptions :: OrderOptions -> Parser OrderOptions
parseOrderOptions OrderOptions
def =
  Bool -> Int -> Double -> OrderOptions
OrderOptions
    (Bool -> Int -> Double -> OrderOptions)
-> Parser Bool -> Parser (Int -> Double -> OrderOptions)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Mod FlagFields Bool -> Parser Bool
switch (String -> Mod FlagFields Bool
forall (f :: * -> *) a. HasName f => String -> Mod f a
long String
"order" Mod FlagFields Bool -> Mod FlagFields Bool -> Mod FlagFields Bool
forall a. Semigroup a => a -> a -> a
<> Char -> Mod FlagFields Bool
forall (f :: * -> *) a. HasName f => Char -> Mod f a
short Char
'o' Mod FlagFields Bool -> Mod FlagFields Bool -> Mod FlagFields Bool
forall a. Semigroup a => a -> a -> a
<> String -> Mod FlagFields Bool
forall (f :: * -> *) a. String -> Mod f a
help String
"calculate order")
    Parser (Int -> Double -> OrderOptions)
-> Parser Int -> Parser (Double -> OrderOptions)
forall a b. Parser (a -> b) -> Parser a -> Parser b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> ReadM Int -> Mod OptionFields Int -> Parser Int
forall a. ReadM a -> Mod OptionFields a -> Parser a
option ReadM Int
forall a. Read a => ReadM a
auto (Int -> Mod OptionFields Int
forall (f :: * -> *) a. HasValue f => a -> Mod f a
value (OrderOptions -> Int
orderLow OrderOptions
def) Mod OptionFields Int
-> Mod OptionFields Int -> Mod OptionFields Int
forall a. Semigroup a => a -> a -> a
<> String -> Mod OptionFields Int
forall (f :: * -> *) a. HasName f => String -> Mod f a
long String
"orderlowest" Mod OptionFields Int
-> Mod OptionFields Int -> Mod OptionFields Int
forall a. Semigroup a => a -> a -> a
<> (Int -> String) -> Mod OptionFields Int
forall a (f :: * -> *). (a -> String) -> Mod f a
showDefaultWith Int -> String
forall a. Show a => a -> String
show Mod OptionFields Int
-> Mod OptionFields Int -> Mod OptionFields Int
forall a. Semigroup a => a -> a -> a
<> String -> Mod OptionFields Int
forall (f :: * -> *) a. HasMetavar f => String -> Mod f a
metavar String
"DOUBLE" Mod OptionFields Int
-> Mod OptionFields Int -> Mod OptionFields Int
forall a. Semigroup a => a -> a -> a
<> String -> Mod OptionFields Int
forall (f :: * -> *) a. String -> Mod f a
help String
"smallest order test")
    Parser (Double -> OrderOptions)
-> Parser Double -> Parser OrderOptions
forall a b. Parser (a -> b) -> Parser a -> Parser b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> ReadM Double -> Mod OptionFields Double -> Parser Double
forall a. ReadM a -> Mod OptionFields a -> Parser a
option ReadM Double
forall a. Read a => ReadM a
auto (Double -> Mod OptionFields Double
forall (f :: * -> *) a. HasValue f => a -> Mod f a
value (OrderOptions -> Double
orderDivisor OrderOptions
def) Mod OptionFields Double
-> Mod OptionFields Double -> Mod OptionFields Double
forall a. Semigroup a => a -> a -> a
<> String -> Mod OptionFields Double
forall (f :: * -> *) a. HasName f => String -> Mod f a
long String
"orderdivisor" Mod OptionFields Double
-> Mod OptionFields Double -> Mod OptionFields Double
forall a. Semigroup a => a -> a -> a
<> (Double -> String) -> Mod OptionFields Double
forall a (f :: * -> *). (a -> String) -> Mod f a
showDefaultWith Double -> String
forall a. Show a => a -> String
show Mod OptionFields Double
-> Mod OptionFields Double -> Mod OptionFields Double
forall a. Semigroup a => a -> a -> a
<> String -> Mod OptionFields Double
forall (f :: * -> *) a. HasMetavar f => String -> Mod f a
metavar String
"DOUBLE" Mod OptionFields Double
-> Mod OptionFields Double -> Mod OptionFields Double
forall a. Semigroup a => a -> a -> a
<> String -> Mod OptionFields Double
forall (f :: * -> *) a. String -> Mod f a
help String
"divisor for order computation")