standard - programming in haskell

Beneficio de evitar múltiples recorridos de listas

Question

He visto muchos ejemplos en lenguajes funcionales sobre el procesamiento de una lista y la construcción de una función para hacer algo con sus elementos después de recibir algún valor adicional (generalmente no presente en el momento en que se generó la función), como:

• Calculando la diferencia entre cada elemento y la media.

  (los 2 últimos ejemplos en "Evaluación perezosa")

• Preparación de una lista agregada en lenguajes funcionales estrictos, como ML / OCaml, para evitar atravesar la primera lista más de una vez

  (La sección titulada "Puesta en escena")

• Comparar una lista con otra con foldr (es decir, generar una función para comparar otra lista con la primera)

  listEq a b = foldr comb null a b
  where comb x frec [] = False
  comb x frec (e:es) = x == e && frec es
  cmp1To10 = listEq [1..10]

En todos estos ejemplos, los autores generalmente comentan el beneficio de atravesar la lista original solo una vez. Pero no puedo evitar pensar "seguro, en lugar de recorrer una lista de N elementos, estás atravesando una cadena de evaluaciones de N, ¿y qué?". Sé que debe haber algún beneficio, ¿podría alguien explicarlo, por favor?

Edit: Gracias a ambos por las respuestas. Desafortunadamente, eso no es lo que quería saber. Trataré de aclarar mi pregunta, por lo que no se confunde con la (más común) sobre la creación de listas intermedias (sobre las que ya he leído en varios lugares). También gracias por corregir mi formato de publicación.

Me interesan los casos en los que construyes una función para aplicarla a una lista, donde todavía no tienes el valor necesario para evaluar el resultado (ya sea una lista o no). Entonces no puede evitar generar referencias a cada elemento de la lista (incluso si ya no se hace referencia a la estructura de la lista). Y tiene los mismos accesos de memoria que antes, pero no tiene que deconstruir la lista (coincidencia de patrones).

Por ejemplo, vea el capítulo de "puesta en escena" en el libro de ML mencionado. Lo he probado en ML y Racket, más específicamente la versión preparada de "append" que recorre la primera lista y devuelve una función para insertar la segunda lista en la cola, sin atravesar la primera lista muchas veces. Sorprendentemente para mí, fue mucho más rápido, incluso teniendo en cuenta que todavía tenía que copiar la estructura de la lista, ya que el último puntero era diferente en cada caso.

La siguiente es una variante del mapa que, después de aplicarla a una lista, debería ser más rápida al cambiar la función. Como Haskell no es estricto, tendría que forzar la evaluación de listMap [1..100000] en cachedList (o tal vez no, ya que después de la primera aplicación debería estar en la memoria).

listMap = foldr comb (const [])
where comb x rest = /f -> f x : rest f
cachedList = listMap [1..100000]
doubles = cachedList (2*)
squares = cachedList (/x -> x*x)
-- print doubles and squares
-- ...

Sé que en Haskell no hace una diferencia (corríjame si me equivoco) usando comb x rest f = ... vs comb x rest = /f -> ... , pero elegí esta versión para enfatizar la idea.

Actualización: después de algunas pruebas simples, no pude encontrar ninguna diferencia en los tiempos de ejecución en Haskell. La pregunta entonces es solo sobre lenguajes estrictos como Scheme (al menos la implementación de Racket, donde lo probé) y ML.

Answer 1

Así que la respuesta a tu pregunta es, compilación parcial . Hecho antes de tiempo, hace que no sea necesario recorrer la lista para llegar a los elementos individuales; todas las referencias se encuentran de antemano y se almacenan dentro de la función precompilada.

En cuanto a su preocupación acerca de la necesidad de que esa función se cruce también, sería cierto en los idiomas interpretados. Pero la compilación elimina este problema.

En presencia de la pereza, este truco de codificación puede llevar a resultados opuestos. Teniendo ecuaciones completas, por ejemplo, el compilador Haskell GHC puede realizar todo tipo de optimizaciones, que esencialmente eliminan las listas completamente y convierten el código en un equivalente de bucles. Esto sucede cuando -O2 el código con, por ejemplo, el interruptor -O2 .

Escribir las ecuaciones parciales puede impedir esta optimización del compilador y forzar la creación real de funciones, con una reducción drástica del código resultante. cachedList código de su cachedList y vi que el tiempo de ejecución de 0.01s se convirtió en 0.20s (no recuerdo en este momento la prueba exacta que hice).

Answer 2

Ejecutar unas pocas instrucciones aritméticas adicionales en su cuerpo de bucle es más barato que ejecutar unas pocas recuperaciones de memoria, básicamente.

Las travesías significan hacer un montón de acceso a la memoria, así que cuanto menos hagas, mejor. La fusión de recorridos reduce el tráfico de memoria y aumenta la carga de cómputo en línea recta, para que obtenga un mejor rendimiento.

Concretamente, considere este programa para calcular algunas matemáticas en una lista:

go :: [Int] -> [Int]
go = map (+2) . map (^3)

Claramente, lo diseñamos con dos recorridos de la lista. Entre el primer y el segundo recorrido, un resultado se almacena en una estructura de datos intermedia. Sin embargo, es una estructura perezosa, por lo que solo cuesta O(1) memoria.

Ahora, el compilador de Haskell fusiona inmediatamente los dos bucles en:

go = map ((+2) . (^3))

¿Porqué es eso? Después de todo, ambos son O(n) complejidad, ¿verdad? La diferencia está en los factores constantes.

Teniendo en cuenta esta abstracción: para cada paso de la primera tubería que hacemos:

 i <- read memory -- cost M
j = i ^ 3 -- cost A
write memory j -- cost M
k <- read memory -- cost M
l = k + 2 -- cost A
write memory l -- cost M

entonces pagamos 4 accesos de memoria, y 2 operaciones aritméticas.

Para el resultado fusionado tenemos:

 i <- read memory -- cost M
j = (i ^ 3) + 2 -- cost 2A
write memory j -- cost M

donde A y M son los factores constantes para realizar operaciones matemáticas en la ALU y el acceso a la memoria.

También hay otros factores constantes (dos ramas de bucle) en lugar de uno.

Entonces, a menos que el acceso a la memoria sea libre (no lo es, por mucho), entonces la segunda versión siempre es más rápida.

Tenga en cuenta que los compiladores que operan en secuencias inmutables pueden implementar la fusión de matrices, la transformación que hace esto por usted. GHC es un compilador de este tipo.

Answer 3

Hay otra razón muy importante. Si recorre una lista solo una vez, y no tiene otra referencia a ella, el GC puede liberar la memoria reclamada por los elementos de la lista a medida que los recorre. Además, si la lista se genera de forma perezosa, siempre tendrá un consumo de memoria constante. Por ejemplo

import Data.List
main = do
let xs = [1..10000000]
sum = foldl'' (+) 0 xs
len = foldl'' (/_ -> (+ 1)) 0 xs
print (sum / len)

calcula la sum , pero necesita mantener la referencia a xs y la memoria que ocupa no se puede liberar, porque se necesita para calcular len más adelante. (O viceversa.) Por lo tanto, el programa consume una cantidad considerable de memoria, xs más grande sea la memoria, más memoria necesitará.

Sin embargo, si recorremos la lista solo una vez, se crea perezosamente y los elementos pueden ser GC inmediatamente, por lo que no importa qué tan grande sea la lista, el programa solo toma memoria O(1) .

{-# LANGUAGE BangPatterns #-}
import Data.List
main = do
let xs = [1..10000000]
(sum, len) = foldl'' (/(!s,!l) x -> (s + x, l + 1)) (0, 0) xs
print (sum / len)

Answer 4

Lo siento de antemano por una respuesta de estilo hablador.

Probablemente sea obvio, pero si estamos hablando del rendimiento, siempre debe verificar las hipótesis mediante la medición.

Hace un par de años estaba pensando en la semántica operacional de GHC, la máquina STG. Y me hice la misma pregunta: seguramente los famosos algoritmos "de un solo recorrido" no son tan buenos. Solo se ve como un recorrido en la superficie, pero debajo del capó también tiene esta estructura de cadena de trocitos que generalmente es bastante similar a la lista original.

Escribí algunas versiones (que varían en rigor) del famoso problema RepMin: dado un árbol lleno de números, genere el árbol de la misma forma, pero reemplace cada número con el mínimo de todos los números. Si mi memoria es correcta (recuerda: ¡siempre verifica las cosas por ti mismo!), El ingenuo algoritmo de dos recorridos se realizó mucho más rápido que varios algoritmos inteligentes de un solo recorrido.

También compartí mis observaciones con Simon Marlow (ambos estábamos en una escuela de verano de PF durante ese tiempo), y dijo que usan este enfoque en GHC. Pero no para mejorar el rendimiento, como podría haber pensado. En su lugar, dijo, para un AST grande (como el de Haskell), anotar todos los constructores ocupa mucho espacio (en términos de líneas de código), por lo que solo reducen la cantidad de código anotando solo un recorrido transversal (sintáctico) .

Personalmente, evito este truco porque si cometes un error, obtienes un bucle que es algo muy desagradable de depurar.