java - programacion - Programación dinámica en el paradigma funcional.

programacion funcional ventajas y desventajas

Question

Estoy viendo el Problema treinta y uno en el Proyecto Euler, que pregunta cuántas maneras diferentes hay de hacer £ 2 usando cualquier número de monedas de 1p, 2p, 5p, 10p, 20p, 50p, £ 1 (100p) y £ 2 (200p).

Hay soluciones recursivas, como esta en Scala (crédito a Pavel Fatin)

def f(ms: List[Int], n: Int): Int = ms match {
  case h :: t =>
    if (h > n) 0 else if (n == h) 1 else f(ms, n - h) + f(t, n)
  case _ => 0
} 
val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)

y aunque funciona lo suficientemente rápido, es relativamente ineficiente, ya que llama a la función f alrededor de 5.6 millones de veces.

Vi la solución de otra persona en Java que se programó dinámicamente (crédito a Wizeman de Portugal)

final static int TOTAL = 200;

public static void main(String[] args) {
    int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
    int[] ways = new int[TOTAL + 1];
    ways[0] = 1;

    for (int coin : coins) {
        for (int j = coin; j <= TOTAL; j++) {
            ways[j] += ways[j - coin];
        }
    }

    System.out.println("Result: " + ways[TOTAL]);
}

Esto es mucho más eficiente y pasa el bucle interno solo 1220 veces.

Si bien obviamente podría traducir esto más o menos literalmente en Scala usando objetos Array , ¿hay una forma funcional idiomática de hacerlo usando estructuras de datos inmutables, preferiblemente con una concisión y rendimiento similares?

He intentado y me quedo estancado tratando de actualizar recursivamente una List antes de decidir que probablemente me estoy acercando a ella de manera incorrecta.

Answer 1

Cada vez que una parte de una lista de datos se calcula en función de un elemento anterior, pienso en la recursión de Stream . Desafortunadamente, tal recursión no puede ocurrir dentro de las definiciones de los métodos o funciones, por lo que tuve que convertir una función en una clase para que funcione.

class IterationForCoin(stream: Stream[Int], coin: Int) {
  val (lower, higher) = stream splitAt coin
  val next: Stream[Int] = lower #::: (higher zip next map { case (a, b) => a + b })
}
val coins = List(1, 2, 5, 10, 20, 50, 100, 200)
val result = coins.foldLeft(1 #:: Stream.fill(200)(0)) { (stream, coin) =>
  new IterationForCoin(stream, coin).next
} last

Las definiciones de lower y higher no son necesarias; podría reemplazarlos fácilmente con stream take coin y stream drop coin , pero creo que es un poco más claro (y más eficiente) de esta manera.

Answer 2

En aras de la integridad, aquí hay una ligera variante de la respuesta anterior que no usa Stream :

object coins {
  val coins = List(1, 2, 5, 10, 20, 50, 100, 200)
  val total = 200
  val result = coins.foldLeft(1 :: List.fill(total)(0)) { (list, coin) =>
    new IterationForCoin(list, coin).next(total)
  } last
}

class IterationForCoin(list: List[Int], coin: Int) {
  val (lower, higher) = list splitAt coin
  def next (total: Int): List[Int] = {
    val listPart = if (total>coin) next(total-coin) else lower
    lower ::: (higher zip listPart map { case (a, b) => a + b })
  }
}

Answer 3

La programación dinámica funcional puede ser realmente hermosa en un lenguaje perezoso, como Haskell (hay haskell.org/haskellwiki/Dynamic_programming_example en la wiki de Haskell). Esta es una solución de programación dinámica para el problema:

import Data.Array

makeChange :: [Int] -> Int -> Int
makeChange coinsList target = arr ! (0,target)
  where numCoins = length coinsList
        coins    = listArray (0,numCoins-1) coinsList
        bounds   = ((0,0),(numCoins,target))
        arr      = listArray bounds . map (uncurry go) $ range bounds
        go i n   | i == numCoins = 0
                 | otherwise     = let c = coins ! i
                                   in case c `compare` n of
                                        GT -> 0
                                        EQ -> 1
                                        LT -> (arr ! (i, n-c)) + (arr ! (i+1,n))

main :: IO ()
main = putStrLn $  "Project Euler Problem 31: "
                ++ show (makeChange [1, 2, 5, 10, 20, 50, 100, 200] 200)

Es cierto que esto utiliza la memoria O ( cn ), donde c es el número de monedas y n es el objetivo (a diferencia de la memoria O ( n ) de la versión de Java); para conseguir eso, tendrías que usar alguna técnica de captura de estado mutable (probablemente un STArray ). Sin embargo, ambos se ejecutan en tiempo O ( cn ). La idea es codificar la solución recursiva de forma casi directamente recursiva, pero en lugar de hacerlo de forma recurrente, buscamos la respuesta en la matriz. ¿Y cómo construimos la matriz? Al llamar a ir en cada índice. Ya que Haskell es perezoso, solo calcula las cosas cuando se le pide, por lo que todo el orden de evaluación necesario para la programación dinámica se maneja de manera transparente.

Y gracias a los parámetros de nombre de Scala y los valores lazy val , podemos imitar esta solución en Scala:

class Lazy[A](x: => A) {
  lazy val value = x
}

object Lazy {
  def apply[A](x: => A) = new Lazy(x)
  implicit def fromLazy[A](z: Lazy[A]): A = z.value
  implicit def toLazy[A](x: => A): Lazy[A] = Lazy(x)
}

import Lazy._

def makeChange(coins: Array[Int], target: Int): Int = {
  val numCoins = coins.length
  lazy val arr: Array[Array[Lazy[Int]]]
    = Array.tabulate(numCoins+1,target+1) { (i,n) =>
        if (i == numCoins) {
          0
        } else {
          val c = coins(i)
          if (c > n)
            0
          else if (c == n)
            1
          else
            arr(i)(n-c) + arr(i+1)(n)
        }
      }
  arr(0)(target)
}

// makeChange(Array(1, 2, 5, 10, 20, 50, 100, 200), 200)

La clase Lazy codifica valores que solo se evalúan a pedido, y luego construimos una matriz completa de ellos. Ambas soluciones funcionan para un valor objetivo de 10000 prácticamente al instante, aunque son mucho más grandes y se encontrará con un desbordamiento de enteros o (en Scala, al menos) un desbordamiento de pila.

Answer 4

No sé lo suficiente acerca de Scala para comentar específicamente sobre eso, pero la forma típica de traducir una solución de DP a una recursiva es a través de la memoria (use http://en.wikipedia.org/wiki/Memoization ). Básicamente, esto es el almacenamiento en caché del resultado de su función para todos los valores del dominio.

También encontré esto en http://michid.wordpress.com/2009/02/23/function_mem/ . HTH

Answer 5

Ok, aquí está la versión memorizada del código de Pavel Fatin. Estoy usando cosas de memoización de Scalaz, aunque es realmente sencillo escribir tu propia clase de memoización.

import scalaz._
import Scalaz._

val memo = immutableHashMapMemo[(List[Int], Int), Int]
def f(ms: List[Int], n: Int): Int = ms match {
  case h :: t =>
    if (h > n) 0 else if (n == h) 1 else memo((f _).tupled)(ms, n - h) + memo((f _).tupled)(t, n)
  case _ => 0
} 
val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)