java - potencia - programa en haskell

¿Por qué el cálculo factorial es mucho más rápido en Haskell que en Java?

Question

Uno de los problemas de programación que he encontrado involucra el cálculo de factoriales de grandes números (de números hasta 10 ^ 5). He visto un código simple de Haskell que es así.

factorial :: (Eq x, Num x) => x -> x
factorial 0 = 1
factorial a = a * factorial (a - 1)

que maneja de forma implícita los grandes números y de alguna manera se ejecuta más rápido incluso sin ningún almacenamiento en caché involucrado en el código.

Cuando traté de resolver el problema usando Java, tuve que usar BigInteger para mantener los grandes números y también usar la versión iterativa de factorial

public static BigInteger factorialIterative(int n)
{
        if(n == 0 || n == 1) return BigInteger.valueOf(1);
        BigInteger f = BigInteger.valueOf(1);
        for(int i = 1 ; i <= n ;i++)
            f = f.multiply(BigInteger.valueOf(i));
        return f;
}

El código anterior excedió el límite de tiempo de ejecución establecido para el programa. También probé la versión recursiva en caché de factorial

public static BigInteger factorial(int n)
{
     if(cache[n] != null) 
         return cache[n];
     else if(n == 0) 
         return new BigInteger("1");
     else {
         cache[n] = n* factorial(n - 1);
         return cache[n]; 
     }
}          

que me dio un error de memoria (probablemente debido a la recursión).

Mi pregunta es, ¿por qué los lenguajes de programación funcionales como Haskell manejan mejor este tipo de problemas que involucran grandes números? (A pesar de que no hay caché evidente). ¿Hay alguna manera de hacer que el código Java se ejecute tan rápido como el código Haskell?

Answer 1

Aquí hay una pregunta relacionada: https://softwareengineering.stackexchange.com/q/149167/26988

Parece que en este caso particular, está viendo la diferencia en las optimizaciones de una función pura frente a una impura. En Haskell, todas las funciones son puras a menos que estén haciendo IO (ver enlace).

Creo que lo que está pasando es que GHC puede optimizar mejor el código debido a la garantía de pureza. Aunque no hay una llamada final, sabe que no hay ningún efecto secundario (debido a la garantía de pureza), por lo que puede hacer algunas optimizaciones que el código Java no puede (como el almacenamiento en caché automático y otras cosas como @andrew menciona en su respuesta) .

Una mejor solución en Haskell sería utilizar la función de producto integrada:

factorial n = product [1..n]

Esto es capaz de hacer la optimización de la llamada de cola porque es solo una iteración. Lo mismo se puede hacer en Java con un bucle for como en su ejemplo, pero no tendrá la ventaja de ser funcionalmente puro.

Editar:

Asumí que la eliminación de llamadas de cola estaba ocurriendo, pero aparentemente no. Aquí está la respuesta original como referencia (todavía tiene información útil sobre por qué Haskell puede ser más rápido que Java en algunos contextos recursivos).

Los lenguajes de programación funcionales como Haskell aprovechan la eliminación de llamadas de cola.

En la mayoría de los lenguajes de programación, las llamadas recursivas mantienen una pila de llamadas. Cada función recursiva asigna una nueva pila, que no se limpia hasta que vuelve. Por ejemplo:

call fact()
    call fact()
        call fact()
        cleanup
    cleanup
cleanup

Los lenguajes funcionales, sin embargo, no necesitan mantener una pila. En los lenguajes de procedimiento, a menudo es difícil saber si la función de llamada utilizará el valor de retorno, por lo que es difícil optimizarlo. Sin embargo, en FP, el valor de retorno solo tiene sentido cuando se completa la recursión, por lo que puede eliminar la pila de llamadas y terminar con algo como esto:

call fact()
call fact()
call fact()
cleanup

Las líneas de call fact() pueden suceder todas en el mismo marco de pila porque el valor de retorno no es necesario en los cálculos intermedios.

Ahora, para responder a su pregunta, puede resolver este problema de varias maneras, todas las cuales tienen como objetivo eliminar la pila de llamadas:

• use un bucle for en lugar de recursión (generalmente la mejor opción)
• devuelve vacío y espero que el compilador haga la eliminación de la llamada de cola
• usar una función de trampolín (similar a la idea de bucle for, pero se parece más a una recursión)

Aquí hay algunas preguntas relacionadas con ejemplos de lo anterior:

• Recursión vs bucles for: factoriales, Java (para bucle en lugar de recursión para factorial)
• ¿Por qué la JVM todavía no admite la optimización de llamadas de cola? (Tal vez la eliminación de llamadas de cola no es confiable en Java)
• ¿Qué es una función de trampolín? (función de trampolín en C)

Nota:

No se garantiza que las llamadas recursivas reutilicen el mismo marco de pila, por lo que algunas implementaciones pueden reasignarse en cada llamada recursiva. A menudo, esto es más fácil y aún proporciona la misma seguridad de memoria que la reutilización del marco de pila.

Para más información sobre esto, vea estos artículos:

• Llamada de cola
• Recursión de cola en Haskell

Answer 2

Creo que la diferencia no tiene nada que ver con la optimización de llamadas de cola, o la optimización en absoluto. La razón por la que creo que es que la optimización puede, en el mejor de los casos, lograr solo algo que sea como su versión iterativa de Java.

La verdadera razón es, en mi humilde opinión, que los BigIntegers de Java son lentos en comparación con los de Haskell.

Para establecer esto, propongo 2 experimentos:

1. Usa los mismos algoritmos, pero usa mucho tiempo. (Los resultados serán un poco de basura para números más altos, pero los cálculos se realizarán sin embargo). Aquí, la versión de Java debe estar a la par con Haskell.

2. Use una biblioteca de enteros grandes más rápida en la versión java. El rendimiento debería mejorar en consecuencia. Hay envoltorios para GMP por ahí, así como mejoras a los grandes enteros java como github.com/tbuktu/bigint . Las múltiples mejoras de rendimiento posibles para la multiplicación de grandes números son reveladoras.

Answer 3

Las explicaciones de abajo, obviamente, no son suficientes. Aquí hay algunas diapositivas que explican la transformación por la que pasa una función cuando sus parámetros son estrictos (como en el ejemplo anterior) y no se generan trucos: http://www.slideshare.net/ilyasergey/static-analyses-and-code-optimizations-in-glasgow-haskell-compiler

La versión de Haskell hará solo el cálculo almacenando solo el cálculo anterior y aplicando el siguiente, por ejemplo, 6 x 4. Mientras que la versión de Java está haciendo almacenamiento en caché (todos los valores históricos), gestión de memoria, GC y similares.

Está haciendo un análisis de rigor y automáticamente almacena en caché el cálculo anterior. Consulte: http://neilmitchell.blogspot.com.au/2008/03/lazy-evaluation-strict-vs-speculative.html?m=1

Hay más detalles en el Wiki de Haskell: "La optimización de compiladores como GHC intenta reducir el costo de la pereza utilizando el análisis de rigor, que intenta determinar qué argumentos de función siempre son evaluados por la función y, por lo tanto, el llamador puede evaluarlos".

"El análisis de rigor puede detectar el hecho de que el argumento n es estricto y se puede representar sin caja. La función resultante no usará ningún montón mientras se está ejecutando, como es de esperar".

"El análisis de rigidez es un proceso mediante el cual GHC intenta determinar, en tiempo de compilación, qué datos definitivamente ''siempre serán necesarios''. GHC puede luego construir código para simplemente calcular dichos datos, en lugar del proceso normal (mayor sobrecarga) para el almacenamiento. Sube el cálculo y ejecútalo más tarde ".

http://www.haskell.org/haskellwiki/Performance/Strictness http://www.haskell.org/haskellwiki/GHC_optimisations

Answer 4

Primero quiero señalar dos factores que claramente no son la razón de la diferencia de velocidad, pero que se han mencionado, sin embargo, en la pregunta y algunas respuestas.

Sin almacenamiento en caché / memoria

La pregunta menciona el almacenamiento en caché, y algunas de las respuestas mencionan la memorización. Pero la función factorial no se beneficia de la memorización, porque se llama a sí misma de forma recursiva con diferentes argumentos. Por lo tanto, nunca podríamos acceder a una entrada en el caché que ya esté llena, y todo el almacenamiento en caché es innecesario. Tal vez la gente estaba pensando en la función de fibonacci aquí?

Para el registro, Haskell no proporcionaría la memoria automática de todos modos.

Ninguna otra optimización inteligente

Tanto el programa de Java como el de Haskell me parecen ya óptimos. Ambos programas utilizan el mecanismo de iteración de elección de sus respectivos idiomas: Java usa un bucle, Haskell usa la recursión. Ambos programas utilizan un tipo estándar para la aritmética de enteros grandes.

En todo caso, la versión de Haskell debería ser más lenta porque no es recursiva, mientras que la versión de Java utiliza un bucle que es la construcción de bucle más rápida disponible en Java.

No veo mucho margen para las optimizaciones de alto nivel inteligentes que un compilador podría hacer para estos programas. Sospecho que la diferencia de velocidad observada se debe a los detalles de bajo nivel sobre cómo se implementan los enteros grandes.

Entonces, ¿por qué la versión de Haskell es más rápida?

El compilador de Haskell tiene un soporte integrado y razonable para Integer. Eso parece ser menos con las implementaciones de Java y la clase de entero grande. Busqué en Google para "BigInteger lento" y los resultados sugieren que la pregunta realmente debería ser: ¿Por qué el BigInteger de Java es tan lento? Parece que hay otras clases de enteros grandes que son más rápidas. No soy un experto en Java, por lo que no puedo responder a esta variante de la pregunta en ningún detalle.

Answer 5

shachaf dice shachaf , la diferencia es que GHC (de forma predeterminada) utiliza GMP para los cálculos de Integer que superan el rango Int , y GMP está bastante bien optimizado. No tiene nada que ver con la pureza, el almacenamiento en caché, la optimización de llamadas de cola o similares.

BigInteger de Java usa más o menos los algoritmos ingenuos de libros escolares. Si miras el código para multiply (openjdk7), el caballo de trabajo es

/**
 * Multiplies int arrays x and y to the specified lengths and places
 * the result into z. There will be no leading zeros in the resultant array.
 */
private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) {
    int xstart = xlen - 1;
    int ystart = ylen - 1;

    if (z == null || z.length < (xlen+ ylen))
        z = new int[xlen+ylen];

    long carry = 0;
    for (int j=ystart, k=ystart+1+xstart; j>=0; j--, k--) {
        long product = (y[j] & LONG_MASK) *
                       (x[xstart] & LONG_MASK) + carry;
        z[k] = (int)product;
        carry = product >>> 32;
    }
    z[xstart] = (int)carry;

    for (int i = xstart-1; i >= 0; i--) {
        carry = 0;
        for (int j=ystart, k=ystart+1+i; j>=0; j--, k--) {
            long product = (y[j] & LONG_MASK) *
                           (x[i] & LONG_MASK) +
                           (z[k] & LONG_MASK) + carry;
            z[k] = (int)product;
            carry = product >>> 32;
        }
        z[i] = (int)carry;
    }
    return z;
}

una multiplicación cuadrática dígito a dígito (los dígitos, por supuesto, no son base 10). Eso no duele demasiado aquí, ya que uno de los factores es siempre un solo dígito, pero indica que aún no se ha puesto mucho trabajo en la optimización de los cálculos de BigInteger en Java.

Una cosa que se puede ver desde la fuente es que en los productos Java de la forma smallNumber * largeNumber son más rápidos que largeNumber * smallNumber (en particular si el número pequeño es de un solo dígito, teniendo eso como primer número significa el segundo bucle con el el bucle anidado no se ejecuta en absoluto, por lo que tiene menos gastos generales de control del bucle, y el bucle que se ejecuta tiene un cuerpo más simple).

Tan cambiante

f = f.multiply(BigInteger.valueOf(i));

en su versión de Java para

f = BigInteger.valueOf(i).multiply(f);

da una aceleración considerable (incrementando con el argumento, ~ 2 × para 25000, ~ 2.5 × para 50000, ~ 2.8 × para 100000).

El cálculo sigue siendo mucho más lento que la combinación de GHC / GMP por un factor de aproximadamente 4 en el rango probado en mi caja, pero, bueno, la implementación de GMP está claramente mejor optimizada.

Si realiza cálculos que a menudo multiplican dos números grandes, se mostrará la diferencia algorítmica entre la multiplicación cuadrática de BigInteger y los GMP que usan Karatsuba o Toom-Cook cuando los factores son lo suficientemente grandes (FFT para números realmente grandes).

Sin embargo, si multiplicar no es todo lo que hace, si imprime los factoriales, por lo tanto, conviértalos a String , se verá afectado por el hecho de que el método toString BigInteger es abominablemente lento (es aproximadamente cuadrático, por lo que, desde el cálculo de El factorial es totalmente cuadrático en la longitud del resultado, no se obtiene una complejidad algorítmica [mucho] más alta, pero se obtiene un factor de gran constante en la parte superior del cálculo). La instancia de Show para Integer es mucho mejor, O(n * (log n)^x) [no estoy seguro de qué es x , entre 1 y 2], por lo que la conversión del resultado a String agrega solo un poco al tiempo de cálculo.