Perf.BigO

Order of complexity calculations.

What is Order of Complexity .

donsbot blog

profiling

rules of thumb

Documentation

data O

order type

Constructors

N3

cubic

N2

quadratic

N32

^3/2

NLogN

N * log N

N1

linear

N12

sqrt N

LogN

log N

N0

constant

Instances

Enum O

Defined in Perf.BigO

Methods

succ :: O -> O

pred :: O -> O

toEnum :: Int -> O

fromEnum :: O -> Int

enumFrom :: O -> [O]

enumFromThen :: O -> O -> [O]

enumFromTo :: O -> O -> [O]

enumFromThenTo :: O -> O -> O -> [O]

Eq O

Defined in Perf.BigO

Methods

(==) :: O -> O -> Bool

(/=) :: O -> O -> Bool

Ord O

Defined in Perf.BigO

Methods

compare :: O -> O -> Ordering

(<) :: O -> O -> Bool

(<=) :: O -> O -> Bool

(>) :: O -> O -> Bool

(>=) :: O -> O -> Bool

max :: O -> O -> O

min :: O -> O -> O

Show O

Defined in Perf.BigO

Methods

showsPrec :: Int -> O -> ShowS

show :: O -> String

showList :: [O] -> ShowS

Generic O

Defined in Perf.BigO

Associated Types

type Rep O :: Type -> Type

Methods

from :: O -> Rep O x

to :: Rep O x -> O

type Rep O

Defined in Perf.BigO

type Rep O = D1 ('MetaData "O" "Perf.BigO" "perf-0.10.0-BT4aHB78pyC11ZtafhbK03" 'False) (((C1 ('MetaCons "N3" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "N2" 'PrefixI 'False) (U1 :: Type -> Type)) :+: (C1 ('MetaCons "N32" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "NLogN" 'PrefixI 'False) (U1 :: Type -> Type))) :+: ((C1 ('MetaCons "N1" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "N12" 'PrefixI 'False) (U1 :: Type -> Type)) :+: (C1 ('MetaCons "LogN" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "N0" 'PrefixI 'False) (U1 :: Type -> Type))))

olist :: [O]

enumeration of O types

>>> olist
[N3,N2,N32,NLogN,N1,N12,LogN,N0]

promote :: Order Double -> Double -> Double

Calculate the expected performance measure

>>> promote (order N2 1) 10
100.0

promote1 :: Order Double -> Double

Calculate the expected performance measure per n

>>> promote (order N2 1) 10
100.0

promote_ :: [Double -> Double]

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]

demote :: O -> Double -> Double -> Order Double

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

demote1 :: O -> Double -> Order Double

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

spectrum :: Double -> Double -> Order Double

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

newtype Order a

a set of factors for each order, which represents a full Order specification.

Constructors

Order

Fields

• factors :: [a]

Instances

Functor Order

Defined in Perf.BigO

Methods

fmap :: (a -> b) -> Order a -> Order b

(<$) :: a -> Order b -> Order a

Eq a => Eq (Order a)

Defined in Perf.BigO

Methods

(==) :: Order a -> Order a -> Bool

(/=) :: Order a -> Order a -> Bool

Num a => Num (Order a)

Defined in Perf.BigO

Methods

(+) :: Order a -> Order a -> Order a

(-) :: Order a -> Order a -> Order a

(*) :: Order a -> Order a -> Order a

negate :: Order a -> Order a

abs :: Order a -> Order a

signum :: Order a -> Order a

fromInteger :: Integer -> Order a

Ord a => Ord (Order a)

Defined in Perf.BigO

Methods

compare :: 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

max :: Order a -> Order a -> Order a

min :: Order a -> Order a -> Order a

Show a => Show (Order a)

Defined in Perf.BigO

Methods

showsPrec :: Int -> Order a -> ShowS

show :: Order a -> String

showList :: [Order a] -> ShowS

Generic (Order a)

Defined in Perf.BigO

Associated Types

type Rep (Order a) :: Type -> Type

Methods

from :: Order a -> Rep (Order a) x

to :: Rep (Order a) x -> Order a

type Rep (Order a)

Defined in Perf.BigO

type Rep (Order a) = D1 ('MetaData "Order" "Perf.BigO" "perf-0.10.0-BT4aHB78pyC11ZtafhbK03" 'True) (C1 ('MetaCons "Order" 'PrefixI 'True) (S1 ('MetaSel ('Just "factors") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [a])))

bigO :: (Ord a, Num a) => Order a -> (O, a)

find the dominant order, and it's factor

>>> bigO o
(N2,1.0)

runtime :: Order Double -> Double

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

data BigOrder a

A set of factors consisting of the dominant order, the dominant order factor and a constant factor

Constructors

BigOrder

Fields

• bigOrder :: O
• bigFactor :: a
• bigConstant :: a

Instances

Functor BigOrder

Defined in Perf.BigO

Methods

fmap :: (a -> b) -> BigOrder a -> BigOrder b

(<$) :: a -> BigOrder b -> BigOrder a

Eq a => Eq (BigOrder a)

Defined in Perf.BigO

Methods

(==) :: BigOrder a -> BigOrder a -> Bool

(/=) :: BigOrder a -> BigOrder a -> Bool

Ord a => Ord (BigOrder a)

Defined in Perf.BigO

Methods

compare :: 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

max :: BigOrder a -> BigOrder a -> BigOrder a

min :: BigOrder a -> BigOrder a -> BigOrder a

Show a => Show (BigOrder a)

Defined in Perf.BigO

Methods

showsPrec :: Int -> BigOrder a -> ShowS

show :: BigOrder a -> String

showList :: [BigOrder a] -> ShowS

Generic (BigOrder a)

Defined in Perf.BigO

Associated Types

type Rep (BigOrder a) :: Type -> Type

Methods

from :: BigOrder a -> Rep (BigOrder a) x

to :: Rep (BigOrder a) x -> BigOrder a

type Rep (BigOrder a)

Defined in Perf.BigO

type Rep (BigOrder a) = D1 ('MetaData "BigOrder" "Perf.BigO" "perf-0.10.0-BT4aHB78pyC11ZtafhbK03" 'False) (C1 ('MetaCons "BigOrder" 'PrefixI 'True) (S1 ('MetaSel ('Just "bigOrder") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 O) :*: (S1 ('MetaSel ('Just "bigFactor") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Just "bigConstant") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a))))

fromOrder :: Order Double -> BigOrder Double

compute the BigOrder

>>> fromOrder o
BigOrder {bigOrder = N2, bigFactor = 1.0, bigConstant = 100.0}

toOrder :: BigOrder Double -> Order Double

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

order :: Num a => O -> a -> Order a

create an Order

>>> order N2 1
Order {factors = [0,1,0,0,0,0,0,0]}

mcurve :: Semigroup a => Measure IO a -> (Int -> b) -> [Int] -> IO [a]

performance curve for a Measure.

dcurve :: (Int -> Measure IO [Double]) -> StatDType -> Int -> (Int -> a) -> [Int] -> IO [Double]

repetitive Double Meaure performance curve.

tcurve :: StatDType -> Int -> (Int -> a) -> [Int] -> IO [Double]

time performance curve.

diffs :: [Double] -> [Double] -> [[Double]]

The errors for a list of n's and measurements, based on the spectrum of the last measurement.

bestO :: [Double] -> [Double] -> O

minimum error order for a list of measurements

>>> bestO ns ms
N1

estO :: [Double] -> [Double] -> (Order Double, [Double])

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

estOs :: [Double] -> [Double] -> [Order Double]

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

estOrder :: (Int -> b) -> Int -> [Int] -> IO (BigOrder Double)

BigOrder estimate

estOrder (\x -> sum [1..x]) 100 [1,10,100,1000,10000]

BigOrder {bigOrder = N1, bigFactor = 76.27652961460446, bigConstant = 0.0}