Динамическое программирование в функциональной парадигме

Question

Я смотрю на Задача тридцать одна в Project Euler, которая спрашивает, сколько существует способов заработать £ 2, используя любое количество монет 1p, 2p, 5p, 10p, 20p, 50 пенсов, 1 фунт (100 пенсов) и 2 фунта (200 пенсов).

Есть рекурсивные решения, такие как это в Scala (кредит Павлу Фатину)

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)

и хотя он работает достаточно быстро, он относительно неэффективен, вызывая функцию f около 5,6 миллионов раз.

Я видел чье-то решение на Java, которое программировалось динамически (кредит wizeman из Португалии)

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

Это намного эффективнее и проходит внутренний цикл только 1220 раз.

Хотя я мог бы, очевидно, перевести этот более или менее дословно в Scala, используя Array объекты, существует ли идиоматический функциональный способ сделать это, используя неизменные структуры данных, предпочтительно с аналогичной краткостью и производительностью?

Я пытался застрять, пытаясь рекурсивно обновить List, прежде чем решить, что, вероятно, просто подхожу к нему неправильно.

Answer 1

Всякий раз, когда некоторая часть списка данных вычисляется на основе предыдущего элемента, я думаю о Stream рекурсии. К сожалению, такая рекурсия не может происходить внутри определений методов или функций, поэтому мне пришлось превратить функцию в класс, чтобы она работала.

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

Определения lower и higher не являются необходимыми - я мог бы легко заменить их на stream take coin и stream drop coin, но я думаю, что это немного яснее (и эффективнее) таким образом.

Answer 2

Я не знаю достаточно о Scala, чтобы комментировать конкретно, но типичный способ перевести решение DP в рекурсивное - это запоминание (используйте http://en.wikipedia.org/wiki/Memoization). Это в основном кеширование результата вашегофункция для всех значений домена

Я также нашел это http://michid.wordpress.com/2009/02/23/function_mem/. HTH

Answer 3

Функциональное динамическое программирование может быть действительно красивым на ленивом языке, таком как Haskell (на нем есть статья в вики Haskell). Это динамическое программирование решения проблемы:

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)

Следует признать, что используется память O ( cn ), где c - это количество монет, а n - цель (в отличие от версии Java). O ( n ) памяти); чтобы получить это, вы должны использовать некоторую технику захвата изменяемого состояния (вероятно, STArray). Тем не менее, они оба работают в O ( cn ) время. Идея состоит в том, чтобы закодировать рекурсивное решение почти непосредственно рекурсивно, но вместо рекурсии в go мы ищем ответ в массиве. И как мы строим массив? Позвонив по номеру , перейдите на каждый индекс. Поскольку Haskell является ленивым, он вычисляет только то, что ему нужно, поэтому все элементы порядка оценки, необходимые для динамического программирования, обрабатываются прозрачно.

А благодаря параметрам имени Scala и lazy val s мы можем имитировать это решение в 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)

Класс Lazy кодирует значения, которые оцениваются только по требованию, а затем мы строим массив, полный из них. Оба эти решения практически мгновенно достигают целевого значения в 10000, хотя становятся намного больше, и вы столкнетесь либо с целочисленным переполнением, либо (по крайней мере, в Scala) переполнением стека.

Answer 4

Хорошо, вот памятная версия кода Павла Фатина.Я использую Scalaz для запоминания, хотя написать собственный класс для запоминания очень просто.

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)

Answer 5

Для полноты изложения приведем небольшой вариант ответа выше, в котором не используется 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 })
  }
}