Ich implementiere eine N-Body-Simulation in Haskell. Ссылка
Im Moment berechnet jedes Teilchen seine Kraft und dann die Beschleunigung gegen jedes andere Teilchen. Mit anderen Worten, O (n²) Berechnungen der Kraft. Ich könnte dies auf O reduzieren (n wähle 2), wenn ich jede Kombination einmal berechnen würde.
%Vor% Aber ich kann nicht herausfinden, wie man diese auf die Teilchen anwendet, ohne den Zustand zu benutzen. Im obigen Beispiel ist ps [Particle] wo
Theoretisch wäre ich in einer Stateful-Sprache einfach in der Lage, die Kombinationen zu durchlaufen, die jeweilige Beschleunigung aus der Kraft von a und b zu berechnen und dann jedes Particle in ps acceleration als I zu aktualisieren Mach das.
Ich habe über etwas wie foldr f ps combs nachgedacht. Der Startakkumulator wäre das aktuelle ps und f wäre eine Funktion, die jedes comb übernimmt und das relevante Particle in ps aktualisiert und diesen Akkumulator zurückgibt. Das scheint wirklich speicherintensiv und ziemlich kompliziert für einen so einfachen Prozess.
Irgendwelche Ideen?
Nimm den Code von Ссылка
%Vor%und modifizieren es so, dass die Beschleunigungen in einer Matrix (gut, Liste von Listen ...) getrennt von der Aktualisierung jedes Partikels ausgearbeitet werden, erhalten wir ...
%Vor% ... so besteht das Problem im Wesentlichen darin, wie die Anzahl der Aufrufe von gravitate verringert werden kann, wenn accsMatrix ausgearbeitet wird, wobei die Tatsache verwendet wird, dass gravitate a b = -1 * gravitate b a .
Wenn wir accsMatrix ausdrucken würden, würde es aussehen wie ...
... so sehen wir accsMatrix !! i !! j == -1 * accsMatrix !! j !! i .
Um die obige Tatsache zu nutzen, brauchen wir Zugriff auf einige Indizes. Zuerst indexieren wir die äußere Liste ...
%Vor%... und ersetze die innere Liste durch ein Listenverständnis ...
%Vor%... einige weitere Indizes per ZIP verfügbar machen ...
%Vor% ... und dann, der Schlüssel, ist make accsMatrix von sich selbst abhängig für die Hälfte der Matrix ...
Wir können es auch ein bisschen teilen, wie unten ...
%Vor% ... oder vermeiden Sie List-Comprehensions mit map
... oder mit der Liste monad ...
%Vor%... obwohl es (für mich) schwieriger ist zu sehen, was in diesen passiert.
Es gibt wahrscheinlich einige schreckliche Leistungsprobleme mit dieser Liste von Listen Ansatz, insbesondere mit !! , und die Tatsache, dass Sie immer noch O (n²) Operationen aufgrund der Durchquerungen laufen, und die Tatsache, dass O (n · (n - 1)) ≡ O (n²) als @leftaroundabout erwähnt, aber jede Iteration sollte gravitate n * (n-1) / 2 mal aufrufen.
Tags und Links haskell physics simulation