Unterschied in der Rechenzeit zwischen C++ und Delphi

st3fan85

Das ist alles auf meinem Mist gewachsen. Meine letzte Programmiererfahrung sind schon ein paar Jahre her. Das einzige was ich gemacht habe ist mal ein Arduino programmiert oder ein paar Daten ausgewertet und da kam es nicht auf Performance an.
Es geht im Grunde um einen Diffusionsprozess auf einer Oberfläche. Für die Oberfläche wird ein 2D-Array verwendet. Jede x,y-Koordinate ist ein Platz für ein Atom. Diese Atome können sich bewegen und wenn sich zwei treffen, bilden sie einen Tropfen. Dementsprechend existieren zwei Vectoren, einer für Atome und einer für Tropfen, die die Position auf der Oberfläche beschreiben. Atome haben nur x,y-Koordinaten und Tropfen zusätzlich Parameter wie die Größe. Bei Tropfenbildung müssen zwei Atome aus dem Vector gefunden und gelöscht werden und ein Tropfen erzeugt. Trifft ein Atom auf einen Tropfen muss ein Atom gelöscht werden und der Tropfen in seiner Größe aktualisiert werden.
Ich versuch den Such- und Löschprozess für die Atome mal grob hier einzugeben.

#include <iostream>
#include <vector>
#include <algorithm>
...
using namespace std;
const int SimSize = 200;                          
int SimField[SimSize][SimSize] = { 0 };  //Oberfläche
int gl_x, gl_y;    //Globale x,y-Koordinaten für die Prädikaten-Funktion

struct monoStr         // Sturktur für Atome/Monomere
{
    int x;
    int y;
};

struct dropStr          //Struktur für Tropfen
{
    int x;
    int y;
    int V;
    double r;
    double RE;
};

vector<monoStr> Monomers;   //Vector für die Atome/Monomere
vector<dropStr> Droplets;    // Vector für die Tropfen

bool find_monomer(const monoStr &monomer)      //Prädikat-Funktion für find_if Anweisung
{
  return monomer.x==gl_x && monomer.y==gl_y;
}

void newMono(int x, int y)   //Funktion für die Erstellung eines neuen Atoms
{
    SimField[x][y]++;
    monoStr nMono = {x, y};
    Monomers.push_back(nMono);
}

void delMonomer(int x, int y)    //Funktion für das Löschen eines Atoms von der Oberfläche
{
    SimField[x][y]--;
    gl_x = x;
    gl_y = y;
    vector<monoStr>::iterator iter = find_if(Monomers.begin(), Monomers.end(), find_monomer);
    Monomers.erase(iter);
}

void Diffusion(int Index, int Richtung)
{
//Hier findes der Bewegungsprozess statt und bei einer Anlagerung an einem Tropfen muss jetzt ein Atom gelöscht werden:
delMonomer(Monomers[index].x, Monomers[index].y)
}

int main()
{
do
{
//Hier wird jetzt ein Prozess ausgewählt und welches Atom davon betroffen ist. 
//Beim Diffusionsprozess wird ein Index ausgewählt und die Richtung in die Das Atom laufen soll.

Diffusion(Index, Richtung);

...
}while(t>= t_stop);
return 0;
}

Ich hoffe, dass man die Struktur des Programms einigermaßen verstehen kann. Zusätzlich zur Diffusion existieren noch mehrere Prozesse, für die es auch separate Funktionen gibt.
Ist es dann sinnvoller die Vectoren immer mit in die Funktionen zu geben?
Oder ist hier der Punkt gekommen an den die Zeiger von C++ ins Spiel kommen und nur die Adressen des Speicherbereicht an die Funktion übergeben werden? Das Zeiger-Konzept ist für mich auch ganz neu.

Schönen Gruß
Stefan

TGGC

Es gibt spezielle Datenstrukturen, die dafür gedacht sind Werte zu finden und zu entfernen und ab bestimmten Datenmengen immer schneller sind als eine "bessere" Programmiersprache. Die Perfomance von dem was du beschreibst ist dann durch die Menge der zu lesenden Daten beschränkt und nicht der Sprache.

Bashar

@st3fan85 sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

vector<monoStr> Monomers;   //Vector für die Atome/Monomere
vector<dropStr> Droplets;    // Vector für die Tropfen

bool find_monomer(const monoStr &monomer)      //Prädikat-Funktion für find_if Anweisung
{
  return monomer.x==gl_x && monomer.y==gl_y;
}

void delMonomer(int x, int y)    //Funktion für das Löschen eines Atoms von der Oberfläche
{
    SimField[x][y]--;
    gl_x = x;
    gl_y = y;
    vector<monoStr>::iterator iter = find_if(Monomers.begin(), Monomers.end(), find_monomer);
    Monomers.erase(iter);
}

Der find_if-Aufruf lässt sich mit Lambdas deutlich verbessern:

auto iter = find_if(Monomers.begin(), Monomers.end(), [x, y](const monoStr& m) { return m.x == x && m.y == y; });

Dann erübrigen sich auch die globalen gl_x und gl_y.

Das Löschen aus einem Vektor ist aber natürlich nicht gerade effizient, weil alle Element nach dem Iterator nach vorne geschoben werden. Ich denke, da verlierst du eher Performance. Wie hast du das denn in Delphi umgesetzt? Das kocht ja auch nur mit Wasser und kann bei einer äquivalenten array-basierten Umsetzung sicher nicht wesentlich schneller sein.

Quiche Lorraine

@Bashar
Auch das find hat eine Komplexität von O(n).

Evtuell sollte man wie TGGC schon andeutete ein std::map ausprobieren.

SeppJ

Wie schon befürchtet:

Konsequent monoStr überall benutzen, wo Koordinatenpaare gefragt sind.
Globale Variablen komplett weg, siehe Bashar
erase-remove idiom benutzen. Das macht das gleiche, was du für deinen Delphi-Code beschreibst, nämlich etwas von hinten an die Löschposition tauschen und dann hinten abschneiden. Das bringt das Löschen (minus das Suchen) von O(N) auf O(1).

Nach 1-3 bist du dann auch garantiert flotter als dein vergleichbarer Delphi Code.

Aber für beide Codes gilt:
4. Was TGGC gesagt hat: Über ganz andere Datenstrukturen nachdenken. Für Simulationen dieser Art gibt es optimierte Arten und Weisen, die Daten zu organisieren, so dass man beispielsweise nicht einen ganzen Vector nach einem bestimmten Element durchsuchen braucht, weil man schon weiß, wo man ungefähr gucken muss. Die passenden Vorgehensweisen hängen natürlich von deinen genauen Anforderungen ab, aber in Büchern über Computersimulationen stehen allerlei gängige Tipps und Tricks, die du mal studieren solltest.

Standardfrage: wurde der Compiler mit eingeschaltetem Optimizer ausgeführt? (Release oder -O3)

Bashar

@Quiche-Lorraine sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

@Bashar
Auch das find hat eine Komplexität von O(n).

Mir gehts hier erstmal darum herauszufinden, wieso das in C++ langsamer als in Delphi ist.

SeppJ

@Quiche-Lorraine sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

Evtuell sollte man wie TGGC schon andeutete ein std::map ausprobieren.

Ich bezweifle dass TGGC das gemeint hat
Er denkt gewiss an Nachbarschaftslisten, zellbasierte Datenstrukturen, und ähnliches.

@SeppJ sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

erase-remove idiom benutzen. Das macht das gleiche, was du für deinen Delphi-Code beschreibst, nämlich etwas von hinten an die Löschposition tauschen und dann hinten abschneiden. Das bringt das Löschen (minus das Suchen) von O(N) auf O(1).

Das stimmt so nicht. std::remove behält die Reihenfolge bei.

Th69

@st3fan85: Und noch ein Tipp; du solltest Str aus dem Namen deiner Strukturen entfernen (bei Strdenkt man eher an einen String).

Und du könntest dir überlegen eine Klasse für deine Daten und Funktionen anzulegen (so wären die globalen Variablen eliminiert).

SeppJ

@manni66 sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

@SeppJ sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

erase-remove idiom benutzen. Das macht das gleiche, was du für deinen Delphi-Code beschreibst, nämlich etwas von hinten an die Löschposition tauschen und dann hinten abschneiden. Das bringt das Löschen (minus das Suchen) von O(N) auf O(1).

Das stimmt so nicht. std::remove behält die Reihenfolge bei.

Argh, stimmt. Bin schon lange nicht mehr auf die Idee gekommen, aus der Mitte von Vectoren zu löschen und verwechsele wie ich es machen würde mit was tatsächlich gemacht wird

hustbaer

Hat jetzt auch nix mit Delphi vs. C++ zu tun, aber das

void delMonomer(int x, int y)    //Funktion für das Löschen eines Atoms von der Oberfläche
{
    SimField[x][y]--;
    gl_x = x;
    gl_y = y;
    vector<monoStr>::iterator iter = find_if(Monomers.begin(), Monomers.end(), find_monomer);
    Monomers.erase(iter);
}

void Diffusion(int Index, int Richtung)
{
//Hier findes der Bewegungsprozess statt und bei einer Anlagerung an einem Tropfen muss jetzt ein Atom gelöscht werden:
delMonomer(Monomers[index].x, Monomers[index].y)
}

ist doch verschenkte Rechenzeit.
Erst holst du in Diffusion über den Index die X und Y Koordinaten des Monomers, rufst dann damit delMonomer auf, dann sucht delMonomer wieder den Index anhand der X und Y Koordinaten und löscht dann den Eintrag. Wäre effizienter gleich den Eintrag über den Index zu löschen:

void delMonomer(vector<monoStr>::iterator iter)
{
    SimField[iter->x][iter->y]--;
    Monomers.erase(iter);
}

void delMonomer(int x, int y)
{
    gl_x = x;
    gl_y = y;
    vector<monoStr>::iterator iter = find_if(Monomers.begin(), Monomers.end(), find_monomer);
    delMonomer(iter);
}

void Diffusion(int Index, int Richtung)
{
    // ...
    delMonomer(Monomers.begin() + Index);
}

hustbaer

@st3fan85 sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:
Wie andere schon erwähnt haben wird wohl das

Zum Löschen haben wir dazu immer das zu löschende Element mit dem letzten Element überschrieben und dann das Array verkürzt. Die Reihenfolge der Elemente spielt dabei keine Rolle.

der Grund für die unterschiedliche Performance gewesen sein.

st3fan85

Hallo,
vielen Dank für die vielen Antworten. Ich muss sie mir erstmal in Ruhe durchlesen und dann meinen Code verändern, oder besser neu schreiben. Eine Frage habe ich schon. Ich habe mehrere Konstanten die in verschiedenen Funktionen verwendet werden. Ist es besser diese in den einzelnen Funktionen neu zu definieren oder kann man eine globale erstellen und diese dann an eine lokale Variable in der Funktion übergeben?

Schöne Grüße
Stefan

SeppJ

Konstanten haben die Eigenschaft, nicht variabel zu sein…

@SeppJ sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

Argh, stimmt. Bin schon lange nicht mehr auf die Idee gekommen, aus der Mitte von Vectoren zu löschen und verwechsele wie ich es machen würde mit was tatsächlich gemacht wird

Was du vorschlägst würde erase + partition tun.

Wenn einem die Reihenfolge egal ist, könnte sortiertes Einfügen/Löschen mit lower_bound + insert/erase die bessere Wahl sein. Ich würde vermuten, dass das O(N) für memmove billiger zu haben ist als das O(n) für eine lineare Suche.

hustbaer

@manni66

Ich würde vermuten, dass das O(N) für memmove billiger zu haben ist als das O(n) für eine lineare Suche.

Und ich würde vermuten dass das so oder so ausgehen kann, je nachdem. Da spielen viele Faktoren mit rein.

Was aber recht effizient sein sollte: Statt Element für Element abzuarbeiten und im Falle des Falles zu löschen, kann man es ala Mark & Sweep machen. Im ersten Durchlauf markiert man bloss die Dinge die gelöscht werden sollen, und im zweiten Durchlauf löscht man dann alles was markiert ist gleichzeitig. Ob das was bringt hängt natürlich davon ab wie viele Einträge man bei einem durchschnittlichen Durchlauf so löscht. Wenn das in der Grössenordnung von 1 ist, wird es nicht viel bringen. Wenn es deutlich > 1 ist, wird es was bringen.

Oder man nutzt aus dass es pro Zelle in dem 2-dimensionalen Feld eh nur einen Eintrag geben kann. Man kann also statt der Anzahl (die wenn ich das richtig verstehe sowieso immer nur 0 oder 1 sein kann) gleich den Index speichern.

Weiters könnte man noch den Unterschied zwischen Monomeren und Tropfen entfernen, und alles als Tropfen modellieren.

TGGC

@SeppJ sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

@Quiche-Lorraine sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

Evtuell sollte man wie TGGC schon andeutete ein std::map ausprobieren.

Ich bezweifle dass TGGC das gemeint hat
Er denkt gewiss an Nachbarschaftslisten, zellbasierte Datenstrukturen, und ähnliches.

Ich möchte auch widersprechen, das ich für performancerelevante Anwendungen std::map empfehle (fiese Unterstellung ). Ich würde erstmal probieren nxn Vektoren zu nutzen, nachdem ich den gesamten Problemraum in nxn AABBs zerteilt hab. Das was SeppJ hier glaube "zellbasierte Datenstrukturen" nennt, weiss jetzt aber nicht ob das ein gutes Gogle Stichwort ist.