Unterschied in der Rechenzeit zwischen C++ und Delphi
-
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.
-
@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.
-
@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.
