Ich baue einige ziemlich große DIMACS Dateien, allerdings mit der Methode, die unterhalb der Speicherbelegung verwendet wird ist ziemlich groß im Vergleich zur Größe der erzeugten Dateien, und auf einigen der größeren Dateien, die ich generieren muss, laufe ich zu out of memory problems.
Ich möchte das monadische Aufbauen von Klauseln beibehalten, da es sehr praktisch ist, aber ich muss das Speicherproblem überwinden. Wie optimiere ich das obige Programm, damit es nicht zu viel Speicher verwendet?
Wenn Sie ein gutes Speicherverhalten wünschen, müssen Sie sicherstellen, dass Sie die Klauseln beim Generieren ausschreiben, anstatt sie im Speicher zu sammeln und sie als solche zu speichern, entweder durch Lazyness oder einen expliziteren Ansatz wie Conduits, Aufzähler, Pipes oder ähnliches.
Das Haupthindernis für diesen Ansatz besteht darin, dass das DIMACS-Format die Anzahl der Klauseln und Variablen im Header erwartet. Dies verhindert, dass die naive Implementierung ausreichend faul ist. Es gibt zwei Möglichkeiten:
Die pragmatische Methode besteht darin, die Klauseln zuerst in einen temporären Ort zu schreiben. Danach sind die Nummern bekannt, also schreibst du sie in die reale Datei und fügst den Inhalt der temporären Datei an.
Der schönere Ansatz ist möglich, wenn die Erzeugung von Klauseln keine Nebeneffekte hat (neben den Effekten von DIMACSM monad) und ausreichend schnell ist: Führen Sie es zweimal aus, werfen Sie zuerst die Klauseln weg und berechnen Sie einfach die Zahlen, drucken Sie die Kopfzeile, den Generator erneut laufen lassen; Jetzt drucken Sie die Klauseln.
(Das ist aus meiner Erfahrung mit der Implementierung von SAT-Britney , wo ich den zweiten Ansatz genommen habe, weil es passte besser zu anderen Anforderungen in diesem Kontext.)
Außerdem ist addAll in Ihrem Code nicht faul genug: Die Liste c muss auch nach dem Schreiben (in MonadWriter sense) der Klauseln beibehalten werden. Dies ist ein weiteres Leck im Weltraum. Ich schlage vor, dass Sie add als primitive Operation und dann addAll = mapM_ add implementieren.
Wie in Joachim Breitners Antwort erklärt, war das Problem, dass DIMACSM nicht faul genug war, sowohl weil die strikten Versionen der Monaden verwendet wurden als auch weil die Anzahl der Variablen und Klauseln benötigt wird, bevor ByteString geschrieben werden kann die Datei. Die Lösung besteht darin, die faulen Versionen der Monaden zu verwenden und sie zweimal auszuführen. Es stellt sich heraus, dass auch WriterT die äußere Monade sein muss:
Tags und Links haskell