algorithm functional-programming performance

algorithm - Eficiencia de la programación puramente funcional.



functional-programming performance (6)

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

Aclaración del comentario de itowlson : ¿hay algún problema para el cual el mejor algoritmo no destructivo conocido sea asintóticamente peor que el mejor algoritmo destructivo conocido, y si es así, cuánto?

"Funcional" es un conjunto de características diferentes, cada una de las cuales es útil de forma independiente, y se considera más útil para examinarlas individualmente.

Inmutabilidad

Ahora que estoy familiarizado con eso, cada vez que puedo salir adelante con un resultado inmutable, siempre trato de hacerlo, incluso en un programa orientado a objetos. Es más fácil razonar sobre el programa si tiene datos de tipo valor.

Funciones como tipos de primera clase

Como quiera llamarlo, pasar a los delegados, acciones o funciones es una manera realmente útil de resolver toda una clase de problemas del mundo real, como el "agujero en el patrón medio".

Ser capaz de componer funciones (por ejemplo, convertir la acción en solo una acción también es muy útil en algunos escenarios).

También debemos tener en cuenta la sintaxis de Lambda aquí, porque solo se obtiene la sintaxis de Lambda cuando se promueven funciones a tipos de primera clase. La sintaxis lambda puede ser muy expresiva y concisa.

Mónadas

Este es un constructo sutil pero muy poderoso. Es tan poderoso como la palabra clave de rendimiento utilizada para crear clases IEnumerable en C #. Esencialmente, está construyendo una máquina de estados debajo de las cubiertas, pero su lógica parece lineal.

Evaluación perezosa y recursión

Los puse juntos porque, si bien siempre están agrupados como características de la programación funcional, se han abierto camino tan rápidamente en lenguajes imperativos que es difícil llamarlos funcionales.

S-Expresiones

Supongo que no estoy seguro de dónde colocar esto, pero la capacidad de tratar el código no compilado como un objeto (y de inspeccionarlo / modificarlo), como Lisp S-Expressions o LINQ Expressions, es, de alguna manera, La herramienta más potente de programación funcional. La mayoría de las nuevas interfaces "fluidas" .NET y DSL, usan una combinación de sintaxis lambda y LINQ Expressions para crear algunas API muy concisas. Sin mencionar Linq2Sql / Linq2Nhibernate donde su código C # se ejecuta "mágicamente" como SQL en lugar de como código C #.

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

Bosquejo 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 imperativo con la misma complejidad asintótica como si estuviera ejecutando en esa máquina. Esto se debe a que puede administrar la memoria mutable como una estructura de datos persistente, dando lectura y escritura a O (log (n)), pero con un límite superior fijo en el uso de la memoria, puede tener una cantidad fija de memoria, lo que hace que desintegración 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 máquina virtual, por lo que ambos deben tener la misma complejidad asintótica.

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

  • El mencionado hallazgo sindical.
  • Mesas de hash
  • Arrays
  • Algunos algoritmos de grafos
  • ...

Sin embargo, asumimos que en los idiomas "imperativos" el acceso a la memoria es O (1), mientras que en teoría no puede ser tan asintóticamente (es decir, para problemas de tamaño ilimitados) y el acceso a la memoria dentro de un gran conjunto de datos siempre es O (log n) , que puede ser emulado 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).

Según Pippenger [1996] , cuando se compara 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 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 la memoria de acceso aleatorio utilizando solo punteros). Pippenger también establece que hay algoritmos para los cuales 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 que deben hacerse acerca de este documento. Lo más significativo es que no aborda lenguajes funcionales perezosos, como Haskell. Bird, Jones y De Moor [1997] demuestran que el problema construido por Pippenger puede resolverse en un lenguaje funcional perezoso en tiempo O ( n ), pero no establecen (y hasta donde sé, nadie lo ha hecho) si o no ni 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 ) se construya específicamente para lograr este resultado, y no es necesariamente representativo de problemas prácticos del mundo real. Hay algunas restricciones en 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 factor O (log n ) adicional observado en el problema lineal pueda ser "absorbido" en el proceso de operaciones adicionales necesarias para algoritmos con mayores tiempos de ejecución. Ben-Amram explora brevemente estas aclaraciones y preguntas abiertas [1996] .

En la práctica, muchos algoritmos pueden implementarse 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 a utilizar 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 debe leer Okasaki. En el peor de los casos, siempre puede obtener una ralentización O (log n ) por operación simulando una memoria mutable con un árbol binario balanceado, pero en muchos casos puede hacerlo considerablemente mejor que eso, y Okasaki describe muchas técnicas útiles, desde técnicas amortizadas hasta reales. Los tiempos que hacen el trabajo amortizado incrementalmente. Las estructuras de datos puramente funcionales pueden ser un poco difíciles de trabajar y analizar, pero ofrecen muchos beneficios como la transparencia referencial que son útiles en la optimización del compilador, en la computación en paralelo y distribuida, y en la implementación de funciones como control de versiones, deshacer y revertir.

Tenga en cuenta también que todo esto discute los tiempos de ejecución asintóticos. Muchas técnicas para implementar estructuras de datos puramente funcionales le dan una cierta cantidad de desaceleración constante del factor, debido a la contabilidad adicional necesaria para que funcionen, y los detalles de implementación del lenguaje en cuestión. Los beneficios de las estructuras de datos puramente funcionales pueden ser mayores que estas reducciones constantes de factores, por lo que generalmente tendrá que hacer concesiones basadas en el problema en cuestión.

Referencias

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 afirman 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 sobre las ventajas y desventajas 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 justos, para citar un comentario, "analfabetos".

Por ejemplo, creo que esta publicación del blog está escrita por alguien que podría decirse que es representativo de la comunidad de programación funcional, y como es una lista de "puntos para la evaluación perezosa", sería un buen lugar para mencionar cualquier inconveniente que La programación perezosa y puramente funcional podría tener. Un buen lugar hubiera sido 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, también tiene complejidad O (f (n)) en un lenguaje perezoso. ¿Por que preocuparse? :)