tasty-bench-fit (empty) → 0.1
raw patch · 7 files changed
+715/−0 lines, 7 filesdep +basedep +containersdep +deepseq
Dependencies added: base, containers, deepseq, infinite-list, regression-simple, tasty, tasty-bench, tasty-bench-fit, tasty-expected-failure, tasty-quickcheck
Files
- CHANGELOG.md +3/−0
- LICENSE +21/−0
- README.md +16/−0
- src/Test/Tasty/Bench/Fit.hs +197/−0
- src/Test/Tasty/Bench/Fit/Complexity.hs +283/−0
- tasty-bench-fit.cabal +63/−0
- test/Main.hs +132/−0
+ CHANGELOG.md view
@@ -0,0 +1,3 @@+## 0.1++* Initial release.
+ LICENSE view
@@ -0,0 +1,21 @@+MIT License++Copyright (c) 2023 Bodigrim++Permission is hereby granted, free of charge, to any person obtaining a copy+of this software and associated documentation files (the "Software"), to deal+in the Software without restriction, including without limitation the rights+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in all+copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE+SOFTWARE.
+ README.md view
@@ -0,0 +1,16 @@+# tasty-bench-fit++Benchmark a given function for variable input sizes and find out its time complexity.++```haskell+> fit $ mkFitConfig (\x -> sum [1..x]) (10, 10000)+1.2153e-8 * x+> fit $ mkFitConfig (\x -> Data.List.nub [1..x]) (10, 10000)+2.8369e-9 * x ^ 2+> fit $ mkFitConfig (\x -> Data.List.sort $ take (fromIntegral x) $ iterate (\n -> n * 6364136223846793005 + 1) (1 :: Int)) (10, 100000)+5.2990e-8 * x * log x+```++One can usually get reliable results for functions, which do not allocate much: like in-place 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.
+ src/Test/Tasty/Bench/Fit.hs view
@@ -0,0 +1,197 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE NumDecimals #-}+{-# LANGUAGE RecordWildCards #-}+{-# LANGUAGE ScopedTypeVariables #-}++-- | Guess complexity of the function.+module Test.Tasty.Bench.Fit (+ -- * Fit benchmarks+ fit,+ fits,+ mkFitConfig,+ FitConfig (..),++ -- * Complexity+ Complexity (..),+ Measurement (..),+ guessComplexity,+ evalComplexity,++ -- * Predicates+ isConstant,+ isLogarithmic,+ isLinear,+ isLinearithmic,+ isQuadratic,+ isCubic,+) where++import Control.DeepSeq (NFData)+import Data.List (maximumBy)+import Data.List.NonEmpty (NonEmpty (..))+import qualified Data.List.NonEmpty as NE+import Data.Map (Map)+import qualified Data.Map as M+import Data.Ord (comparing)+import System.IO.Unsafe (unsafeInterleaveIO)+import Test.Tasty (Timeout, mkTimeout)+import Test.Tasty.Bench (Benchmarkable, RelStDev (..), measureCpuTimeAndStDev, nf)+import Test.Tasty.Bench.Fit.Complexity (+ Complexity (..),+ Measurement (..),+ evalComplexity,+ guessComplexity,+ isConstant,+ isCubic,+ isLinear,+ isLinearithmic,+ isLogarithmic,+ isQuadratic,+ )++#ifdef DEBUG+import Debug.Trace+#endif++-- | Configuration for 'fit'.+data FitConfig = FitConfig+ { fitBench :: Word -> Benchmarkable+ -- ^ Which function to measure? Typically 'nf' @f@.+ , fitLow :: Word+ -- ^ The smallest size of the input.+ -- It should be as small as possible, but big enough for the main asymptotic+ -- term to dwarf constant overhead and other terms.+ , fitHigh :: Word+ -- ^ The largest size of the input.+ -- As large as practically possible, at least 100x larger than+ -- the smallest size.+ , fitTimeout :: Timeout+ -- ^ Timeout of individual measurements.+ , fitRelStDev :: RelStDev+ -- ^ Target relative standard deviation of individual measurements.+ , fitOracle :: Map Word Measurement -> Complexity+ -- ^ An oracle to determine complexity from measurements.+ -- Typically 'guessComplexity'.+ }++-- | Generate a default 'fit' configuration.+mkFitConfig+ :: (NFData a)+ => (Word -> a)+ -- ^ Raw function to measure, without 'nf'.+ -> (Word, Word)+ -- ^ The smallest and the largest sizes of the input.+ -> FitConfig+mkFitConfig f (low, high) =+ FitConfig+ { fitBench = nf f+ , fitLow = low+ , fitHigh = high+ , fitTimeout = mkTimeout 1e8+ , fitRelStDev = RelStDev 0.02+ , fitOracle = guessComplexity+ }++-- | Determine time complexity of the function:+--+-- >>> fit $ mkFitConfig (\x -> sum [1..x]) (10, 10000)+-- 1.2153e-8 * x+-- >>> fit $ mkFitConfig (\x -> Data.List.nub [1..x]) (10, 10000)+-- 2.8369e-9 * x ^ 2+-- >>> fit $ mkFitConfig (\x -> Data.List.sort $ take (fromIntegral x) $ iterate (\n -> n * 6364136223846793005 + 1) (1 :: Int)) (10, 100000)+-- 5.2990e-8 * x * log x+--+-- One can usually get reliable results for functions, which do not+-- allocate much: like in-place 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.+fit :: FitConfig -> IO Complexity+fit cnf = converge <$> fits cnf++converge :: NonEmpty Complexity -> Complexity+converge xs = case zs of+ [] -> NE.last xs+ (_, _, z) : _ -> z+ where+ ys = NE.toList xs+ zs =+ dropWhile (\(x, y, z) -> p x z || p y z) $+ zip3 ys (tail ys) (drop 2 ys)+ p+ Complexity {cmplVarPower = varPow, cmplLogPower = logPow, cmplMultiplier = mult}+ Complexity {cmplVarPower = varPow', cmplLogPower = logPow', cmplMultiplier = mult'} =+ abs (varPow - varPow') > 0.001+ || logPow /= logPow'+ || abs ((mult - mult') / mult) > 0.01++-- | 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.+fits :: FitConfig -> IO (NonEmpty Complexity)+fits FitConfig {..} = unsafeInterleaveIO $ do+ lowTime <- measure fitLow+ highTime <- measure fitHigh+ let mp = M.fromList [(fitLow, lowTime), (fitHigh, highTime)]+ cmpl = fitOracle mp+ cmpl `seq` (cmpl :|) <$> go mp+ where+ measure :: Word -> IO Measurement+ measure =+ fmap (uncurry Measurement)+ . measureCpuTimeAndStDev fitTimeout fitRelStDev+ . fitBench++ processGap+ :: forall t+ . (Ord t)+ => [(Word, t)]+ -> Map Word Measurement+ -> IO (Map Word Measurement)+ processGap gaps mp+ | M.null gaps' = pure mp+ | otherwise = (\m -> M.insert maxGap m mp) <$> measure maxGap+ where+ gaps' = M.fromList gaps `M.difference` mp+ maxGap = fst $ maximumBy (comparing snd) $ M.toList gaps'++ go :: Map Word Measurement -> IO [Complexity]+ go mp = unsafeInterleaveIO $ do+ let xys = M.toAscList $ fmap measTime mp+ paired = zip xys (drop 1 xys)++ arithGaps :: [(Word, Double)]+ arithGaps =+ map+ (\((x, tx), (y, ty)) -> (round ((d x + d y) / 2), ty - tx))+ paired++ geomGaps :: [(Word, Double)]+ geomGaps =+ map+ (\((x, tx), (y, ty)) -> (round (sqrt (d x * d y)), ty / tx))+ paired++ mp' <- processGap arithGaps mp+ mp'' <- processGap geomGaps mp'+ traceShowM' (M.keys mp'')+ let cmpl = fitOracle mp''+ traceShowM' cmpl+ (cmpl :) <$> (if mp == mp'' then pure [] else go mp'')++d :: Word -> Double+d = fromIntegral++traceShowM' :: (Applicative m, Show a) => a -> m ()+#ifdef DEBUG+traceShowM' = traceShowM+#else+traceShowM' = const (pure ())+#endif
+ src/Test/Tasty/Bench/Fit/Complexity.hs view
@@ -0,0 +1,283 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE LambdaCase #-}+{-# LANGUAGE PostfixOperators #-}+{-# LANGUAGE RecordWildCards #-}+{-# LANGUAGE ViewPatterns #-}++-- | Guess complexity from data.+module Test.Tasty.Bench.Fit.Complexity (+ Complexity (..),+ Measurement (..),+ guessComplexity,+ evalComplexity,++ -- * Predicates+ isConstant,+ isLogarithmic,+ isLinear,+ isLinearithmic,+ isQuadratic,+ isCubic,+) where++import Control.DeepSeq (NFData)+import Data.List (intercalate, minimumBy)+import Data.List.Infinite (Infinite (..), (...))+import qualified Data.List.NonEmpty as NE+import Data.Map (Map)+import qualified Data.Map as M+import Data.Ord (comparing)+import GHC.Generics (Generic)+import Math.Regression.Simple (+ Fit (..),+ V2 (..),+ levenbergMarquardt1WithYerrors,+ levenbergMarquardt2WithYerrors,+ linear,+ )+import Text.Printf (printf)+import Prelude hiding (log)+import qualified Prelude as P++#ifdef DEBUG+import Debug.Trace+#endif++log :: Word -> Double+log x = if x >= 1 then P.log (d x) else 0++-- | 'Complexity' @a@ @b@ @k@ represents a time complexity+-- \( k \, x^a \log^b x \), where \( x \) is problem's size.+data Complexity = Complexity+ { cmplVarPower :: !Double+ , cmplLogPower :: !Word+ , cmplMultiplier :: !Double+ }+ deriving (Eq, Ord, Generic)++instance NFData Complexity++-- | Is the complexity \( f(x) = k \)?+isConstant :: Complexity -> Bool+isConstant = \case+ Complexity {cmplVarPower = 0, cmplLogPower = 0} -> True+ _ -> False++-- | Is the complexity \( f(x) = k \log x \)?+isLogarithmic :: Complexity -> Bool+isLogarithmic = \case+ Complexity {cmplVarPower = 0, cmplLogPower = 1} -> True+ _ -> False++-- | Is the complexity \( f(x) = k \, x \)?+isLinear :: Complexity -> Bool+isLinear = \case+ Complexity {cmplVarPower = 1, cmplLogPower = 0} -> True+ _ -> False++-- | Is the complexity \( f(x) = k \, x \log x \)?+isLinearithmic :: Complexity -> Bool+isLinearithmic = \case+ Complexity {cmplVarPower = 1, cmplLogPower = 1} -> True+ _ -> False++-- | Is the complexity \( f(x) = k \, x^2 \)?+isQuadratic :: Complexity -> Bool+isQuadratic = \case+ Complexity {cmplVarPower = 2, cmplLogPower = 0} -> True+ _ -> False++-- | Is the complexity \( f(x) = k \, x^3 \)?+isCubic :: Complexity -> Bool+isCubic = \case+ Complexity {cmplVarPower = 3, cmplLogPower = 0} -> True+ _ -> False++instance Show Complexity where+ show Complexity {..} =+ intercalate " * " $+ filter+ (not . null)+ [ case cmplMultiplier of+ 1 -> ""+ _ -> printf "%.2g" cmplMultiplier+ , case cmplVarPower of+ 0 -> ""+ 1 -> "x"+ _ -> "x ^ " <> round3 cmplVarPower+ , case cmplLogPower of+ 0 -> ""+ 1 -> "log x"+ _ -> "(log x) ^ " <> show cmplLogPower+ ]+ where+ round3 :: Double -> String+ round3 x = if x == d x' then show x' else printf "%.3f" x+ where+ x' :: Word+ x' = round x++-- | Evaluate time complexity for a given size of the problem.+evalComplexity :: Complexity -> Word -> Double+evalComplexity Complexity {..} x =+ cmplMultiplier * d x ** cmplVarPower * log x ^ cmplLogPower++bestOf :: [(Complexity, Double)] -> Complexity+bestOf = fst . minimumBy (comparing weigh)+ where+ weigh (Complexity {..}, wssr) =+ wssr+ * powPenalty+ -- Penalty for high power of logarithm.+ * d (max 1 cmplLogPower)+ where+ -- Penalty for non-integer power.+ powPenalty :: Double+ powPenalty = case abs (cmplVarPower - d (round cmplVarPower)) of+ 0 -> 1+ -- Severe penalty for almost integer powers+ diff ->+ if diff < 0.05+ then 100+ else (if diff < 0.15 then 32 else 10)++-- | Represents a time measurement for a given problem's size.+data Measurement = Measurement+ { measTime :: !Double+ , measStDev :: !Double+ }+ deriving (Eq, Ord, Generic)++instance Show Measurement where+ show (Measurement t err) = printf "%.3g ± %.3g" t err++instance NFData Measurement++-- | 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 non-negative.+-- * 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](https://en.wikipedia.org/wiki/Time_complexity#Superpolynomial_time)+-- and higher classes of complexity.+guessComplexity :: Map Word Measurement -> Complexity+guessComplexity xys =+ trace'+ ("guessComplexity " ++ show (M.assocs xys))+ bestOf+ (takeUntilLocalMin cmpls)+ where+ cmpls :: Infinite ((Complexity, Double), (Complexity, Double))+ cmpls = fmap (guessComplexityForFixedLog xys) (0 ...)++ takeUntilLocalMin+ :: Infinite ((Complexity, Double), (Complexity, Double))+ -> [(Complexity, Double)]+ takeUntilLocalMin ((c1, c2) :< (c3, c4) :< cs)+ | snd c1 > snd c3 || snd c2 > snd c4 =+ c1 : c2 : takeUntilLocalMin ((c3, c4) :< cs)+ | otherwise =+ [c1, c2]++guessComplexityForFixedLog+ :: Map Word Measurement+ -> Word+ -> ((Complexity, Double), (Complexity, Double))+guessComplexityForFixedLog xys logPow = trace' msg res+ where+ -- varPow might be negative here, so always pass it through mkCmpl+ V2 _ varPow = guessComplexityWithoutLog xys logPow+ mkCmpl varPow' = guessComplexityForFixedPowAndLog xys varPow' logPow+ res@((res1, wssr1), (res2, wssr2)) =+ (mkCmpl (max 0 varPow), mkCmpl (d (round varPow)))++ msg =+ printf+ "forFixedLog:\n\t%s, RSS %.4g\n\t%s, RSS %.4g"+ (show res1)+ wssr1+ (show res2)+ wssr2++guessComplexityWithoutLog :: Map Word Measurement -> Word -> V2+guessComplexityWithoutLog (M.assocs -> xys) logPow = finish+ where+ -- Fit y_i ~ a x_i^b, which is equivalent to log y_i ~ log a + b log x_i.+ -- This is not ideal, because minimizing the sum of (log y_i - log a - b log x_i) ^ 2+ -- is not equivalent to minimizing the sum of (y_i - a * x_i^b) ^ 2, but close enough,+ -- so we are going to use it as a starting point for Levenberg-Marquardt.+ V2 b0 la0 =+ linear (\(x, Measurement y _) -> (log x, P.log (y / log x ^ logPow))) xys+ start = V2 (exp la0) (max 0 b0)++ Fit {fitParams = finish} =+ NE.last $+ levenbergMarquardt2WithYerrors+ ( \(V2 mult varPow) (x, Measurement y err) ->+ ( y+ , mult * d x ** varPow * log x ^ logPow+ , V2+ (d x ** varPow * log x ^ logPow)+ (mult * d x ** varPow * log x ^ (logPow + 1))+ , err+ )+ )+ start+ xys++guessComplexityForFixedPowAndLog+ :: Map Word Measurement+ -> Double+ -> Word+ -> (Complexity, Double)+guessComplexityForFixedPowAndLog (M.assocs -> xys) varPow logPow = (res, wssr)+ where+ -- We want to find a which minimizes \sum_i (y_i - a f(x_i))^2 for f(x) = x^b * log^c x.+ -- Then d/da = 0 means that \sum_i (2 a f(x_i)^2 - 2 f(x_i) y_i) = 0+ -- or equivalently a = \sum_i f(x_i) y_i / \sum_i x_i^2.+ eval x = d x ** varPow * log x ^ logPow+ sumXY = sum $ map (\(x, Measurement y _) -> eval x * y) xys+ sumX2 = sum $ map (\(x, _) -> eval x ** 2) xys+ start = sumXY / sumX2++ ft =+ NE.last $+ levenbergMarquardt1WithYerrors+ ( \mult (x, Measurement y err) ->+ ( y+ , mult * d x ** varPow * log x ^ logPow+ , d x ** varPow * log x ^ logPow+ , err+ )+ )+ start+ xys+ res =+ Complexity+ { cmplMultiplier = fitParams ft+ , cmplVarPower = varPow+ , cmplLogPower = logPow+ }+ wssr = fitWSSR ft++d :: Word -> Double+d = fromIntegral++trace' :: String -> b -> b+#ifdef DEBUG+trace' = trace+#else+trace' = const id+#endif
+ tasty-bench-fit.cabal view
@@ -0,0 +1,63 @@+cabal-version: 2.0+name: tasty-bench-fit+version: 0.1+license: MIT+license-file: LICENSE+maintainer: andrew.lelechenko@gmail.com+author: Bodigrim+tested-with:+ ghc ==9.6.1 ghc ==9.4.4 ghc ==9.2.7 ghc ==9.0.2 ghc ==8.10.7+ ghc ==8.8.4 ghc ==8.6.5 ghc ==8.4.4++homepage: https://github.com/Bodigrim/tasty-bench-fit+synopsis: Determine time complexity of a given function+description:+ Benchmark a given function for variable input sizes+ and find out its time complexity.++category: Development+build-type: Simple+extra-doc-files:+ CHANGELOG.md+ README.md++source-repository head+ type: git+ location: https://github.com/Bodigrim/tasty-bench-fit++flag debug+ description: Emit ongoing diagnostic information.+ default: False+ manual: True++library+ exposed-modules: Test.Tasty.Bench.Fit+ hs-source-dirs: src+ other-modules: Test.Tasty.Bench.Fit.Complexity+ default-language: Haskell2010+ ghc-options: -Wall+ build-depends:+ base >=4.11 && <5,+ containers >=0.5.11 && <0.7,+ deepseq >=1.4 && <1.5,+ infinite-list >=0.1 && <0.2,+ tasty >=1.4 && <1.5,+ tasty-bench >=0.3.4 && <0.4,+ regression-simple >=0.2.1 && <0.3++ if flag(debug)+ cpp-options: -DDEBUG++test-suite tasty-bench-fit-test+ type: exitcode-stdio-1.0+ main-is: Main.hs+ hs-source-dirs: test+ default-language: Haskell2010+ build-depends:+ base,+ containers <0.7,+ tasty,+ tasty-bench,+ tasty-bench-fit,+ tasty-quickcheck <0.11,+ tasty-expected-failure <0.13
+ test/Main.hs view
@@ -0,0 +1,132 @@+{-# LANGUAGE LambdaCase #-}++module Main+ ( main+ ) where++import Data.List (nub, sort)+import qualified Data.Map as M+import Test.Tasty+import Test.Tasty.Bench (RelStDev(..))+import Test.Tasty.Bench.Fit+import Test.Tasty.ExpectedFailure+import Test.Tasty.QuickCheck++main :: IO ()+main = defaultMain $ testGroup "All"+ [ testShow+ , testGuess+ , testProperty "sum is linear" $ ioProperty $ do+ c <- fit $ mkFitConfig (\x -> sum [1..x]) (10, 10000)+ pure $ counterexample (show c) $ isLinear c+ -- , testProperty "nub is quadratic" $ ioProperty $ do+ -- c <- fit $ mkFitConfig (\x -> nub [1..x]) (10, 10000)+ -- pure $ counterexample (show c) $ isQuadratic c+ -- , testProperty "sort is linearithmic" $ ioProperty $ do+ -- c <- fit $ (mkFitConfig (\x -> Data.List.sort $ take (fromIntegral x) $+ -- iterate (\n -> n * 6364136223846793005 + 1) (1 :: Word)) (10, 100000))+ -- pure $ counterexample (show c) $ isLinearithmic c+ ]++testShow :: TestTree+testShow = testGroup "Show"+ [ testProperty "Constant" $+ show (Complexity {cmplMultiplier = 5.978911764705882e-9, cmplVarPower = 0, cmplLogPower = 0}) === "5.98e-9"+ , testProperty "Logarithmic" $+ show (Complexity {cmplMultiplier = 5.968840304461118e-8, cmplVarPower = 0, cmplLogPower = 1}) === "5.97e-8 * log x"+ , testProperty "Logarithmic2" $+ show (Complexity {cmplMultiplier = 5.793061712300056e-8, cmplVarPower = 0, cmplLogPower = 2}) === "5.79e-8 * (log x) ^ 2"+ , testProperty "Sqrt" $+ show (Complexity {cmplMultiplier = 8.974841776295381e-10, cmplVarPower = 0.4690504530830262, cmplLogPower = 0}) === "8.97e-10 * x ^ 0.469"+ , testProperty "Linear" $+ show (Complexity {cmplMultiplier = 5.793579541827657e-10, cmplVarPower = 1, cmplLogPower = 0}) === "5.79e-10 * x"+ , testProperty "Linearithmic" $+ show (Complexity {cmplMultiplier = 1.354437369864389e-9, cmplVarPower = 1, cmplLogPower = 1}) === "1.35e-9 * x * log x"+ , testProperty "Linearithmic2" $+ show (Complexity {cmplMultiplier = 5.754981209362351e-10, cmplVarPower = 1, cmplLogPower = 2}) === "5.75e-10 * x * (log x) ^ 2"+ , testProperty "Quadratic" $+ show (Complexity {cmplMultiplier = 5.763471892706858e-10, cmplVarPower = 2, cmplLogPower = 0}) === "5.76e-10 * x ^ 2"+ , testProperty "Cubic" $+ show (Complexity {cmplMultiplier = 5.736276961481605e-10, cmplVarPower = 3, cmplLogPower = 0}) === "5.74e-10 * x ^ 3"+ ]++testGuess :: TestTree+testGuess = testGroup "Guess"+ [ testProperty "Constant" $ checkComplexity isConstant+ [(10,5.881e-9),(15,6.05e-9),(20,6.0e-9),(30,5.938e-9),(40,6.074e-9),(61,6.194e-9),(80,6.282e-9),(122,6.105e-9),(160,6.108e-9),(244,5.927e-9),(320,5.93e-9),(488,5.949e-9),(640,5.9e-9),(976,5.892e-9),(1280,5.918e-9),(1953,5.901e-9),(2560,5.918e-9),(3906,5.947e-9),(5120,5.901e-9),(7812,5.906e-9),(10240,5.907e-9),(15625,5.95e-9),(20480,5.982e-9),(31250,5.993e-9),(40960,5.946e-9),(62500,5.901e-9),(81920,5.922e-9),(125000,5.93e-9),(163840,5.928e-9),(250000,6.228e-9),(327680,5.961e-9),(500000,6.025e-9),(655360,5.929e-9),(1000000,5.96e-9)]+ , testProperty "Logarithmic" $ checkComplexity isLogarithmic+ [(10,1.54191e-7),(15,1.7357e-7),(20,1.90191e-7),(30,2.20661e-7),(40,2.31167e-7),(61,2.55251e-7),(80,2.71941e-7),(122,2.97561e-7),(160,3.1158e-7),(244,3.38001e-7),(320,3.50998e-7),(488,3.7589e-7),(640,3.93221e-7),(976,4.15118e-7),(1280,4.30965e-7),(1953,4.5525e-7),(2560,4.70494e-7),(3906,4.98164e-7),(5120,5.1214e-7),(7812,5.50508e-7),(10240,5.51175e-7),(15625,5.75977e-7),(20480,5.98614e-7),(31250,6.14841e-7),(40960,6.32332e-7),(62500,6.60092e-7),(81920,6.67221e-7),(125000,6.94264e-7),(163840,7.08961e-7),(250000,7.3384e-7),(327680,7.48206e-7),(500000,7.75123e-7),(655360,7.90332e-7),(1000000,8.12204e-7)]+ , testProperty "Logarithmic2" $ checkComplexity isLogarithmic2+ [(10,3.2606e-7),(15,4.41324e-7),(20,5.44409e-7),(30,6.84828e-7),(40,8.1833e-7),(61,1.017501e-6),(80,1.155663e-6),(122,1.376089e-6),(160,1.527048e-6),(244,1.783776e-6),(320,1.963467e-6),(488,2.255293e-6),(640,2.482833e-6),(976,2.813505e-6),(1280,2.995748e-6),(1953,3.392042e-6),(2560,3.609635e-6),(3906,4.011062e-6),(5120,4.266189e-6),(7812,4.679779e-6),(10240,4.963383e-6),(15625,5.409899e-6),(20480,5.70888e-6),(31250,6.266229e-6),(40960,6.554699e-6),(62500,7.130075e-6),(81920,7.429367e-6),(125000,7.953335e-6),(163840,8.318951e-6),(250000,8.901232e-6),(327680,9.295489e-6),(500000,9.926727e-6),(655360,1.034403e-5),(1000000,1.0997949e-5)]+ , testProperty "Logarithmic6" $ checkComplexity isLogarithmic6+ [(10,8.628924e-6),(15,2.2718701e-5),(20,4.1468945e-5),(30,8.90083e-5),(40,1.44395898e-4),(61,2.76677148e-4),(80,4.07342187e-4),(122,7.0664375e-4),(160,9.83112109e-4),(244,1.594223437e-3),(320,2.119596093e-3),(488,3.235329687e-3),(640,4.227651562e-3),(976,6.111234375e-3),(1280,7.672078125e-3),(1953,1.08728375e-2),(2560,1.344470625e-2),(3906,1.8441325e-2),(5120,2.2353e-2),(7812,2.97963125e-2),(10240,3.5516875e-2),(15625,4.6447275e-2),(20480,5.477735e-2),(31250,7.038505e-2),(40960,8.21456e-2),(62500,0.10381915),(81920,0.1200662),(125000,0.1495741),(163840,0.1715495),(250000,0.2110635),(327680,0.2401788),(500000,0.2922768),(655360,0.3303902),(1000000,0.3993154)]+ , testProperty "Sqrt" $ checkComplexity isSqrt+ [(10,9.179e-9),(15,9.129e-9),(20,9.721e-9),(30,1.0412e-8),(40,1.0851e-8),(61,1.1441e-8),(80,1.2102e-8),(122,1.3903e-8),(160,1.4497e-8),(244,1.6241e-8),(320,1.746e-8),(488,2.0412e-8),(640,2.2189e-8),(976,2.5812e-8),(1280,2.7865e-8),(1953,3.3284e-8),(2560,3.5825e-8),(3906,4.7608e-8),(5120,5.3362e-8),(7812,6.3584e-8),(10240,7.0786e-8),(15625,8.4566e-8),(20480,9.4943e-8),(31250,1.13772e-7),(40960,1.29419e-7),(62500,1.56251e-7),(81920,1.76977e-7),(125000,2.16214e-7),(163840,2.46864e-7),(250000,3.01931e-7),(327680,3.43224e-7),(500000,4.24035e-7),(655360,4.80871e-7),(1000000,5.90708e-7)]+ , testProperty "Linear" $ checkComplexity isLinear+ [(10,1.2137e-8),(19,1.7499e-8),(20,1.8083e-8),(39,2.849e-8),(40,2.9045e-8),(78,5.6604e-8),(80,5.7759e-8),(156,1.01422e-7),(160,1.03728e-7),(312,1.9109e-7),(320,1.962e-7),(625,3.73153e-7),(640,3.81767e-7),(1250,7.34564e-7),(1280,7.49969e-7),(2500,1.469915e-6),(2560,1.505307e-6),(5000,2.896041e-6),(5120,2.967195e-6),(10000,5.777413e-6)]+ , testProperty "Linearithmic" $ checkComplexity isLinearithmic+ [(10,2.2405e-8),(19,4.8021e-8),(20,5.0446e-8),(39,9.8831e-8),(40,1.02064e-7),(78,2.13687e-7),(80,2.20389e-7),(156,4.71726e-7),(160,5.15425e-7),(312,1.094096e-6),(320,1.141173e-6),(625,2.407279e-6),(640,2.426035e-6),(1250,5.195858e-6),(1280,5.407168e-6),(2500,1.1405377e-5),(2560,1.1602465e-5),(5000,2.4561621e-5),(5120,2.5307434e-5),(10000,5.5566052e-5)]+ , testProperty "Linearithmic2" $ checkComplexity isLinearithmic2+ [(10,4.7181e-8),(19,1.12792e-7),(20,1.22449e-7),(39,3.20318e-7),(40,3.32249e-7),(78,8.75328e-7),(80,9.04648e-7),(156,2.329658e-6),(160,2.419274e-6),(312,6.00791e-6),(320,6.189526e-6),(625,1.5036761e-5),(640,1.5424169e-5),(1250,3.6494995e-5),(1280,3.7753466e-5),(2500,8.7988085e-5),(2560,9.1063623e-5),(5000,2.09651562e-4),(5120,2.13942675e-4),(10000,4.88197265e-4)]+ , testProperty "Quadratic" $ checkComplexity isQuadratic+ [(10,6.9102e-8),(15,1.41744e-7),(20,2.42625e-7),(31,5.7397e-7),(40,9.56442e-7),(62,2.248535e-6),(80,3.740179e-6),(125,9.10119e-6),(160,1.4752551e-5),(250,3.5977856e-5),(320,5.9150854e-5),(500,1.44069628e-4),(640,2.36670605e-4),(1000,5.76093359e-4)]+ , testProperty "Quadrithmic4" $ checkComplexity isQuadrithmic4+ [(5,3.5023e-8),(9,1.59489e-7),(10,2.12688e-7),(19,1.627995e-6),(20,1.919146e-6),(39,1.5753015e-5),(40,1.704226e-5),(78,1.25921337e-4),(80,1.35570312e-4),(156,9.08977343e-4),(160,9.75295703e-4),(312,6.07931875e-3),(320,6.496996875e-3),(625,3.86003e-2),(640,4.0853375e-2),(1250,0.2314005),(1280,0.2456381),(2500,1.339004),(2560,1.4231234),(5000,7.528904)]+ , testProperty "Cubic" $ checkComplexity isCubic+ [(10,5.98066e-7),(11,7.7601e-7),(20,4.609741e-6),(23,6.99185e-6),(40,3.6676177e-5),(46,5.5854089e-5),(80,2.92877148e-4),(93,4.66834472e-4),(160,2.344111718e-3),(187,3.740370312e-3),(320,1.8751396875e-2),(375,3.018281875e-2),(640,0.150031325),(750,0.2414234),(1280,1.1982404),(1500,1.9280254),(2560,9.5926602),(3000,15.4408018)]+ , testProperty "Quartic" $ checkComplexity isQuartic+ [(5,1.6603e-8),(7,3.0392e-8),(10,9.1955e-8),(15,3.25706e-7),(20,9.76705e-7),(31,5.34298e-6),(40,1.472517e-5),(62,8.4625488e-5),(80,2.34295019e-4),(125,1.395396875e-3),(160,3.74655e-3),(250,2.23739875e-2),(320,6.0027625e-2),(500,0.357446),(640,0.9591132),(1000,5.725087)]++ , testProperty "Karatsuba" $ checkComplexity isKaratsuba+ [(10,4.8364e-8),(12,6.0228e-8),(20,9.9186e-8),(24,1.21309e-7),(40,2.31972e-7),(48,2.9911e-7),(80,6.2843e-7),(97,8.46736e-7),(160,1.846619e-6),(195,2.503655e-6),(320,5.42057e-6),(390,7.376403e-6),(640,1.6124441e-5),(781,2.2078021e-5),(1280,4.8210919e-5),(1562,6.6098962e-5),(2560,1.44684423e-4),(3125,1.98921875e-4),(5120,4.34806054e-4),(6250,5.9602539e-4),(10240,1.301581445e-3),(12500,1.784770312e-3),(20480,3.903389843e-3),(25000,5.354964062e-3),(40960,1.171065625e-2),(50000,1.604174375e-2),(81920,3.509155625e-2),(100000,4.82393125e-2)]+ , testProperty "Strassen" $ checkComplexity isStrassen+ [(10,4.02343e-7),(11,5.14162e-7),(20,2.64022e-6),(23,3.884503e-6),(40,1.8058444e-5),(46,2.6682556e-5),(80,1.258875e-4),(93,1.92064208e-4),(160,8.8356914e-4),(187,1.362714843e-3),(320,6.163835937e-3),(375,9.710895312e-3),(640,4.32488375e-2),(750,6.8603265625e-2),(1280,0.30328925),(1500,0.4761277),(2560,2.1247246),(3000,3.3290002)]++ , testProperty "Linear again" $ checkComplexity isLinear+ [(1,6.9753e-8),(2,1.28492e-7),(4,2.46261e-7),(5,3.05419e-7),(8,4.82596e-7),(10,6.01227e-7)]+ ]++checkComplexity :: (Complexity -> Bool) -> [(Word, Double)] -> Property+checkComplexity p xys = counterexample (show cmpl) (p cmpl)+ where+ cmpl = guessComplexity $ fmap (`Measurement` 1) $ M.fromList xys++isSqrt :: Complexity -> Bool+isSqrt = \case+ Complexity {cmplVarPower = varPow, cmplLogPower = 0} -> varPow > 0.4 && varPow < 0.6+ _ -> False++isLogarithmic2 :: Complexity -> Bool+isLogarithmic2 = \case+ Complexity {cmplVarPower = 0, cmplLogPower = 2} -> True+ _ -> False++isLogarithmic6 :: Complexity -> Bool+isLogarithmic6 = \case+ Complexity {cmplVarPower = 0, cmplLogPower = 6} -> True+ _ -> False++isLinearithmic2 :: Complexity -> Bool+isLinearithmic2 = \case+ Complexity {cmplVarPower = 1, cmplLogPower = 2} -> True+ _ -> False++isQuadrithmic4 :: Complexity -> Bool+isQuadrithmic4 = \case+ Complexity {cmplVarPower = 2, cmplLogPower = 4} -> True+ _ -> False++isQuartic :: Complexity -> Bool+isQuartic = \case+ Complexity {cmplVarPower = 4, cmplLogPower = 0} -> True+ _ -> False++isKaratsuba :: Complexity -> Bool+isKaratsuba = \case+ Complexity {cmplVarPower = varPow, cmplLogPower = 0} -> varPow > 1.5 && varPow < 1.7+ _ -> False++isStrassen :: Complexity -> Bool+isStrassen = \case+ Complexity {cmplVarPower = varPow, cmplLogPower = 0} -> varPow > 2.7 && varPow < 2.9+ _ -> False