Safe Haskell  SafeInferred 

Language  Haskell2010 
Guess complexity of the function.
Synopsis
 fit :: FitConfig > IO Complexity
 fits :: FitConfig > IO (NonEmpty Complexity)
 mkFitConfig :: NFData a => (Word > a) > (Word, Word) > FitConfig
 data FitConfig = FitConfig {
 fitBench :: Word > Benchmarkable
 fitLow :: Word
 fitHigh :: Word
 fitTimeout :: Timeout
 fitRelStDev :: RelStDev
 fitOracle :: Map Word Measurement > Complexity
 data Complexity = Complexity {
 cmplVarPower :: !Double
 cmplLogPower :: !Word
 cmplMultiplier :: !Double
 data Measurement = Measurement {}
 guessComplexity :: Map Word Measurement > Complexity
 guessPolynomialComplexity :: Map Word Measurement > Complexity
 evalComplexity :: Complexity > Word > Double
 isConstant :: Complexity > Bool
 isLogarithmic :: Complexity > Bool
 isLinear :: Complexity > Bool
 isLinearithmic :: Complexity > Bool
 isQuadratic :: Complexity > Bool
 isCubic :: Complexity > Bool
Fit benchmarks
fit :: FitConfig > IO Complexity Source #
Determine time complexity of the function:
>>>
fit $ mkFitConfig (\x > sum [1..x]) (10, 10000)
1.2153e8 * x>>>
fit $ mkFitConfig (\x > Data.List.nub [1..x]) (10, 10000)
2.8369e9 * x ^ 2>>>
fit $ mkFitConfig (\x > Data.List.sort $ take (fromIntegral x) $ iterate (\n > n * 6364136223846793005 + 1) (1 :: Int)) (10, 100000)
5.2990e8 * x * log x
One can usually get reliable results for functions, which do not
allocate much: like inplace vector sort or fused list operations like
sum
[1..x]
.
Unfortunately, fitting functions, which allocate a lot,
is likely to be disappointing: GC kicks in irregularly depending on nursery
and heap sizes and often skews observations beyond any recognition.
Consider running such measurements with O0
or in ghci
prompt. This is how
the usage example above was generated. Without optimizations your program
allocates much more and triggers GC regularly, somewhat evening out its effect.
While suitable for automatic estimates, fit
generally provides bad user
experience in interactive environments, because it can take a very long time
before it returns a result without any heartbeat in between. Consider using
fits
or enabling debug
flag.
fits :: FitConfig > IO (NonEmpty Complexity) Source #
Same as fit
, but interactively emits a list of complexities,
gradually converging to the final result.
If fit
takes too long, you might wish to implement your own criterion
of convergence atop of fits
directly.
>>>
cmpls < fits $ mkFitConfig (\x > sum [1..x]) (10, 10000)
>>>
traverse print cmpls
3.36e8 * x ^ 0.903 1.39e8 * x 1.38e8 * x ...
FitConfig  

Complexity
data Complexity Source #
Complexity
a
b
k
represents a time complexity
\( k \, x^a \log^b x \), where \( x \) is problem's size.
Complexity  

Instances
data Measurement Source #
Represents a time measurement for a given problem's size.
Instances
guessComplexity :: Map Word Measurement > Complexity Source #
Guess time complexity from a map where keys are problem's sizes and values are time measurements (or instruction counts).
>>>
:set XNumDecimals
>>>
guessComplexity $ Data.Map.fromList $ map (\(x, t) > (x, Measurement t 1)) [(2, 4), (3, 10), (4, 15), (5, 25)]
0.993 * x ^ 2>>>
guessComplexity $ Data.Map.fromList $ map (\(x, t) > (x, Measurement t 1)) [(1e2, 2.1), (1e3, 2.9), (1e4, 4.1), (1e5, 4.9)]
0.433 * log x
This function uses following simplifying assumptions:
 All coefficients are nonnegative.
 The power of \( \log x \) (
cmplLogPower
) is unlikely to be \( > 1 \).  The power of \( x \) (
cmplVarPower
) is unlikely to be fractional.
This function is unsuitable to guess superpolynomial and higher classes of complexity.
guessPolynomialComplexity :: Map Word Measurement > Complexity Source #
Same as guessComplexity, but the power of \( \log x \) (cmplLogPower
)
is pinned to be 0.
Since: 0.1.1
evalComplexity :: Complexity > Word > Double Source #
Evaluate time complexity for a given size of the problem.
Predicates
isConstant :: Complexity > Bool Source #
Is the complexity \( f(x) = k \)?
isLogarithmic :: Complexity > Bool Source #
Is the complexity \( f(x) = k \log x \)?
isLinear :: Complexity > Bool Source #
Is the complexity \( f(x) = k \, x \)?
isLinearithmic :: Complexity > Bool Source #
Is the complexity \( f(x) = k \, x \log x \)?
isQuadratic :: Complexity > Bool Source #
Is the complexity \( f(x) = k \, x^2 \)?
isCubic :: Complexity > Bool Source #
Is the complexity \( f(x) = k \, x^3 \)?