Ich denke darüber nach, Parallelität für ein Problem zu nutzen, das ich zu lösen versuche. Das Problem ist ungefähr das: gegebene Eingabe (Folge von Punkten) finde eine beste Ausgabe (größtes Dreieck, das aus diesen Punkten, der längsten Linie usw. zusammengesetzt ist). Es gibt 3 verschiedene "Formen" in der Reihenfolge der Punkte, aber ich interessiere mich nur für diejenige mit "bestem Ergebnis" (normalerweise irgendeine Form von 'Länge' mal Koeffizient). Nennen wir die Formen S1, S2, S3.
Ich habe zwei verschiedene Algorithmen zum Lösen von S1 - 'S1a' ist in O (n 2 ), 'S1b' verhält sich meistens besser, aber der schlechteste Fall ist ungefähr O (n 4) ).
Erste Frage: Gibt es eine einfache Möglichkeit, S1a und S1b parallel zu betreiben, die eine, die zuerst beendet wird und die andere stoppt? Soweit ich Dokumentation lese, könnte dies mit etwas ForkIO programmiert werden und die Threads töten, wenn ein Ergebnis erhalten wird - nur fragen, ob es etwas einfacher ist?
Zweite Frage - viel zäher: Ich rufe die Optimierungsfunktion so auf:
%Vor%valueOfSx ist für jede Form spezifisch und gibt eine mögliche Punktzahl (oder eine Schätzung einer Punktzahl) zurück. Optimize ruft diese Funktion auf, um die beste Lösung zu finden. Was mich interessiert, ist:
%Vor%Wenn ich jedoch das Ergebnis von S1 kenne, kann ich alle Lösungen, die kleiner sind, verwerfen, wodurch s2 und s3 schneller konvergieren, wenn keine bessere Lösung existiert (oder zumindest die schlechtesten Lösungen wegwerfen und somit platzsparender sein). . Was ich jetzt mache ist:
%Vor%Die Frage ist: Kann ich z.B. S2 und S3 parallel so, dass, je nachdem, welcher zuerst beendet wird, der Parameter 'threshold' der Score-Funktion, die im anderen Thread läuft, aktualisiert wird? Etwas im Sinne von:
%Vor%Für die erste Frage, schaut euch Conal Elliotts %code% : Ссылка
anLetztendlich wird jede Lösung unter Verwendung von ForkIO unter der Haube enden, weil Sie möchten, dass mehrere Transaktionen parallel stattfinden. Sogar Conals Einfall funktioniert auf diese Weise.
Für Letzteres möchten Sie wahrscheinlich eine kompliziertere Monade, die sich auflädt und eine Weile läuft, bevor Sie eine MVar gelegentlich auf einen monoton geposteten Verbesserungswert überprüfen, aber die einfachste Antwort auf Verschachtelung (innerhalb eines Threads) ist, nur eine Partialität zu schreiben Monade.
%Vor%Mit einer geeigneten MonadFix-Instanz, die Rekursion oder großzügig gestreute Yield-Aufrufe behandelt, können Sie beide Operationen in der partiellen Monade durchführen und sie zu einem deterministischen Ergebnis bringen.
Aber in der Praxis, wenn Sie die Vorteile der Parallelität voll ausschöpfen wollen, sollten Sie regelmäßig eine Art "Verbesserung" von MVar aktualisieren und überprüfen.
So etwas wie (aus dem Stegreif, tut mir leid, kein Compiler zur Hand!):
%Vor%Natürlich sollte das umgeschrieben werden können, um jedes idempotente kommutative Monoid zu unterstützen, nicht nur max.