opciones - pattern matching haskell

¿Cómo mejorar el rendimiento de este programa Haskell?

Question

Estoy trabajando en los problemas del Proyecto Euler como una forma de aprender Haskell, y encuentro que mis programas son mucho más lentos que una versión C comparable, incluso cuando están compilados. ¿Qué puedo hacer para acelerar mis programas de Haskell?

Por ejemplo, mi solución de fuerza bruta al Problema 14 es:

import Data.Int
import Data.Ord
import Data.List

searchTo = 1000000

nextNumber :: Int64 -> Int64
nextNumber n
    | even n    = n `div` 2
    | otherwise = 3 * n + 1

sequenceLength :: Int64 -> Int
sequenceLength 1 = 1
sequenceLength n = 1 + (sequenceLength next)
    where next = nextNumber n

longestSequence = maximumBy (comparing sequenceLength) [1..searchTo]

main = putStrLn $ show $ longestSequence

Lo que toma alrededor de 220 segundos, mientras que una versión "equivalente" de fuerza bruta C solo toma 1.2 segundos.

#include <stdio.h>

int main(int argc, char **argv)
{
    int longest = 0;
    int terms = 0;
    int i;
    unsigned long j;

    for (i = 1; i <= 1000000; i++)
    {
        j = i;
        int this_terms = 1;

        while (j != 1)
        {
            this_terms++;

            if (this_terms > terms)
            {
                terms = this_terms;
                longest = i;
            }

            if (j % 2 == 0)
                j = j / 2;
            else
                j = 3 * j + 1;
        }
    }

    printf("%d/n", longest);
    return 0;
}

¿Qué estoy haciendo mal? ¿O soy ingenuo para pensar que Haskell podría incluso acercarse a la velocidad de C?

(Estoy compilando la versión C con gcc -O2, y la versión Haskell con ghc --make -O).

Answer 1

Aunque esto ya es bastante antiguo, permítanme intervenir, hay un punto crucial que no se ha abordado antes.

Primero, los horarios de los diferentes programas en mi caja. Ya que estoy en un sistema Linux de 64 bits, muestran características algo diferentes: usar Integer lugar de Int64 no mejora el rendimiento como lo haría con un GHC de 32 bits, donde cada operación Int64 incurriría en el costo de una llamada C mientras que los cálculos con el ajuste de Integer en enteros de 32 bits con signo no necesitan una llamada externa (ya que solo unas pocas operaciones exceden ese rango aquí, el Integer es la mejor opción en un GHC de 32 bits).

• C: 0.3 segundos
• Haskell original: 14.24 segundos, usando Integer lugar de Int64 : 33.96 segundos
• Versión mejorada de KennyTM: 5,55 segundos, utilizando Int : 1,85 segundos
• Versión de Chris Kuklewicz: 5.73 segundos, utilizando Int : 1.90 segundos
• Versión de FUZxxl: 3.56 segundos, usando " quotRem lugar de divMod : 1.79 segundos"

Entonces, ¿qué tenemos?

1. Calcule la longitud con un acumulador para que el compilador pueda transformarlo (básicamente) en un bucle
2. No vuelva a calcular las longitudes de secuencia para las comparaciones
3. No uses div resp. divMod cuando no es necesario, "resp. quotRem son mucho más rápidos

¿Qué falta todavía?

if (j % 2 == 0)
    j = j / 2;
else
    j = 3 * j + 1;

Cualquier compilador de C que haya usado transforma la prueba j % 2 == 0 en un enmascaramiento de bits y no usa una instrucción de división. GHC no (todavía) hace eso. Por lo tanto, probar even n o computar n `quotRem` 2 es una operación bastante costosa. Reemplazo de nextNumber en la versión Integer de KennyTM con

nextNumber :: Integer -> Integer
nextNumber n
    | fromInteger n .&. 1 == (0 :: Int) = n `quot` 2
    | otherwise = 3*n+1

reduce su tiempo de ejecución a 3.25 segundos (Nota: para Integer , n `quot` 2 es más rápido que n `shiftR` 1 , ¡eso lleva 12.69 segundos!).

Hacer lo mismo en la versión Int reduce su tiempo de ejecución a 0,41 segundos. Para Int s, el desplazamiento de bits para la división por 2 es un poco más rápido que la operación de quot , reduciendo su tiempo de ejecución a 0,39 segundos.

Eliminando la construcción de la lista (que tampoco aparece en la versión C),

module Main (main) where

import Data.Bits

result :: Int
result = findMax 0 0 1

findMax :: Int -> Int -> Int -> Int
findMax start len can
    | can > 1000000 = start
    | canlen > len = findMax can canlen (can+1)
    | otherwise = findMax start len (can+1)
      where
        canlen = findLen 1 can

findLen :: Int -> Int -> Int
findLen l 1 = l
findLen l n
    | n .&. 1 == 0  = findLen (l+1) (n `shiftR` 1)
    | otherwise     = findLen (l+1) (3*n+1)

main :: IO ()
main = print result

produce una pequeña aceleración adicional, lo que resulta en un tiempo de ejecución de 0,37 segundos.

Así que la versión de Haskell que está en estrecha correspondencia con la versión C no toma mucho tiempo, es un factor de ~ 1.3.

Bueno, seamos justos, hay una ineficiencia en la versión C que no está presente en las versiones Haskell,

if (this_terms > terms)
{
    terms = this_terms;
    longest = i;
}

apareciendo en el bucle interno. Eliminar eso del bucle interno en la versión C reduce su tiempo de ejecución a 0.27 segundos, haciendo que el factor sea ~ 1.4.

Answer 2

Incluso si llego un poco tarde, aquí está el mío, eliminé la dependencia de las listas y esta solución no utiliza ningún montón también.

{-# LANGUAGE BangPatterns #-}
-- Compiled with ghc -O2 -fvia-C -optc-O3 -Wall euler.hs
module Main (main) where

searchTo :: Int
searchTo = 1000000

nextNumber :: Int -> Int
nextNumber n = case n `divMod` 2 of
   (k,0) -> k
   _     -> 3*n + 1

sequenceLength :: Int -> Int
sequenceLength n = sl 1 n where
  sl k 1 = k
  sl k x = sl (k + 1) (nextNumber x)

longestSequence :: Int
longestSequence = testValues 1 0 0 where
  testValues number !longest !longestNum
    | number > searchTo     = longestNum
    | otherwise            = testValues (number + 1) longest'' longestNum'' where
    nlength  = sequenceLength number
    (longest'',longestNum'') = if nlength > longest
      then (nlength,number)
      else (longest,longestNum)

main :: IO ()
main = print longestSequence

ghc -O2 -fvia-C -optc-O3 -Wall euler.hs esta pieza con ghc -O2 -fvia-C -optc-O3 -Wall euler.hs y se ejecuta en 5 segundos, en comparación con 80 de la implementación inicial. No usa Integer , pero como estoy en una máquina de 64 bits, los resultados pueden ser engañados.

El compilador puede desempaquetar todos los Int s en este caso, lo que resulta en un código realmente rápido. Funciona más rápido que todas las otras soluciones que he visto hasta ahora, pero C es aún más rápido.

Answer 3

La comparación puede ser la sequenceLength recálculo de la longitud demasiado. Esta es mi mejor versión:

type I = Integer
data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !I deriving (Eq,Ord,Show)

searchTo = 1000000

nextNumber :: I -> I
nextNumber n = case quotRem n 2 of
                  (n2,0) -> n2
                  _ -> 3*n+1

sequenceLength :: I -> Int
sequenceLength x = count x 1 where
  count 1 acc = acc
  count n acc = count (nextNumber n) (succ acc)

longestSequence = maximum . map (/i -> P (sequenceLength i) i) $ [1..searchTo]

main = putStrLn $ show $ longestSequence

La respuesta y el tiempo son más lentos que C, pero utilizan enteros de precisión arbitrarios (a través del tipo Integer ):

ghc -O2 --make euler14-fgij.hs
time ./euler14-fgij
P 525 837799

real 0m3.235s
user 0m3.184s
sys  0m0.015s

Answer 4

Las listas de Haskell están basadas en el montón, mientras que su código C es extremadamente estricto y no hace ningún uso del montón. Es necesario refactorizar para eliminar la dependencia en las listas.

Answer 5

Para propósitos de prueba acabo de establecer searchTo = 100000 . El tiempo tomado es de 7.34s . Algunas modificaciones llevan a una gran mejora:

1. Utilice un número Integer lugar de Int64 . Esto mejora el tiempo a 1.75s .

2. Use un acumulador (no necesita la secuencia de longitud para ser perezoso, ¿no?) 1.54s .

   seqLen2 :: Int -> Integer -> Int
   seqLen2 a 1 = a
   seqLen2 a n = seqLen2 (a+1) (nextNumber n)
   
   sequenceLength :: Integer -> Int
   sequenceLength = seqLen2 1

3. Reescriba el siguiente nextNumber usando " quotRem , evitando así calcular la división dos veces (una en una y otra en la div ). 1.27s .

   nextNumber :: Integer -> Integer
   nextNumber n 
       | r == 0    = q
       | otherwise = 6*q + 4
       where (q,r) = quotRem n 2 

4. Usa la transformada de Schwartz en lugar de la maximumBy . El problema de maximumBy . comparing maximumBy . comparing es que la función sequenceLength se llama más de una vez para cada valor. 0.32s .

   longestSequence = snd $ maximum [(sequenceLength a, a) | a <- [1..searchTo]]

Nota:

• Reviso la hora compilando con ghc -O y corro con +RTS -s )
• Mi máquina se ejecuta en Mac OS X 10.6. La versión de GHC es 6.12.2. El archivo compilado está en la arquitectura i386.)
• El problema C se ejecuta en 0.078s con el parámetro correspondiente. Se compila con gcc -O3 -m32 .