python - solutions - Proyecto Euler: ¿Cómo es este código haskell tan rápido?

euler python

Question

Estoy trabajando en el problema 401 en el proyecto euler, codifiqué mi solución en Python, pero tardará unos días en ejecutarse, obviamente necesitaré acelerarlo o usar un enfoque diferente. Encontré una solución en Haskell que parece casi idéntica a mi solución de Python pero que se completa casi instantáneamente.

¿Alguien puede explicar cómo es tan rápido? ( NO ESTOY SOLICITANDO AYUDA O SOLUCIONES AL PROBLEMA 401 )

divisors n = filter (/x -> n `mod` x == 0) [1..(n`div`2)] ++ [n]
sigma2 n = sum $ map (/x -> x * x) (divisors n)
sigma2big n = sum $ map (sigma2)[1..n]
let s2b = sigma2big 10^15
putStrLn ("SIGMA2(10^15) mod 10^9 is " ++ (show (mod s2b 10^9)))

A mi entender, solo se usa la división de prueba para generar una lista de divisores, cuadrar y sumar, y luego sumar los resultados de 1 a n.

EDITAR: olvidé mi código python

from time import clock


def timer(function):

    def wrapper(*args, **kwargs):
        start = clock()
        print(function(*args, **kwargs))
        runtime = clock() - start
        print("Runtime: %f seconds." % runtime)

    return wrapper


@timer
def find_answer():
    return big_sigma2(10**15) % 10**9

def get_divisors(n):
    divs = set()
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            divs.add(i)
            divs.add(n // i)
    return divs

def sigma2(n):
    return sum(map(lambda x: x**2, get_divisors(n)))

def big_sigma2(n):
    total = 0
    for i in range(1, n + 1):
        total += sigma2(i)
    return total

if __name__ == "__main__":
    find_answer()

Answer 1

Asegúrese de que está utilizando Integer para sus cálculos y no Int porque 10^15 desbordarán un valor Int .

Si cambias:

let s2b = sigma2big 10^15

a:

let s2b = sigma2big (10^15 :: Integer)

El código de Haskell se queda sin memoria en ghci y no me molesté en esperar a que se completara al ejecutar la versión compilada.

Answer 2

Prelude> sigma2big 1000
401382971
(0.48 secs, 28491864 bytes)

Prelude> sigma2big 10^3
103161709
(0.02 secs, 1035252 bytes)

Prelude> (sigma2big 10)^3
103161709

función de precedencia (shh ...)