Unterschied in der Rechenzeit zwischen C++ und Delphi

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.