437 votos

Comparación de velocidad con Project Euler: C vs Python vs vs Erlang Haskell

He tomado Problema #12 de Project Euler como un ejercicio de programación y comparar mi (seguramente no es la óptima) implementaciones en C, Python, Erlang y Haskell. Con el fin de obtener unos mayores tiempos de ejecución, que la búsqueda de la primera triángulo número con más de 1000 divisores, en lugar de 500 como se indica en el problema original.

El resultado es el siguiente:

C:

lorenzo@enzo:~/erlang$ gcc -lm -o euler12.bin euler12.c
lorenzo@enzo:~/erlang$ time ./euler12.bin
842161320

real    0m11.074s
user    0m11.070s
sys 0m0.000s

python:

lorenzo@enzo:~/erlang$ time ./euler12.py 
842161320

real    1m16.632s
user    1m16.370s
sys 0m0.250s

python con pypy:

lorenzo@enzo:~/Downloads/pypy-c-jit-43780-b590cf6de419-linux64/bin$ time ./pypy /home/lorenzo/erlang/euler12.py 
842161320

real    0m13.082s
user    0m13.050s
sys 0m0.020s

erlang:

lorenzo@enzo:~/erlang$ erlc euler12.erl 
lorenzo@enzo:~/erlang$ time erl -s euler12 solve
Erlang R13B03 (erts-5.7.4) [source] [64-bit] [smp:4:4] [rq:4] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.4  (abort with ^G)
1> 842161320

real    0m48.259s
user    0m48.070s
sys 0m0.020s

haskell:

lorenzo@enzo:~/erlang$ ghc euler12.hs -o euler12.hsx
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12.hsx ...
lorenzo@enzo:~/erlang$ time ./euler12.hsx 
842161320

real    2m37.326s
user    2m37.240s
sys 0m0.080s

Resumen:

  • C: 100%
  • python: 692% (118% con pypy)
  • erlang: 436% (135% gracias a RichardC)
  • haskell: 1421%

Supongo que C tiene una gran ventaja, ya que utiliza mucho para los cálculos y no arbitraria de la longitud de los enteros como los otros tres. También él no necesita cargar un tiempo de ejecución de la primera (¿ y los demás?).

Pregunta 1: ¿Erlang, Python y Haskell perder velocidad debido a la utilización de longitud arbitraria enteros o no son tan largos como los valores son inferiores a MAXINT?

Pregunta 2: ¿Por qué es Haskell tan lento? Hay un indicador de compilador que convierte los frenos o es mi aplicación? (Esto último es bastante probable como que Haskell es un libro con siete sellos para mí.)

Pregunta 3: Me ofrecen algunos consejos sobre cómo optimizar estas implementaciones sin cambiar la manera de determinar los factores? Optimización de ninguna manera: mejor, más rápido, más "nativos" de la lengua.

EDICIÓN:

Pregunta 4: ¿Mi funcionales de las implementaciones de permiso de LCO (última llamada de optimización, también conocido como cola de recursividad eliminación) y, por tanto, evitar la adición de innecesarias marcos en la pila de llamadas?

Realmente traté de aplicar el mismo algoritmo tan similares como sea posible en los cuatro idiomas, aunque tengo que admitir que mi Haskell, Erlang conocimiento es muy limitado.


Códigos fuente utilizado:

#include <stdio.h>
#include <math.h>

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square;
    int count = isquare == square ? -1 : 0;
    long candidate;
    for (candidate = 1; candidate <= isquare; candidate ++)
        if (0 == n % candidate) count += 2;
    return count;
}

int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index ++;
        triangle += index;
    }
    printf ("%ld\n", triangle);
}

#! /usr/bin/env python3.2

import math

def factorCount (n):
    square = math.sqrt (n)
    isquare = int (square)
    count = -1 if isquare == square else 0
    for candidate in range (1, isquare + 1):
        if not n % candidate: count += 2
    return count

triangle = 1
index = 1
while factorCount (triangle) < 1001:
    index += 1
    triangle += index

print (triangle)

-module (euler12).
-compile (export_all).

factorCount (Number) -> factorCount (Number, math:sqrt (Number), 1, 0).

factorCount (_, Sqrt, Candidate, Count) when Candidate > Sqrt -> Count;

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;

factorCount (Number, Sqrt, Candidate, Count) ->
    case Number rem Candidate of
        0 -> factorCount (Number, Sqrt, Candidate + 1, Count + 2);
        _ -> factorCount (Number, Sqrt, Candidate + 1, Count)
    end.

nextTriangle (Index, Triangle) ->
    Count = factorCount (Triangle),
    if
        Count > 1000 -> Triangle;
        true -> nextTriangle (Index + 1, Triangle + Index + 1)  
    end.

solve () ->
    io:format ("~p~n", [nextTriangle (1, 1) ] ),
    halt (0).

factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' number sqrt candidate count
    | fromIntegral candidate > sqrt = count
    | number `mod` candidate == 0 = factorCount' number sqrt (candidate + 1) (count + 2)
    | otherwise = factorCount' number sqrt (candidate + 1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index + 1) (triangle + index + 1)

main = print $ nextTriangle 1 1

545voto

Thomas M. DuBuisson Puntos 31851

Utilizando GHC 7.0.3, gcc 4.4.6, Linux 2.6.29 en x86_64 Core2 Duo (2.5 GHz) de la máquina, de la compilación usando ghc -O2 -fllvm -fforce-recomp de Haskell, gcc -O3 -lm para C.

  • Su rutina de C se ejecuta en 8.4 segundos (más rápido que el de su ejecución, probablemente debido -O3)
  • El Haskell solución se ejecuta en 36 segundos (debido a la -O2 bandera)
  • Su factorCount' código no está explícitamente escrito y por omision Integer (gracias a Daniel por corregir mis errores de diagnóstico aquí!). Dando un tipo explícito de la firma (que es una práctica común de todos modos), utilizando Int y los cambios de tiempo a 11.1 segundos
  • en factorCount' tiene innecesariamente llamados fromIntegral. Una revisión de los resultados en no cambiar a pesar de que (el compilador es inteligente, por suerte para ti).
  • Utilizó mod donde rem es más rápido y suficiente. Esto cambia el tiempo a 8.5 segundos.
  • factorCount' está constantemente la aplicación de dos argumentos adicionales que nunca cambian (number, sqrt). Un trabajador/envoltorio de transformación nos da:
 $ time ./so
 842161320  

 real    0m7.954s  
 user    0m7.944s  
 sys     0m0.004s  

Eso es correcto, 7.95 segundos. Constantemente la mitad de un segundo más rápido que el de C solución. Sin la -fllvm bandera todavía estoy recibiendo 8.182 seconds, por lo que la NCG backend está haciendo bien en este caso también.

Conclusión: Haskell es impresionante.

Código Resultante

factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' :: Int -> Int -> Int -> Int -> Int
factorCount' number sqrt candidate0 count0 = go candidate0 count0
  where
  go candidate count
    | candidate > sqrt = count
    | number `rem` candidate == 0 = go (candidate + 1) (count + 2)
    | otherwise = go (candidate + 1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index + 1) (triangle + index + 1)

main = print $ nextTriangle 1 1

EDIT: ahora que hemos explorado que permite responder a las preguntas

Pregunta 1: ¿erlang, python y haskell perder velocidad debido a la utilización de longitud arbitraria enteros o no, ellos siempre y cuando los valores son menos de MAXINT?

En Haskell, utilizando Integer es más lento que Int pero cuánto más lento depende de los cálculos realizados. Por suerte (para 64 bits máquinas) Int es suficiente. Para portabilidad de la causa, usted probablemente debería escribir mi código para utilizar Int64 o Word64 C no es el único idioma con un long).

Pregunta 2: ¿por Qué es haskell tan lento? Hay un indicador de compilador que apaga los frenos o es mi aplicación? (Esto último es bastante probable como que haskell es un libro con siete sellos para mí.)

Pregunta 3: ¿usted me ofrece algunos consejos sobre cómo optimizar estas implementaciones sin cambiar la manera de determinar los factores? Optimización de ninguna manera: mejor, más rápido, más "nativos" de la lengua.

Eso fue lo que respondí anteriormente. La respuesta fue

  • 0) optimización del Uso de la vía -O2
  • 1) rápido (en particular: unbox) cuando sea posible
  • 2) rem no mod (frecuentemente olvidado de optimización) y
  • 3) trabajador/envoltorio de transformación (tal vez la más común de optimización).

Pregunta 4: ¿mi funcionales de las implementaciones de permiso del comité de gestión del pasivo y por lo tanto evitar la adición de innecesarias marcos en la pila de llamadas?

Sí, ese no era el problema. Buen trabajo y me alegro de que usted considera esto.

171voto

RichardC Puntos 5059

Hay algunos problemas con el Erlang aplicación. Como línea de base para el siguiente, mi midió el tiempo de ejecución para su modificadas Erlang programa fue de 47,6 segundos, en comparación con el 12,7 segundos para el código de C.

La primera cosa que usted debe hacer si desea ejecutar computacionalmente intensivo de Erlang código es el uso de código nativo. Compilar con erlc +native euler12 consiguió el tiempo hasta el 41.3 segundos. Sin embargo, esto es mucho menor speedup (sólo el 15%) de lo esperado de compilación nativa en este tipo de código, y el problema es el uso de -compile(export_all). Esto es útil para la experimentación, pero el hecho de que todas las funciones son potencialmente accesible desde el exterior hace que el compilador nativo ser muy conservador. (El normal HAZ emulador no es mucho afectados). La sustitución de esta declaración, -export([solve/0]). da una mucho mejor speedup: 31.5 segundos (casi el 35% de la línea de base).

Pero el código en sí tiene un problema: para cada iteración en la factorCount bucle, de realizar esta prueba:

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;

El código de C no hacerlo. En general, puede ser difícil hacer una comparación justa entre los diferentes implementaciones del mismo código, y, en particular, si el algoritmo es numérica, debido a que usted necesita para asegurarse de que en realidad están haciendo lo mismo. Un leve error de redondeo en la implementación, debido a algunos encasillado en algún lugar puede provocar que hacer muchas más iteraciones que el otro, aunque ambos llegan al mismo resultado.

Para eliminar esta posible fuente de error (y deshacerse del exceso de prueba en cada iteración), reescribí la factorCount una función como la siguiente, estrechamente el código en C:

factorCount (N) ->
    Sqrt = math:sqrt (N),
    ISqrt = trunc(Sqrt),
    if ISqrt == Sqrt -> factorCount (N, ISqrt, 1, -1);
       true          -> factorCount (N, ISqrt, 1, 0)
    end.

factorCount (_N, ISqrt, Candidate, Count) when Candidate > ISqrt -> Count;
factorCount ( N, ISqrt, Candidate, Count) ->
    case N rem Candidate of
        0 -> factorCount (N, ISqrt, Candidate + 1, Count + 2);
        _ -> factorCount (N, ISqrt, Candidate + 1, Count)
    end.

Esta reescritura, no export_all, y la compilación nativa, me dio la siguiente tiempo de ejecución:

$ erlc +native euler12.erl
$ time erl -noshell -s euler12 solve
842161320

real    0m19.468s
user    0m19.450s
sys 0m0.010s

lo que no es malo en comparación con el código en C:

$ time ./a.out 
842161320

real    0m12.755s
user    0m12.730s
sys 0m0.020s

teniendo en cuenta que Erlang no es en todos orientados hacia la escritura de código numérico, siendo sólo el 50% más lento que C en un programa como este es bastante bueno.

Por último, en cuanto a tus preguntas:

Pregunta 1: ¿erlang, python y haskell sueltas de velocidad debido a la utilización de longitud arbitraria enteros o no son tan largos como los valores son inferiores a MAXINT?

Sí, un poco. En Erlang, no hay manera de decir "usar 32/64 bits aritméticos con wrap-around", así que a menos que el compilador puede probar algunos límites en su enteros (y por lo general no puede), se debe comprobar que todos los cálculos para ver si pueden caber en una sola palabra etiquetada o si tiene que recurrir a ellos en la pila-asignado bignums. Incluso si no bignums se utilizará en la práctica en tiempo de ejecución, estos cheques tienen que ser realizadas. Por otro lado, que significa que usted sabe que el algoritmo nunca fallan debido a un inesperado entero envolvente si de repente se dan las grandes entradas que antes.

Pregunta 4: ¿mi funcionales de las implementaciones de permiso del comité de gestión del pasivo y, por tanto, evitar la adición de innecesarias marcos en la pila de llamadas?

Sí, su Erlang código es correcto con respecto a la última convocatoria de optimización.

134voto

zeekay Puntos 22640

En lo que respecta a Python optimización, además de la utilización de PyPy (por bastante impresionante velocidad-ups con cero cambio en su código), podría usar PyPy de la traducción herramientas para compilar un RPython compatible con la versión, o Cython para construir un módulo de extensión, ambos de los cuales son más rápidos que la versión C en mis pruebas, con la Cython módulo de casi el doble de rápido. De referencia que incluyen C y PyPy resultados de la evaluación así:

C (compilado con gcc -O3 -lm)

% time ./euler12-c 
842161320

./euler12-c  11.95s 
 user 0.00s 
 system 99% 
 cpu 11.959 total

PyPy 1.5

% time pypy euler12.py
842161320
pypy euler12.py  
16.44s user 
0.01s system 
99% cpu 16.449 total

RPython (utilizando las últimas PyPy revisión, c2f583445aee)

% time ./euler12-rpython-c
842161320
./euler12-rpy-c  
10.54s user 0.00s 
system 99% 
cpu 10.540 total

Cython 0.15

% time python euler12-cython.py
842161320
python euler12-cython.py  
6.27s user 0.00s 
system 99% 
cpu 6.274 total

El RPython versión tiene un par de cambios de clave. A traducir en un programa independiente que se necesita para definir su target, que en este caso es el main función. Se espera que acepte sys.argv como único argumento, y está obligado a devolver un int. Se puede traducir por el uso de translate.py, % translate.py euler12-rpython.py que se traduce en C y compila para usted.

# euler12-rpython.py

import math, sys

def factorCount(n):
    square = math.sqrt(n)
    isquare = int(square)
    count = -1 if isquare == square else 0
    for candidate in xrange(1, isquare + 1):
        if not n % candidate: count += 2
    return count

def main(argv):
    triangle = 1
    index = 1
    while factorCount(triangle) < 1001:
        index += 1
        triangle += index
    print triangle
    return 0

if __name__ == '__main__':
    main(sys.argv)

def target(*args):
    return main, None

El Cython versión se ha reescrito como un módulo de extensión _euler12.pyx, que puedo importar y haga la llamada desde un normal archivo de python. La _euler12.pyx es esencialmente el mismo que el de su versión, con algunos adicionales estático tipo de declaraciones. El setup.py tiene la normal estándar para construir la extensión, utilizando python setup.py build_ext --inplace.

# _euler12.pyx
from libc.math cimport sqrt

cdef int factorCount(int n):
    cdef int candidate, isquare, count
    cdef double square
    square = sqrt(n)
    isquare = int(square)
    count = -1 if isquare == square else 0
    for candidate in range(1, isquare + 1):
        if not n % candidate: count += 2
    return count

cpdef main():
    cdef int triangle = 1, index = 1
    while factorCount(triangle) < 1001:
        index += 1
        triangle += index
    print triangle

# euler12-cython.py
import _euler12
_euler12.main()

# setup.py
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext

ext_modules = [Extension("_euler12", ["_euler12.pyx"])]

setup(
  name = 'Euler12-Cython',
  cmdclass = {'build_ext': build_ext},
  ext_modules = ext_modules
)

Honestamente tengo muy poca experiencia con RPython o Cython, y fue gratamente sorprendido por los resultados. Si usted está usando CPython, la escritura intensivo de la CPU, trozos de código en un Cython módulo de extensión parece una forma muy fácil para optimizar su programa.

56voto

Raedwulf Puntos 411

Pregunta 3: ¿Puede usted me ofrece algunos consejos sobre cómo optimizar estas implementaciones sin cambiar la manera de determinar los factores? Optimización en cualquier forma: más bonito, más rápido, más "nativos" de la lengua.

La implementación en C es subóptima (como se insinúa por Thomas M. DuBuisson), la versión que utiliza números enteros de 64 bits (es decir, mucho de tipo de datos). Voy a investigar la asamblea listado más tarde, pero con una conjetura, hay algunos accesos a la memoria pasando en el código compilado, que hacen que el uso de enteros de 64 bits significativamente más lento. Es que o código generado (sea el hecho de que puede encajar menos de 64-bits enteros en un ESS registro o alrededor de un doble a un entero de 64 bits es más lento).

Aquí está el código modificado (simplemente reemplazar largo con int y me explícitamente entre líneas factorCount, aunque no creo que esto es necesario con gcc-O3):

#include <stdio.h>
#include <math.h>

static inline int factorCount(int n)
{
    double square = sqrt (n);
    int isquare = (int)square;
    int count = isquare == square ? -1 : 0;
    int candidate;
    for (candidate = 1; candidate <= isquare; candidate ++)
        if (0 == n % candidate) count += 2;
    return count;
}

int main ()
{
    int triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index++;
        triangle += index;
    }
    printf ("%d\n", triangle);
}

Correr + timing da:

$ gcc -O3 -lm -o euler12 euler12.c; time ./euler12
842161320
./euler12  2.95s user 0.00s system 99% cpu 2.956 total

Para referencia, la de haskell aplicación por parte de Thomas en la anterior respuesta le da:

$ ghc -O2 -fllvm -fforce-recomp euler12.hs; time ./euler12                                                                                      [9:40]
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12 ...
842161320
./euler12  9.43s user 0.13s system 99% cpu 9.602 total

Conclusión: Tomando nada, lejos de ghc, es un gran compilador, pero gcc normalmente genera un código más rápido.

47voto

agf Puntos 45052

Echa un vistazo a este blog. Durante el último año o así que hace un par de el Proyecto Euler problemas en Haskell y Python, y él se encuentra generalmente Haskell a ser mucho más rápido. Creo que entre los idiomas que tiene más que ver con su fluidez y estilo de codificación.

Cuando se trata de Python a la velocidad, se está utilizando la incorrecta aplicación! Trate de PyPy, y por cosas como esta usted encontrará que es mucho, mucho más rápido.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X