algorithm - Lazy La evaluación y la complejidad del tiempo

sorting haskell

Question

Estaba mirando la evaluación Lazy Non-Trivial de stackoverflow, que me llevó a la presentación de Keegan McAllister: ¿Por qué aprender Haskell ? En la diapositiva 8, muestra la función mínima, definida como:

minimum = head . sort

y declara que su complejidad es O (n). No entiendo por qué se dice que la complejidad es lineal si la clasificación por sustitución es O (nlog n). La clasificación a la que se hace referencia en la publicación no puede ser lineal, ya que no asume nada sobre los datos, ya que sería requerida por los métodos de clasificación lineal, como el conteo de ordenación.

¿La evaluación perezosa juega un papel misterioso aquí? Si es así, ¿cuál es la explicación detrás de esto?

Answer 1

En minimum = head . sort minimum = head . sort , el sort no se completará, porque no se hará por adelantado . El sort solo se realizará tanto como sea necesario para producir el primer elemento, exigido por la head .

En eg mergesort, al principio n números de la lista serán comparados por pares, luego los ganadores serán emparejados y comparados ( n/2 números), luego los nuevos ganadores ( n/4 ), etc. En total, O(n) comparaciones para producir el elemento mínimo.

mergesortBy less [] = []
mergesortBy less xs = head $ until (null.tail) pairs [[x] | x <- xs]
  where
    pairs (x:y:t) = merge x y : pairs t
    pairs xs      = xs
    merge (x:xs) (y:ys) | less y x  = y : merge (x:xs) ys
                        | otherwise = x : merge  xs (y:ys)
    merge  xs     []                = xs
    merge  []     ys                = ys

El código anterior se puede aumentar para etiquetar cada número que produce con una serie de comparaciones que entraron en su producción:

mgsort xs = go $ map ((,) 0) xs  where
  go [] = []
  go xs = head $ until (null.tail) pairs [[x] | x <- xs]   where
    ....
    merge ((a,b):xs) ((c,d):ys) 
            | (d < b)   = (a+c+1,d) : merge ((a+1,b):xs) ys    -- cumulative
            | otherwise = (a+c+1,b) : merge  xs ((c+1,d):ys)   --   cost
    ....

g n = concat [[a,b] | (a,b) <- zip [1,3..n] [n,n-2..1]]   -- a little scrambler

Al ejecutarlo durante varias longitudes de lista, vemos que de hecho es ~ n :

*Main> map (fst . head . mgsort . g) [10, 20, 40, 80, 160, 1600]
[9,19,39,79,159,1599]

Para ver si el código de clasificación en sí mismo es ~ n log n , lo cambiamos de modo que cada número producido lleva consigo solo su propio costo, y el costo total se calcula por suma en toda la lista ordenada:

    merge ((a,b):xs) ((c,d):ys) 
            | (d < b)   = (c+1,d) : merge ((a+1,b):xs) ys      -- individual
            | otherwise = (a+1,b) : merge  xs ((c+1,d):ys)     --   cost

Aquí están los resultados para listas de varias longitudes,

*Main> let xs = map (sum . map fst . mgsort . g) [20, 40, 80, 160, 320, 640]
[138,342,810,1866,4218,9402]

*Main> map (logBase 2) $ zipWith (/) (tail xs) xs
[1.309328,1.2439256,1.2039552,1.1766101,1.1564085]

Lo anterior muestra órdenes de crecimiento empíricos para aumentar las longitudes de la lista, n , que están disminuyendo rápidamente, como suele mostrarse mediante cálculos de ~ n log n . Ver también esta publicación en el blog . Aquí hay una verificación de correlación rápida:

*Main> let xs = [n*log n | n<- [20, 40, 80, 160, 320, 640]] in 
                                    map (logBase 2) $ zipWith (/) (tail xs) xs
[1.3002739,1.2484156,1.211859,1.1846942,1.1637106]

editar: La evaluación diferida puede verse metafóricamente como una especie de modismo de productor / consumidor ¹ , con almacenamiento de memoramización independiente como intermediario. Cualquier definición productiva que redactemos, define a un productor que producirá su producción, bit por bit, cuando lo exija su (s) consumidor (es), pero no antes. Todo lo que se produce se memoriza, de modo que si otro consumidor consume la misma producción a un ritmo diferente, accede al mismo almacenamiento, llenado previamente.

Cuando ya no quedan más consumidores que se refieran a una pieza de almacenamiento, se recolecta la basura. A veces, con las optimizaciones, el compilador puede eliminar por completo el almacenamiento intermedio, lo que elimina al intermediario.

¹ ver también: Simple Generators v. Lazy Evaluation por Oleg Kiselyov, Simon Peyton-Jones y Amr Sabry.

Answer 2

Has obtenido una buena cantidad de respuestas que abordan los detalles de la head . sort head . sort Solo agregaré un par de enunciados generales más.

Con una evaluación entusiasta, las complejidades computacionales de varios algoritmos se componen de una manera simple. Por ejemplo, el límite superior mínimo (LUB) para f . g f . g debe ser la suma de los LUB para f y g . Por lo tanto, puede tratar g como cuadros negros y razonar exclusivamente en términos de sus LUB.

Sin embargo, con una evaluación perezosa, f . g f . g puede tener un LUB mejor que la suma de LUBs de f y g . No puede usar el razonamiento de caja negra para probar el LUB; debes analizar las implementaciones y su interacción.

Por lo tanto, el hecho citado a menudo de que la complejidad de la evaluación perezosa es mucho más difícil de razonar que para una evaluación entusiasta. Solo piensa en lo siguiente. Supongamos que intentas mejorar la ejecución asintótica de un fragmento de código cuya forma es f . g f . g . En un lenguaje entusiasta, hay una estrategia obvia que puedes seguir para hacer esto: elige la más compleja de g , y mejora esa primero. Si tienes éxito en eso, tienes éxito en el f . g f . g tarea.

En un lenguaje perezoso, por otro lado, puede tener estas situaciones:

• Mejoras la más compleja de f y g , pero f . g f . g no mejora (o incluso empeora ).
• Puedes mejorar f . g f . g de maneras que no ayudan (o incluso empeoran ) f o g .

Answer 3

Inspirado por la respuesta de Paul Johnson, tracé las tasas de crecimiento para las dos funciones. Primero modifiqué su código para imprimir un personaje por comparación:

import System.Random
import Debug.Trace
import Data.List
import System.Environment

rs n = do
    gen <- newStdGen
    let ns = randoms gen :: [Int]
    return $ take n ns

cmp1 x y = trace "*" $ compare x y
cmp2 x y = trace "#" $ compare x y

main = do
    n <- fmap (read . (!!0)) getArgs
    xs <- rs n
    print "Sorting entire list"
    print $ sortBy cmp1 xs

    print "Head of sorted list"
    print $ head $ sortBy cmp2 xs

Contando los caracteres * y # , podemos muestrear los recuentos de comparación en puntos igualmente espaciados (disculpe mi pitón):

import matplotlib.pyplot as plt
import numpy as np
import envoy

res = []
x = range(10,500000,10000)
for i in x:
    r = envoy.run(''./sortCount %i'' % i)
    res.append((r.std_err.count(''*''), r.std_err.count(''#'')))

plt.plot(x, map(lambda x:x[0], res), label="sort")
plt.plot(x, map(lambda x:x[1], res), label="minimum")
plt.plot(x, x*np.log2(x), label="n*log(n)")
plt.plot(x, x, label="n")
plt.legend()
plt.show()

Ejecutar el script nos daría el siguiente gráfico:

La pendiente de la línea inferior es ..

>>> import numpy as np
>>> np.polyfit(x, map(lambda x:x[1], res), deg=1)
array([  1.41324057, -17.7512292 ])

..1.41324057 (asumiendo que es una función lineal)

Answer 4

La explicación depende de la implementación de sort , y para algunas implementaciones no será verdad. Por ejemplo, con un tipo de inserción que se inserta al final de la lista, la evaluación diferida no ayuda. Así que vamos a elegir una implementación a mirar, y por simplicidad, use la opción de ordenar:

sort [] = []
sort (x:xs) = m : sort (delete m (x:xs)) 
  where m = foldl (/x y -> if x < y then x else y) x xs

La función claramente usa O (n ^ 2) tiempo para ordenar la lista, pero como head solo necesita el primer elemento de la lista, ¡ sort (delete x xs) nunca se evalúa!

Answer 5

No es tan misterioso. ¿Qué cantidad de una lista necesita ordenar para entregar el primer elemento? Necesita encontrar el elemento mínimo, que se puede hacer fácilmente en tiempo lineal. Da la casualidad que para algunas implementaciones de evaluación de sort perezoso hará esto por usted.

Answer 6

Suponga que el minimum'' :: (Ord a) => [a] -> (a, [a]) es una función que devuelve el elemento más pequeño de una lista junto con la lista con ese elemento eliminado. Claramente, esto se puede hacer en el tiempo O (n). Si luego defines sort como

sort :: (Ord a) => [a] -> [a]
sort xs = xmin:(sort xs'')
    where
      (xmin, xs'') = minimum'' xs

entonces la evaluación diferida significa que en (head . sort) xs solo se calcula el primer elemento. Este elemento es, como verá, simplemente (el primer elemento de) el par minimum'' xs , que se calcula en O (n) tiempo.

Por supuesto, como señala Delnan, la complejidad depende de la implementación del sort .

Answer 7

Una forma interesante de ver esto en la práctica es rastrear la función de comparación.

import Debug.Trace
import Data.List

myCmp x y = trace (" myCmp " ++ show x ++ " " ++ show y) $ compare x y

xs = [5,8,1,3,0,54,2,5,2,98,7]

main = do
    print "Sorting entire list"
    print $ sortBy myCmp xs

    print "Head of sorted list"
    print $ head $ sortBy myCmp xs

Primero, observe la forma en que el resultado de la lista completa se entrelaza con los mensajes de seguimiento. En segundo lugar, observe cómo los mensajes de seguimiento son similares cuando se trata simplemente de calcular la cabeza.

Acabo de ejecutar esto a través de Ghci, y no es exactamente O (n): se necesitan 15 comparaciones para encontrar el primer elemento, no los 10 que deberían ser necesarios. Pero sigue siendo menor que O (n log n).

Editar: como Vitus señala a continuación, tomar 15 comparaciones en lugar de 10 no es lo mismo que decir que no es O (n). Solo quise decir que toma más que el mínimo teórico.