performance - programacion - ¿Cómo se escriben algoritmos de programación dinámica eficientes en Haskell?

programacion dinamica pdf

Question

He estado jugando con la programación dinámica en Haskell. Prácticamente todos los tutoriales que he visto sobre el tema ofrecen el mismo algoritmo muy elegante basado en la memoria y la pereza del tipo Array. Inspirado por esos ejemplos, escribí el siguiente algoritmo como una prueba:

-- pascal n returns the nth entry on the main diagonal of pascal''s triangle
-- (mod a million for efficiency)
pascal :: Int -> Int
pascal n  = p ! (n,n) where
           p = listArray ((0,0),(n,n)) [f (i,j) | i <- [0 .. n], j <- [0 .. n]]

           f :: (Int,Int) -> Int
           f (_,0) = 1
           f (0,_) = 1
           f (i,j) = (p ! (i, j-1) + p ! (i-1, j)) `mod` 1000000 

Mi único problema es la eficiencia. Incluso utilizando GHC -O2, este programa tarda 1.6 segundos en calcular el pascal 1000 , que es aproximadamente 160 veces más lento que un programa equivalente de C ++ no optimizado. Y la brecha solo se amplía con entradas más grandes.

Parece que he intentado todas las permutaciones posibles del código anterior, junto con alternativas sugeridas como la biblioteca de memocombinators de datos, y todas tienen el mismo o peor desempeño. Lo único que no he probado es la ST Monad, que estoy seguro de que se podría hacer para ejecutar el programa más lento que la versión C. Pero realmente me gustaría escribirlo en Haskell idiomático, y no entiendo por qué la versión idiomática es tan ineficiente. Tengo dos preguntas:

1. ¿Por qué el código anterior es tan ineficiente? Parece una iteración directa a través de una matriz, con una operación aritmética en cada entrada. Claramente, Haskell está haciendo algo detrás de la escena que no entiendo.

2. ¿Hay una manera de hacerlo mucho más eficiente (como máximo 10-15 veces el tiempo de ejecución de un programa C) sin sacrificar su formulación recursiva y sin estado (en comparación con una implementación que utiliza arreglos mutables en la Mónada ST)?

Muchas gracias.

Edición: el módulo de matriz utilizado es el estándar Data.Array

Answer 1

1 ¿Por qué el código anterior es tan ineficiente? Parece una iteración directa a través de una matriz, con una operación aritmética en cada entrada. Claramente, Haskell está haciendo algo detrás de la escena que no entiendo.

El problema es que el código escribe Thunks en la matriz. Luego, cuando se lee la entrada (n,n) , la evaluación de los thunks vuelve a saltar por toda la matriz, recurriendo hasta que finalmente se encuentra un valor que no necesita recursión adicional. Eso causa mucha asignación innecesaria e ineficiencia.

El código C ++ no tiene ese problema, los valores se escriben y se leen directamente sin requerir una evaluación adicional. Como sucedería con un STUArray . Hace

p = runSTUArray $ do
    arr <- newArray ((0,0),(n,n)) 1
    forM_ [1 .. n] $ /i ->
        forM_ [1 .. n] $ /j -> do
            a <- readArray arr (i,j-1)
            b <- readArray arr (i-1,j)
            writeArray arr (i,j) $! (a+b) `rem` 1000000
    return arr

realmente se ve tan mal?

2 ¿Hay una manera de hacerlo mucho más eficiente (como máximo 10-15 veces el tiempo de ejecución de un programa de C) sin sacrificar su formulación recursiva y sin estado (en comparación con una implementación que utiliza matrices mutables en la Mónada ST)?

No sé de uno. Pero podría haber.

Apéndice:

Una vez que uno usa STUArray o Vector caja, todavía hay una diferencia significativa en la implementación de C equivalente. La razón es que gcc reemplaza el % por una combinación de multiplicaciones, desplazamientos y restas (incluso sin optimizaciones), ya que el módulo es conocido. Haciendo lo mismo a mano en Haskell (ya que GHC no [todavía] hace eso),

-- fast modulo 1000000
-- for nonnegative Ints < 2^31
-- requires 64-bit Ints
fastMod :: Int -> Int
fastMod n = n - 1000000*((n*1125899907) `shiftR` 50)

consigue las versiones de Haskell a la par con C.

Answer 2

Bueno, el algoritmo podría ser diseñado un poco mejor. Al usar el paquete vector y ser inteligente al solo mantener una fila en la memoria a la vez, podemos obtener algo que es idiomático de una manera diferente:

{-# LANGUAGE BangPatterns #-}
import Data.Vector.Unboxed
import Prelude hiding (replicate, tail, scanl)

pascal :: Int -> Int
pascal !n = go 1 ((replicate (n+1) 1) :: Vector Int) where
  go !i !prevRow
    | i <= n    = go (i+1) (scanl f 1 (tail prevRow))
    | otherwise = prevRow ! n
  f x y = (x + y) `rem` 1000000

Esto se optimiza muy estrechamente, especialmente porque el paquete vector incluye algunos trucos bastante ingeniosos para optimizar de forma transparente las operaciones de matriz escritas en un estilo idiomático.

Answer 3

El truco es pensar cómo escribir todo el maldito algoritmo a la vez, y luego usar vectores sin caja como tipo de datos de respaldo. Por ejemplo, lo siguiente se ejecuta unas 20 veces más rápido en mi máquina que su código:

import qualified Data.Vector.Unboxed as V

combine :: Int -> Int -> Int
combine x y = (x+y) `mod` 1000000

pascal n = V.last $ go n where
    go 0 = V.replicate (n+1) 1
    go m = V.scanl1 combine (go (m-1))

Luego escribí dos funciones main que llamaban a la tuya y la mía con un argumento de 4000; estos funcionaron en 10.42s y 0.54s respectivamente. Por supuesto, como estoy seguro de que saben, los dos se salen del agua ( 0.00s ) por la versión que usa un algoritmo mejor:

pascal'' :: Integer -> Integer
pascal :: Int -> Int
pascal'' n = product [n+1..n*2] `div` product [2..n]
pascal = fromIntegral . (`mod` 1000000) . pascal'' . fromIntegral