performance - muestrales - introduccion ala probabilidad y estadistica mendenhall 13th pdf

¿Por qué las listas de diferencias son más eficientes que la concatenación regular?

Question

Actualmente estoy trabajando en el libro Learn you a haskell en línea, y he llegado a un capítulo donde el autor explica que algunas concatenaciones de listas pueden ser ineficaces: por ejemplo

((((a ++ b) ++ c) ++ d) ++ e) ++ f

Es supuestamente ineficiente. La solución que se le ocurre al autor es usar ''listas de diferencias'' definidas como

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (/xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (/xs -> f (g xs))

Estoy luchando para entender por qué DiffList es más eficiente computacionalmente que una simple concatenación en algunos casos. ¿Podría alguien explicarme en términos simples por qué el ejemplo anterior es tan ineficiente, y de qué manera el DiffList resuelve este problema?

Answer 1

El problema en

((((a ++ b) ++ c) ++ d) ++ e) ++ f

es el anidamiento Las aplicaciones de (++) están anidadas a la izquierda, y eso es malo, anidando a la derecha

a ++ (b ++ (c ++ (d ++ (e ++f))))

no sería un problema Eso es porque (++) se define como

[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

para encontrar qué ecuación usar, la implementación debe sumergirse en el árbol de expresiones

             (++)
             /  /
          (++)   f
          /  /
       (++)   e
       /  /
    (++)   d
    /  /
 (++)   c
 /  /
a    b

hasta que descubra si el operando izquierdo está vacío o no. Si no está vacío, se toma su cabeza y se burbujea en la parte superior, pero la cola del operando izquierdo se deja intacta, por lo que cuando se solicita el siguiente elemento de la concatenación, el mismo procedimiento comienza de nuevo.

Cuando las concatenaciones están anidadas a la derecha, el operando izquierdo de (++) está siempre en la parte superior, y la comprobación de vacío / burbujeo en la cabeza es O (1).

Pero cuando las concatenaciones se anidan a la izquierda, n capas profundas, para llegar al primer elemento, se deben atravesar n nodos del árbol, para cada elemento del resultado (procedente de la primera lista, n-1 para los que provienen de la segunda etc.).

Consideremos a = "hello" en

hi = ((((a ++ b) ++ c) ++ d) ++ e) ++ f

y queremos evaluar take 5 hi . Entonces, primero, debe verificarse si

(((a ++ b) ++ c) ++ d) ++ e

esta vacio. Para eso, debe verificarse si

((a ++ b) ++ c) ++ d

esta vacio. Para eso, debe verificarse si

(a ++ b) ++ c

esta vacio. Para eso, debe verificarse si

a ++ b

esta vacio. Para eso, debe verificarse si

a

esta vacio. Uf. No lo es, entonces podemos burbujear nuevamente, ensamblando

a ++ b                             = ''h'':("ello" ++ b)
(a ++ b) ++ c                      = ''h'':(("ello" ++ b) ++ c)
((a ++ b) ++ c) ++ d               = ''h'':((("ello" ++ b) ++ c) ++ d)
(((a ++ b) ++ c) ++ d) ++ e        = ''h'':(((("ello" ++ b) ++ c) ++ d) ++ e)
((((a ++ b) ++ c) ++ d) ++ e) ++ f = ''h'':((((("ello" ++ b) ++ c) ++ d) ++ e) ++ f)

y para la ''e'' , debemos repetir, y para la ''l'' también ...

Dibujando una parte del árbol, el burbujeo es así:

            (++)
            /  /
         (++)   c
         /  /
''h'':"ello"   b

se convierte en primer

     (++)
     /  /
   (:)   c
  /   /
''h''   (++)
      /  /
 "ello"   b

y entonces

      (:)
      / /
    ''h'' (++)
        /  /
     (++)   c
     /  /
"ello"   b

todo el camino de regreso a la cima. La estructura del árbol que se convierte en el hijo correcto del nivel superior (:) es exactamente igual a la estructura del árbol original, a menos que la lista de la izquierda esté vacía, cuando el

 (++)
 /  /
[]   b

los nodos se colapsan a solo b .

Por lo tanto, si tiene concatenaciones anidadas a la izquierda de listas cortas, la concatenación se vuelve cuadrática porque para obtener el encabezado de la concatenación hay una operación O (profundidad de anidación). En general, la concatenación de un anidado a la izquierda

(...((a_d ++ a_{d-1}) ++ a_{d-2}) ...) ++ a_2) ++ a_1

es O(sum [i * length a_i | i <- [1 .. d]]) para evaluar completamente.

Con listas de diferencias (sin el envoltorio de tipo nuevo para la simplicidad de la exposición), no es importante si las composiciones están anidadas a la izquierda

((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++)

o anidado en la derecha. Una vez que haya atravesado el anidamiento para alcanzar (a ++) , ese (++) se izará a la parte superior del árbol de expresiones, por lo que obtener cada elemento de a es nuevamente O (1).

De hecho, toda la composición se reasocia con listas de diferencias, tan pronto como requiera el primer elemento,

((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++) $ f

se convierte

((((a ++) . (b ++)) . (c ++)) . (d ++)) $ (e ++) f
(((a ++) . (b ++)) . (c ++)) $ (d ++) ((e ++) f)
((a ++) . (b ++)) $ (c ++) ((d ++) ((e ++) f))
(a ++) $ (b ++) ((c ++) ((d ++) ((e ++) f)))
a ++ (b ++ (c ++ (d ++ (e ++ f))))

y después de eso, cada lista es el operando izquierdo inmediato del nivel superior (++) después de que se haya consumido la lista anterior.

Lo importante en esto es que la función de antependencia (a ++) puede comenzar a producir su resultado sin inspeccionar su argumento, de modo que la reasociación de

             ($)
             / /
           (.)  f
           / /
         (.) (e ++)
         / /
       (.) (d ++)
       / /
     (.) (c ++)
     / /
(a ++) (b ++)

vía

           ($)---------
           /           /
         (.)           ($)
         / /           / /
       (.) (d ++) (e ++)  f
       / /
     (.) (c ++)
     / /
(a ++) (b ++)

a

     ($)
     / /
(a ++) ($)
       / /
  (b ++) ($)
         / /
    (c ++) ($)
           / /
      (d ++) ($)
             / /
        (e ++)  f

no necesita saber nada sobre las funciones compuestas de la lista final f , por lo que es solo una reescritura O(depth) . Entonces el nivel superior

     ($)
     / /
(a ++)  stuff

se convierte

 (++)
 /  /
a    stuff

y todos los elementos de a se pueden obtener en un solo paso. En este ejemplo, donde tuvimos un anidado de izquierda puro, solo se necesita una nueva reescritura. Si en lugar de (por ejemplo) (d ++) la función en ese lugar hubiera sido una composición anidada a la izquierda, (((g ++) . (h ++)) . (i ++)) . (j ++) (((g ++) . (h ++)) . (i ++)) . (j ++) , la reasociación de nivel superior dejaría intacta y esto se reasociaría cuando se convierta en el operando izquierdo del nivel superior ($) después de que se hayan consumido todas las listas anteriores.

El trabajo total necesario para todas las reasociaciones es O(number of lists) , por lo que el costo total para la concatenación es O(number of lists + sum (map length lists)) . (Eso significa que puede traer un mal rendimiento a esto también, insertando mucho profundamente anidado en la izquierda ([] ++) .)

los

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (/xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (/xs -> f (g xs))

simplemente envuelve eso para que sea más conveniente manejarlo de manera abstracta.

DiffList (a ++) `mappend` DiffList (b ++) ~> DiffList ((a ++) . (b++))

Tenga en cuenta que solo es eficaz para las funciones que no necesitan inspeccionar su argumento para comenzar a producir, si las funciones arbitrarias se envuelven en DiffList s, no tiene tales garantías de eficiencia. En particular, anexar ( (++ a) , envuelto o no) puede crear árboles anidados a la izquierda (++) cuando se compone de jerarquización derecha, por lo que puede crear el comportamiento de concatenación O(n²) con eso si el constructor DiffList es expuesto.

Answer 2

Puede ser útil mirar la definición de concatenación:

[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

Como puede ver, para concatenar dos listas necesita ir a la lista de la izquierda y crear una "copia" de la misma, solo para que pueda cambiar su final (esto es porque no puede cambiar directamente el final de la anterior lista, debido a la inmutabilidad).

Si haces tus concatenaciones de la manera asociativa correcta, no hay problema. Una vez insertado, una lista nunca tendrá que volver a tocarse (observe cómo la definición de ++ nunca inspecciona la lista de la derecha), por lo que cada elemento de lista solo se inserta "una vez" durante un tiempo total de O (N).

--This is O(n)
(a ++ (b ++ (c ++ (d ++ (e ++ f)))))

Sin embargo, si realiza una concatenación de forma asociativa izquierda, la lista "actual" tendrá que "derribarse" y "reconstruirse" cada vez que agregue otro fragmento de lista al final. Cada elemento de lista se repetirá cuando ¡está insertado y cada vez que se añaden fragmentos futuros! Es como el problema que obtienes en C si llamas ingenuamente a strcat varias veces seguidas.

En cuanto a las listas de diferencias, el truco es que mantienen un "agujero" explícito al final. Cuando conviertas un DList a una lista normal, le pasas lo que quieres que esté en el agujero y estará listo para funcionar. Las listas normales, por el contrario, siempre tapan el agujero al final con [] por lo que si desea cambiarlo (al concatenar), entonces necesita abrir la lista para llegar a ese punto.

La definición de listas de diferencias con funciones puede parecer intimidante al principio, pero en realidad es bastante simple. Puede verlos desde un punto de vista orientado a objetos al considerarlos como objetos opacos. El método "toList" que recibe la lista que debe insertarse en el agujero al final devuelve el prefijo interno del DL más la cola que se proporcionó. Es eficiente porque solo conectas el "agujero" al final después de que termines de convertir todo.