Optimierung Ansammlung von Vektoren für die Monte-Carlo-Simulation

Question

ich den folgenden Code optimieren wollen:

Während einer Monte-Carlo-Simulation akkumulieren ich einige Mengen f(x) (f(x) teuer zu berechnen ist) und sie im Array speichern bins nach jeder Probenahme Schritt.

EDIT: f (x) ist nicht eine deterministische Funktion von x (damit meine ich es Pseudozufallszahlen erzeugt und verwendet sie, um das Ergebnis zu ändern), und hängt auch von previoulsy berechneten Werte f (y)

for(int n=0;n<N;n++) 
{ 
    // compute some values f(x) at points "p" 
    for(auto k: p) bins[k] += f(k); 
} 

p.size() ist viel kleiner als die Größe bins, aber schließlich werden die meisten Elemente eingestellt werden.

Nach der Simulation ich meine Endwerte akkumulieren durch eine gewichtete Summe über bins tun (g ein Lookup in einem anderen Array):

for(int l=0;l<M;l++) 
    for(int k=0;k<bins.size();k++) 
     finalResult[l] += g(k,l)*bins[k]; 

ich natürlich meine aktualisiert finalResult nach jedem Abtastschritt berechnen könnte, diese verlangsamt jedoch das Programm sehr, aufgrund der Schleife über M.

Ich habe schon ein sehr einfaches boost::accumulate versucht, aber das hat die Leistung nicht verbessert (wenn ich bei diesem Design bleibe, werde ich es irgendwann wegen der Stabilität verwenden müssen, obwohl).

Alle Arrays sind vom Typ Eigen::MatrixXd, da ich sie für BLAS-Operationen brauche.

p.size() < 10^2 
N ~ 10^7 
M ~ 10^4 
bins.size() ~ 10^5 

Haben Sie Vorschläge haben, auf die Techniken zur Optimierung hier nützlich sein könnten?

Answer 1

Versuchen Sie, f(x) nur einmal für jeden der N Werte (d. H. Memoisierung) zu berechnen. So zum Beispiel, wenn N groß ist (wie es in dieser Situation ist), versuchen Sie Schleife in etwa wie folgt zu ändern: Alternativ

static std::unordered_map<unsigned int, double> memoizedFunction; 
for(int n=0;n<N;n++) 
{ 
    // compute some values f(x) at points "p" 
    for(auto k: p) 
    { 
     auto it = memoizedFunction.find(k); 
     if (it == memoizedFunction.end()) 
     { 
      it = memoizedFunction.emplace(f(k)).first; 
     } 

     bins[k] += *it; 
    } 
} 

, könnten Sie speichern nur die Anzahl, wie oft die k ten ist gewesen hit in bins[k] und dann am Ende durchlaufen und berechnen bins[k] * f(k) für jeden k.

Answer 2

Nur ein Gedanke hier aber Sie, wenn Sie, dass f überprüfen können (x) eine lineare Transformation dann könnte man die Matrix erstellen A so dass

[f(x)] = A[x] where [x] is the coordinates of x with respect to some basis B. 

Die f machen könnte (x) einfacher und schneller zu berechnen, besonders wenn x in einem Vektorraum mit einer kleinen Basis existiert.

Allerdings, wenn die Konvertierung zwischen Koordinaten und die Antwort ist teuer , die alle Vorteile töten könnte (nur daran denken).

Hier sind einige Links, die helfen könnten, die Matrixdarstellung von linearen Transformationen zu erklären.

https://math.colorado.edu/~nita/MatrixRepresentations.pdf https://math.dartmouth.edu/archive/m24w07/public_html/Lecture12.pdf https://en.wikipedia.org/wiki/Transformation_matrix