Динамическое программирование в функциональной парадигме
Я смотрю на проблему тридцать первую в Project Euler, которая спрашивает, сколько существует различных способов заработать 2 фунта, используя любое количество монет 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) и £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 прежде чем решить, что я, вероятно, просто подхожу к этому неправильно.
5 ответов
Всякий раз, когда некоторая часть списка данных вычисляется на основе предыдущего элемента, я думаю о 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, но я думаю, что это немного яснее (и эффективнее) таким образом.
Я не знаю достаточно о Scala, чтобы комментировать конкретно, но типичным способом преобразования решения DP в рекурсивное является запоминание (используйте http://en.wikipedia.org/wiki/Memoization). Это в основном кеширование результата вашей функции для всех значений домена
Я также нашел это http://michid.wordpress.com/2009/02/23/function_mem/. НТН
Функциональное динамическое программирование может быть действительно красивым на ленивом языке, таком как 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 - цель (в отличие от памяти O (n) версии Java); чтобы получить это, вы должны использовать некоторую технику захвата изменяемого состояния (вероятно, STArray). Тем не менее, они оба работают за O (cn) время. Идея состоит в том, чтобы закодировать рекурсивное решение практически непосредственно рекурсивно, но вместо того, чтобы рекурсировать в go, мы ищем ответ в массиве. И как мы строим массив? По звонкам идут на каждый индекс. Поскольку Haskell ленив, он вычисляет только то, что ему нужно, поэтому все, что нужно для динамического программирования, - порядок оценки, который обрабатывается прозрачно.
И благодаря именным параметрам Scala и lazy vals, мы можем имитировать это решение в 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) переполнением стека.
Хорошо, вот памятная версия кода Павла Фатина. Я использую 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)
Для полноты изложения приведу небольшой вариант ответа выше, который не использует 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 })
}
}