Comment peut-itérative approfondir la recherche mise en œuvre efficace haskell?

Question

J'ai un problème d'optimisation que je veux résoudre. Vous avez une sorte de structure de données:

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

et une fonction de notation:

rateFoo :: myFoo -> Int

I ai pour optimiser le résultat de rateFoo en changeant les valeurs dans le struct. Dans ce cas spécifique, j'ai décidé d'utiliser recherche itérative approfondissement pour résoudre le problème. Le (infini) arbre de recherche de la meilleure optimisation est créée par une autre fonction, qui applique simplement tous les changements possibles récursivement à l'arbre:

fooTree :: Foo -> Tree

Ma fonction de recherche ressemble à quelque chose comme ceci:

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

La question que j'avais, avant de commencer est la suivante:

  

Comme l'arbre peut être généré par les données à chaque point, est-il possible d'avoir seulement les parties de l'arbre généré, qui sont actuellement nécessaires par l'algorithme? Est-il possible d'avoir la mémoire libérée et l'arbre régénéré si nécessaire afin d'économiser de la mémoire (un congé au niveau n peut être généré en O(n) et n reste faible, mais pas assez petit pour avoir l'ensemble arbre en mémoire au fil du temps)?

     

Est-ce que je peux excpect de l'exécution? Peut-le runtime unevaluate expressions (transformer une expression évaluée dans un un non évalué)? Ou quel est le sale pirater que je dois faire pour cela?

Answer 1

Voici mon conseil:

1. Il suffit de mettre en œuvre votre algorithme dans le manière la plus simple possible.
2. Profil.
3. Optimiser pour la vitesse ou de la mémoire si nécessaire.

J'ai très vite appris que je ne suis pas intelligent et / ou assez expérimenté pour raisonner sur ce que GHC fera ou comment la collecte des ordures fonctionnera. Parfois, les choses que je suis sûr, sera lamentablement travail inefficace mémoire en douceur la première fois, et moins souvent les choses qui semblent simples exigent beaucoup d'embêter avec annotations strictness, etc.

Real World Haskell chapitre sur le profilage et optimisation est incroyablement utile une fois que vous arrivez à les étapes 2 et 3.

---

Par exemple, voici une implémentation très simple de IDDFS, où f étend les enfants, p est le prédicat de recherche et x est le point de départ.

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)

J'ai testé en recherchant "abbaaaaaacccaaaaabbaaccc" avec children x = [x ++ "a", x ++ "bb", x ++ "ccc"] comme f. Il semble assez rapide et ne nécessite que très peu de mémoire (linéaire avec la profondeur, je pense). Pourquoi ne pas essayer quelque chose comme ça d'abord, puis passer à une structure de données plus compliquée si elle est pas assez bon?

Answer 2

Le moteur d'exécution ne expressions pas unevaluate.

Il y a une façon simple d'obtenir ce que vous voulez cependant.

Considérons une structure semblable à fermeture à glissière pour votre arbre. Chaque noeud contient une valeur et un thunk représentant vers le bas, en haut, etc. Lorsque vous passez au nœud suivant, vous pouvez déplacer normalement (en plaçant la valeur du noeud précédent dans la fente correspondante) ou par distraction (en plaçant une expression qui évalue à la précédente le noeud dans la fente à droite). Ensuite, vous avez le contrôle sur la quantité de « l'histoire » vous accrochez à.