ventajas programacion paradigma orientada objetos funcional desventajas java scala functional-programming dynamic-programming

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



programacion funcional ventajas y desventajas (5)

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.

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.

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 }) } }

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.

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)