2012-04-13 2 views
6

Tengo un programa que produce una serie de funciones f y g que se parece a lo siguiente:Cómo acelerar (o memoize) una serie de funciones mutuamente recursivas

step (f,g) = (newF f g, newG f g) 

newF f g x = r (f x) (g x) 
newG f g x = s (f x) (g x) 

foo = iterate step (f0,g0) 

Donde r y s son algunos sin interés funciones de f x y g x. Ingenuamente esperaba que tener foo ser una lista significaría que cuando llamo al n'th f no volverá a calcular el (n-1) th f si ya lo ha calculado (como hubiera sucedido si f y g no fueran funciones). ¿Hay alguna manera de memorizar esto sin romper todo el programa (por ejemplo, evaluando f0 y g0 en todos los argumentos relevantes y luego trabajando hacia arriba)?

+2

Volver a calcular la n'th 'f' repetidamente no vuelve a calcular el (n-1) 'th' f' repetidamente ... pero recuerde, volver a calcular una función no significa lo mismo que volver a calcular el resultado de una llamada una función con un argumento! –

Respuesta

0

Puede encontrar Data.MemoCombinators útil (en el paquete data-memocombinators).

Usted no dice qué tipos argumento de su toma y fg --- si ambos toma valores enteros, entonces sería utilizar de esta manera:

import qualified Data.MemoCombinators as Memo 

foo = iterate step (Memo.integral f0, Memo.integral g0) 

Si es necesario, se podría memoise la salida de cada paso también

step (f,g) = (Memo.integral (newF f g), Memo.integral (newG f g)) 

Espero que no vea esto como una ruptura de todo el programa.


En respuesta a su comentario:

Esto es lo mejor que puedo llegar a. No se ha probado, pero debería funcionar en la línea correcta.

Me preocupa que la conversión entre DoubleRational y es innecesariamente ineficaz --- si había una instancia Bits para Double podríamos utilizar Memo.bits lugar. Por lo tanto, esto podría no ser útil para ti en última instancia.

import Control.Arrow ((&&&)) 
import Data.Ratio (numerator, denominator, (%)) 

memoV :: Memo.Memo a -> Memo.Memo (V a) 
memoV m f = \(V x y z) -> table x y z 
    where g x y z = f (V x y z) 
     table = Memo.memo3 m m m g 

memoRealFrac :: RealFrac a => Memo.Memo a 
memoRealFrac f = Memo.wrap (fromRational . uncurry (%)) 
          ((numerator &&& denominator) . toRational) 
          Memo.integral 

Un enfoque diferente.

Tienes

step :: (V Double -> V Double, V Double -> V Double) 
    -> (V Double -> V Double, V Double -> V Double) 

¿Qué cambia eso a

step :: (V Double -> (V Double, V Double)) 
    -> (V Double -> (V Double, V Double)) 
step h x = (r fx gx, s fx gx) 
    where (fx, gx) = h x 

y también cambiar

foo = (fst . bar, snd . bar) 
    where bar = iterate step (f0 &&& g0) 

Esperemos que la compartían fx y gx debería resultar en un poco de velocidad -arriba.

+0

Gracias por la gran respuesta. El único problema que veo con este enfoque es que 'f' y' g' tienen el tipo 'V Double -> V Double' donde' data V a = V aaa' y no es exactamente claro para mí cómo escribiría un " 'Memo.v'" o si eso es posible. –

+1

@SeanD Ver mi edición. – dave4420

0

¿Hay alguna manera de memorizar esto sin separar todo el programa (por ejemplo, evaluando f0 y g0 en todos los argumentos relevantes y luego trabajando hacia arriba)?

Esto puede ser lo que quiere decir con "rasga todo el programa aparte", pero aquí es una solución en la que (creo, pero no puedo probar ATM) fooX puede ser compartido.

nthFooOnX :: Integer -> Int -> (Integer, Integer) 
nthFooOnX x = 
    let fooX = iterate step' (f0 x, g0 x) 
    in \n-> fooX !! n 

step' (fx,gx) = (r fx gx, s fx gx) 

-- testing definitions: 
r = (+) 
s = (*) 
f0 = (+1) 
g0 = (+1) 

No sé si eso conserva el espíritu de su implementación original.

Cuestiones relacionadas