¿Cómo se puede profundizar iterativo de búsqueda implementado eficiente en Haskell?

Question

Tengo un problema de optimización que quiero resolver. Usted tiene algún tipo de técnica de estructura:

data Foo =
  { fooA :: Int
  , fooB :: Int
  , fooC :: Int
  , fooD :: Int
  , fooE :: Int
}

y una función de clasificación:

rateFoo :: myFoo -> Int

I tiene que optimizar el resultado de rateFoo cambiando los valores en el struct. En este caso específico, decidí usar iterativo de búsqueda profundización para resolver el problema. El (infinito) árbol de búsqueda de la mejor optimización se crea por otra función, que se limita a aplicar todos los cambios posibles recursivamente al árbol:

fooTree :: Foo -> Tree

Mi búsqueda miradas función algo como esto:

optimize :: Int -> Foo -> Foo
optimize threshold foo = undefined

La pregunta que tenía, antes de empezar es la siguiente:

A medida que el árbol puede ser generado por los datos en cada punto, es posible tener sólo las partes del árbol generado, que actualmente son necesarios por el algoritmo? ¿Es posible tener la memoria liberada y el árbol regenerado si es necesario con el fin de ahorrar memoria (Un permiso en el nivel n se pueden generar en O(n) yn sigue siendo pequeña, pero no lo suficientemente pequeño como para tener todo el árbol en la memoria con el tiempo)?

Es esto algo que puedo excpect desde el tiempo de ejecución? ¿Puede el tiempo de ejecución unevaluate Las expresiones (a su vez una expresión evaluada en un uno sin evaluar)? O lo que es lo sucio piratear que tengo que hacer para esto?

Answer 1

Este es mi consejo:

1. Sólo implementar el algoritmo en el la mayoría manera directa posible.
2. Perfil.
3. Optimizar para velocidad o el uso de memoria si es necesario.

muy rápidamente aprendió que no soy inteligente y / o experiencia suficiente para razonar acerca de lo que va a hacer GHC o cómo la recolección de basura va a funcionar. A veces las cosas que estoy seguro será desastrosa memoria de trabajo ineficiente sin problemas la primera vez, y con menos frecuencia, cosas que parecen simples requieren una gran cantidad de quejarse con anotaciones de estrictez, etc.

El Real World Haskell de perfiles y optimización es increíblemente útil una vez que llegue a los pasos 2 y 3.

---

Por ejemplo, he aquí una muy simple aplicación de IDDFS, donde se expande f niños, p es el predicado de búsqueda, y x es el punto de partida.

search :: (a -> [a]) -> (a -> Bool) -> a -> Bool
search f p x = any (\d -> searchTo f p d x) [1..]
  where
    searchTo f p d x
      | d == 0    = False
      | p x       = True
      | otherwise = any (searchTo f p $ d - 1) (f x)

I probado mediante la búsqueda de "abbaaaaaacccaaaaabbaaccc" con children x = [x ++ "a", x ++ "bb", x ++ "ccc"] como f. Parece razonablemente rápido y requiere muy poca memoria (lineal con la profundidad, creo). ¿Por qué no intentar algo como esto primero y luego pasar a una estructura de datos más complicado si no es lo suficientemente bueno?

Answer 2

El tiempo de ejecución hace expresiones no unevaluate.

Hay una manera fácil de obtener lo que desea sin embargo.

Considere una cremallera-como la estructura para su árbol. Cada nodo tiene un valor y un procesador que representa abajo, arriba, etc. Cuando se mueve al siguiente nodo, o bien se pueden mover normalmente (colocando el valor de nodo anterior en la ranura correspondiente) o forgetfully (colocando una expresión que evalúa a la anterior nodo en la ranura derecha). Entonces usted tiene el control sobre la cantidad de "historia" que agarrarse.