Wie kann iterative Tiefensuche effizient in Haskell implementiert?

Question

ich ein Optimierungsproblem ich lösen will, muss. Sie haben eine Art von Datenstruktur:

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

und eine Bewertungsfunktion:

rateFoo :: myFoo -> Int

Ich habe das Ergebnis rateFoo zu optimieren, indem die Werte in der Struktur zu verändern. In diesem speziellen Fall, habe ich beschlossen, verwenden iterative Vertiefung Suche , um das Problem zu lösen. Der (unendliche) Suchbaum für die beste Optimierung wird durch eine andere Funktion erstellt, die einfach trifft alle möglichen Änderungen rekursiv auf den Baum:

fooTree :: Foo -> Tree

Meine Suchfunktion sieht etwa so aus:

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

Die Frage, die ich hatte, bevor ich anfange, ist dies:

Wie der Baum kann durch die Daten an jedem Punkt erzeugt wird, ist es möglich, erzeugte nur die Teile des Baumes zu haben, die zur Zeit durch den Algorithmus benötigt werden? Ist es möglich, befreite den Speicher zu haben und den Baum regenerierte benötigt, um, wenn der Speicher zu speichern (A leave auf Stufe n kann in O(n) erzeugt werden und n bleibt klein, aber nicht klein genug, um den ganzen Baum in Erinnerung über die Zeit zu haben)?

Ist das etwas, was ich von der Laufzeit excpect kann? Kann die Laufzeit unevaluate Ausdrücke (wiederum einen ausgewertete Ausdruck in einen unbewertet ein)? Oder was ist das schmutzige hack ich dafür tun?

Answer 1

Hier ist mein Rat:

1. implementieren Sie einfach Ihren Algorithmus in der direkteste Art und Weise möglich.
2. Profil.
3. Optimieren für Geschwindigkeit oder Speichernutzung, falls erforderlich.

ich sehr schnell gelernt, dass ich bin nicht klug und / oder erfahren genug, um zu wissen, was Grund GHC tun oder wie Garbage Collection funktioniert. Manchmal Dinge, die ich bin sicher, werden katastrophal speicher ineffiziente Arbeit reibungslos beim ersten Mal, und weniger oft Dinge, die einfach scheinen erfordern viel mit Strengen Anmerkungen Getue, etc.

Die Real World Haskell Kapitel auf Profilierung und Optimierung unglaublich nützlich ist, wenn Sie auf die Schritte 2 und 3 erhalten.

---

Zum Beispiel, hier ist eine sehr einfache Implementierung von IDDFS, wo f Kinder erweitert, p ist die Suche Prädikat und x ist der Ausgangspunkt.

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 getestet, indem für "abbaaaaaacccaaaaabbaaccc" mit children x = [x ++ "a", x ++ "bb", x ++ "ccc"] als f suchen. Es scheint ziemlich schnell und erfordert nur sehr wenig Speicher (linear mit der Tiefe, glaube ich). Warum nicht so etwas wie dies zunächst versuchen, und dann zu einer komplizierteren Datenstruktur zu bewegen, wenn es nicht gut genug ist?

Answer 2

Die Laufzeit nicht unevaluate Ausdrücke.

Es gibt eine einfache Möglichkeit zu bekommen, was Sie jedoch wollen.

Betrachten wir eine reißverschlussartige Struktur für Ihren Baum. Jeder Knoten hält einen Wert und eine Thunk darstellen unten, oben, etc. Wenn Sie an den nächsten Knoten zu verschieben, kann man entweder normal bewegen (den vorherigen Knotenwert in dem entsprechenden Schlitz platziert) oder aus Vergesslichkeit (platzieren einen Ausdruck, den auswertet, um zum vorherigen Knoten in dem rechten Schlitz). Dann haben Sie die Kontrolle darüber, wie viel „Geschichte“ Sie hängen an.