sobre - Encontrar la complejidad de las funciones de Haskell.

haskell basico

Question

¿Cómo puedo encontrar la complejidad (en términos de big-O ) para diferentes funciones de Haskell?

Por ejemplo, ¿cuál es la complejidad de las subsequences ?

Answer 1

Solo puede calcular la complejidad exacta de una función mirando el código. Sin embargo, puedes estimarlo usando criterion .

Por ejemplo, el siguiente programa estima la complejidad de la subsequence en función de la longitud de la lista.

module Main where

import Criterion (bench, nf)
import Criterion.Main (defaultMain)
import Data.List (subsequences)
import Control.DeepSeq (deepseq)

main = defaultMain (map createBenchmark [0, 2 .. 24])
    where
        createBenchmark n =
            let
                xs = replicate n ''x''
            in
                xs `deepseq` (bench (show n) $ nf subsequences xs)

Si lo compilas (con -O2 !) Y lo ejecutas con

./Main -u report

(o

./Main --csv report

en nuevas versiones de criterio)

obtendrá un archivo CSV con los datos (tiempo promedio, variación y otra información por ejecución).

Si traza esos datos, se dará cuenta de que es exponencial en n como lo muestra la siguiente sesión de gnuplot.

> f(x) = a * exp(b * x)
> fit f(x) ''report'' using ($0 * 2):2 every ::2 via a,b
...

Final set of parameters            Asymptotic Standard Error
=======================            ==========================

a               = 1.7153e-07       +/- 5.441e-09    (3.172%)
b               = 0.711104         +/- 0.001438     (0.2023%)


correlation matrix of the fit parameters:

               a      b      
a               1.000 
b              -1.000  1.000
> set log y
> set xlabel ''n''
> set ylabel ''mean time [s]''
> plot ''report'' using ($0 * 2):2 every ::2 with lp title ''data'', f(x) title ''fit''

a es aproximadamente cero, y b casi no tiene error. Así que es bastante seguro suponer que la complejidad es O (2 ^ n), porque e ^ 0.71 es casi exactamente 2.

Por supuesto, esta técnica supone que en realidad estás usando todo lo que devuelve la función. Si solo está accediendo al primer elemento de la lista devuelta, la complejidad será O (1) debido a una evaluación perezosa.

Es probable que pueda encontrar una manera de hacer que este programa sea independiente de la función para realizar un punto de referencia (al menos para las funciones que solo toman una lista). También hay algunas bibliotecas agradables de Haskell para trazar datos, por lo que no necesita depender de programas externos (desafortunadamente, como científico nunca usé nada más que gnuplot).