Eficiencia de la programación puramente funcional.

397

¿Alguien sabe cuál es la peor desaceleración asintótica posible que puede ocurrir cuando se programa puramente funcionalmente en lugar de imperativo (es decir, permitiendo efectos secundarios)?

Aclaración del comentario de itowlson : ¿hay algún problema para el cual el algoritmo no destructivo más conocido sea asintóticamente peor que el algoritmo destructivo más conocido y, en caso afirmativo, por cuánto?

algorithm functional-programming performance Optar
fuente
66
Lo mismo que cuando se programa imperativamente, sea lo que sea.
R. Martinho Fernandes
3
@jldupont: para devolver el resultado de un cálculo, por supuesto. Existen muchos programas libres de efectos secundarios. Simplemente no pueden hacer mucho más que calcular en su entrada. Pero eso sigue siendo útil.
jalf
24
¡Puedo hacerlo tan mal como quieras, escribiendo mal mi código funcional! * sonrisa * Creo que lo que estás preguntando es "¿hay algún problema para el cual el algoritmo no destructivo más conocido sea asintóticamente peor que el algoritmo destructivo más conocido, y si es así, por cuánto?" ... ¿es correcto? ?
itowlson
2
¿Podría dar un ejemplo del tipo de desaceleración que le interesa? Su pregunta es un poco vaga.
Peter Recore
55
Un usuario eliminó su respuesta, pero afirmó que la versión funcional del problema de 8 reinas se ejecutó en más de un minuto por n = 13. Admitió que no estaba "escrita muy bien", así que decidí escribir mi propia versión del 8 reinas en F #: pastebin.com/ffa8d4c4 . No hace falta decir que mi programa puramente funcional calcula n = 20 en poco más de un segundo.
Julieta

Respuestas:

531

Según Pippenger [1996] , al comparar un sistema Lisp que es puramente funcional (y tiene una semántica de evaluación estricta, no perezosa) con uno que puede mutar datos, se puede traducir un algoritmo escrito para el Lisp impuro que se ejecuta en O ( n ) a un algoritmo en el Lisp puro que se ejecuta en tiempo O ( n log n ) (basado en el trabajo de Ben-Amram y Galil [1992] sobre la simulación de memoria de acceso aleatorio utilizando solo punteros). Pippenger también establece que hay algoritmos para los que es lo mejor que puede hacer; hay problemas que son O ( n ) en el sistema impuro que son Ω ( n log n ) en el sistema puro.

Hay algunas advertencias sobre este documento. Lo más significativo es que no aborda los lenguajes funcionales perezosos, como Haskell. Bird, Jones y De Moor [1997] demuestran que el problema construido por Pippenger se puede resolver en un lenguaje funcional vago en O ( n ) tiempo, pero no establecen (y que yo sepa, nadie tiene) si No un lenguaje funcional perezoso puede resolver todos los problemas en el mismo tiempo de ejecución asintótico que un lenguaje con mutación.

El problema construido por Pippenger requiere que Ω ( n log n ) esté específicamente construido para lograr este resultado, y no es necesariamente representativo de problemas prácticos del mundo real. Existen algunas restricciones sobre el problema que son un poco inesperadas, pero necesarias para que la prueba funcione; en particular, el problema requiere que los resultados se calculen en línea, sin poder acceder a entradas futuras, y que la entrada consista en una secuencia de átomos de un conjunto ilimitado de átomos posibles, en lugar de un conjunto de tamaño fijo. Y el documento solo establece resultados (límite inferior) para un algoritmo impuro de tiempo de ejecución lineal; para problemas que requieren un mayor tiempo de ejecución, es posible que el O adicional (log n) factor visto en el problema lineal puede ser "absorbido" en el proceso de operaciones adicionales necesarias para algoritmos con tiempos de ejecución mayores. Estas aclaraciones y preguntas abiertas son exploradas brevemente por Ben-Amram [1996] .

En la práctica, se pueden implementar muchos algoritmos en un lenguaje funcional puro con la misma eficiencia que en un lenguaje con estructuras de datos mutables. Para obtener una buena referencia sobre las técnicas que se utilizarán para implementar estructuras de datos puramente funcionales de manera eficiente, consulte "Estructuras de datos puramente funcionales" de Chris Okasaki [Okasaki 1998] (que es una versión ampliada de su tesis [Okasaki 1996] ).

Cualquiera que necesite implementar algoritmos en estructuras de datos puramente funcionales debería leer Okasaki. Siempre puede obtener, en el peor de los casos, una desaceleración de O (log n ) por operación simulando memoria mutable con un árbol binario equilibrado, pero en muchos casos puede hacerlo considerablemente mejor que eso, y Okasaki describe muchas técnicas útiles, desde técnicas amortizadas hasta técnicas reales. tiempo que hacen el trabajo amortizado de forma incremental. Las estructuras de datos puramente funcionales pueden ser un poco difíciles de trabajar y analizar, pero proporcionan muchos beneficios, como la transparencia referencial, que son útiles en la optimización del compilador, en la computación paralela y distribuida, y en la implementación de características como el control de versiones, deshacer y deshacer.

Tenga en cuenta también que todo esto solo analiza los tiempos de ejecución asintóticos. Muchas técnicas para implementar estructuras de datos puramente funcionales le brindan una cierta cantidad de desaceleración constante del factor, debido a la contabilidad adicional necesaria para que funcionen, y detalles de implementación del idioma en cuestión. Los beneficios de las estructuras de datos puramente funcionales pueden ser mayores que estas desaceleraciones constantes de los factores, por lo que generalmente necesitará hacer compensaciones en función del problema en cuestión.

Referencias

Brian Campbell
fuente
50
Pippinger es la autoridad indiscutible en esta cuestión. Pero debemos enfatizar que sus resultados son teóricos , no prácticos. Cuando se trata de hacer que las estructuras de datos funcionales sean prácticas y eficientes, no puede hacerlo mejor que Okasaki.
Norman Ramsey el
66
itowlson: Debo admitir que no leí suficiente de Pippenger para responder a su pregunta; Fue publicado en una revista revisada por pares, citada por Okasaki, y leí lo suficiente para determinar que sus afirmaciones son relevantes para esta pregunta, pero no lo suficiente como para entender la prueba. La conclusión inmediata que me pasa por consecuencias en el mundo real es que es trivial para convertir un O ( n algoritmo) impuro en un O ( n log n ) uno puro, simplemente simulando la memoria modificable mediante un árbol binario equilibrado. Hay problemas que no pueden ser mejores que eso; No sé si son puramente teóricos.
Brian Campbell el
3
El resultado de Pippenger hace dos suposiciones importantes que limitan su alcance: considera los cálculos "en línea" o "reactivos" (no el modelo habitual de un cálculo que asigna entradas finitas a una única salida) y los cálculos "simbólicos" donde las entradas son secuencias de átomos, que solo pueden probarse para la igualdad (es decir, la interpretación de la entrada es extremadamente primitiva).
Chris Conway
2
Muy buena respuesta; Me gustaría agregar que para los lenguajes puramente funcionales no existe un modelo universalmente acordado para la complejidad informática, mientras que en el mundo impuro la máquina RAM de costo unitario es relativamente estándar (por lo que esto hace que la comparación de las cosas sea más difícil). También tenga en cuenta que el límite superior de una diferencia Lg (N) en puro / impuro puede explicarse intuitivamente muy fácilmente al observar una implementación de matrices en un lenguaje puro (cuesta lg (n) por operación (y obtiene el historial)) .
user51568
44
Punto importante: traducir minuciosamente una especificación puramente funcional en una implementación eficiente puramente funcional más complicada es de poco beneficio si eventualmente, ya sea de forma automática o manual, la traduzca en un código impuro aún más eficiente. La impureza no es tan importante si puede mantenerla en una jaula, por ejemplo, encerrándola en una función externa sin efectos secundarios.
Robin Green
44

De hecho, hay varios algoritmos y estructuras de datos para los que no se conoce una solución puramente funcional asintóticamente eficiente (una implementable en cálculo lambda puro), incluso con pereza.

  • El mencionado hallazgo sindical
  • Tablas hash
  • Matrices
  • Algunos algoritmos gráficos
  • ...

Sin embargo, suponemos que en lenguajes "imperativos" el acceso a la memoria es O (1), mientras que en teoría eso no puede ser tan asintótico (es decir, para tamaños de problemas ilimitados) y el acceso a la memoria dentro de un gran conjunto de datos es siempre O (log n) , que se puede emular en un lenguaje funcional.

Además, debemos recordar que en realidad todos los lenguajes funcionales modernos proporcionan datos mutables, y Haskell incluso los proporciona sin sacrificar la pureza (la mónada ST).

jkff
fuente
3
Si el conjunto de datos se ajusta a la memoria física, el acceso a él es O (1), ya que es posible encontrar un límite superior absoluto en la cantidad de tiempo para leer cualquier elemento. Si el conjunto de datos no lo hace, está hablando de E / S y ese será el factor dominante con diferencia, sin embargo, el programa está escrito.
Donal Fellows
Bueno, por supuesto, estoy hablando de operaciones O (log n) de acceso a la memoria externa. Sin embargo, en cualquier caso, estaba hablando de bs: la memoria externa también puede ser O (1) direccionable ...
jkff
2
Creo que una de las cosas más importantes que gana la programación imperativa en comparación con la programación funcional es la capacidad de mantener referencias a muchos aspectos distintos de un estado, y generar un nuevo estado de tal manera que todas esas referencias apunten a los aspectos correspondientes del nuevo estado. El uso de la programación funcional requeriría que las operaciones de desreferenciación directa fueran reemplazadas por operaciones de búsqueda para encontrar el aspecto apropiado de una versión particular del estado general actual.
supercat
Incluso el modelo de puntero (acceso de memoria O (log n), hablando en términos generales) no es físicamente realista a escalas extremadamente grandes. La velocidad de la luz limita la rapidez con que diferentes equipos informáticos pueden comunicarse entre sí, mientras que actualmente se cree que la cantidad máxima de información que se puede mantener en una región determinada está limitada por su área de superficie.
dfeuer
36

Este artículo afirma que las implementaciones puramente funcionales conocidas del algoritmo de búsqueda de unión tienen una complejidad asintótica peor que la que publican, que tiene una interfaz puramente funcional pero utiliza datos mutables internamente.

El hecho de que otras respuestas afirmen que nunca puede haber ninguna diferencia y que, por ejemplo, el único "inconveniente" del código puramente funcional es que puede ser paralelo, le da una idea de la información / objetividad de la comunidad de programación funcional sobre estos asuntos .

EDITAR:

Los comentarios a continuación señalan que una discusión sesgada de los pros y los contras de la programación funcional pura puede no provenir de la "comunidad de programación funcional". Buen punto. Quizás los defensores que veo son, por citar un comentario, "analfabetos".

Por ejemplo, creo que esta publicación de blog está escrita por alguien que podría decirse que es representativo de la comunidad de programación funcional, y dado que es una lista de "puntos para una evaluación perezosa", sería un buen lugar para mencionar cualquier inconveniente que programación perezosa y puramente funcional podría tener. Un buen lugar habría estado en lugar del siguiente despido (técnicamente cierto, pero sesgado hasta el punto de no ser gracioso):

Si una función estricta tiene complejidad O (f (n)) en un lenguaje estricto, entonces también tiene complejidad O (f (n)) en un lenguaje vago. ¿Por que preocuparse? :)

Pascal Cuoq
fuente
4

Con un límite superior fijo en el uso de memoria, no debería haber diferencia.

Boceto de prueba: dado un límite superior fijo en el uso de la memoria, uno debería poder escribir una máquina virtual que ejecute un conjunto de instrucciones imperativas con la misma complejidad asintótica que si estuviera ejecutando en esa máquina. Esto es así porque puede administrar la memoria mutable como una estructura de datos persistente, dando O (log (n)) lectura y escritura, pero con un límite superior fijo en el uso de la memoria, puede tener una cantidad fija de memoria, lo que hace que estos decaimiento a O (1). Por lo tanto, la implementación funcional puede ser la versión imperativa que se ejecuta en la implementación funcional de la VM, por lo que ambos deben tener la misma complejidad asintótica.

Brian
fuente
66
Un límite superior fijo en el uso de la memoria no es cómo las personas analizan este tipo de cosas; asume una memoria arbitrariamente grande pero finita. Al implementar un algoritmo, estoy interesado en cómo se escalará desde la entrada más simple hasta cualquier tamaño de entrada arbitrario. Si pones un límite superior fijo en el uso de la memoria, ¿por qué no pones también un límite superior fijo en cuánto tiempo permitirás que tome el cálculo y digas que todo es O (1)?
Brian Campbell el
@Brian Campbell: Eso es cierto. Solo estoy sugiriendo que si quisieras, podrías ignorar la diferencia en el factor constante en muchos casos en la práctica. Todavía sería necesario tener en cuenta la diferencia al comprometer la memoria y el tiempo para asegurarse de que el uso de m veces más memoria disminuye su tiempo de ejecución en al menos un factor de log (m).
Brian