Performanz / Effektivität für folgendes Problem (schwierig hier nen passenden Titel zu finden... =)

Freddy_Kay

Marthog schrieb:

Warum Vererbung und warum die ganzen new Aufrufe?

Und warum verwendest du QList statt der STL?

Vererbung weil strukturell die koordinaten sehr ähnlich sind und sich im Grunde nur in der Anzahl der eigentlichen Koordinateneinträge unterscheiden (3 oder 6, je nachdem welches Referenzsystem) und der transformationsalgorithmen unterscheiden, daher werden gemeinsame Funktionen von der Basisklasse geerbt.

new weil ich im ersten Fall eine riesenmenge an Instanzen hab und der Stack nicht ausreicht (allein an double werten kanns auf einige hundert MB hinauslaufen). Außerdem müssen die Objekte unabhängig vom Block sein in dem sie definiert werden. Aber meine Frage geht ja in genau dieselbe Richtung. Was wäre denn die Alternative?

QList weil ich sowieso Qt verwende und es sich angebten hat. Das ganze darf gerne äquivalent gesehen werden als hätte ich einen STL Container verwendet, das Grundproblem bleibt dasselbe.

Falls du einen Vorschlag hast was eine bessere Vorgehensweise wäre, wäre ich sehr verbunden

otze

std::vector<KoordintenImICRFSystem>

Alles andre ist wahrscheinlich langsam.

in 99,9% aller Fälle in denen listen eingesetzt werden, sind vektoren vorzuziehen. ALleine dass das einfügen in die liste ein zusätzliches new verschlingt...

Shade Of Mine

Freddy_Kay schrieb:

Vererbung weil strukturell die koordinaten sehr ähnlich sind und sich im Grunde nur in der Anzahl der eigentlichen Koordinateneinträge unterscheiden (3 oder 6, je nachdem welches Referenzsystem) und der transformationsalgorithmen unterscheiden, daher werden gemeinsame Funktionen von der Basisklasse geerbt.

Das ist eigentlich eine Argumentation gegen Vererbung.

Freddy_Kay

otze schrieb:

std::vector<KoordintenImICRFSystem>
Alles andre ist wahrscheinlich langsam.

in 99,9% aller Fälle in denen listen eingesetzt werden, sind vektoren vorzuziehen. ALleine dass das einfügen in die liste ein zusätzliches new verschlingt...

Inwiefern wäre das bei Vektoren anders? Ich müsste doch weiterhin unterschiedliche Instanzen anlegen?

Die Liste hab ich gewählt, weil ich keine hintereinanderliegenden Einträge brauche. Mir ist egal dass ich einen Tick länger für den zugriff auf einzelne Elemente brauche, solange das einfügen schnell geht.

Shade Of Mine schrieb:

Freddy_Kay schrieb:

Vererbung weil strukturell die koordinaten sehr ähnlich sind und sich im Grunde nur in der Anzahl der eigentlichen Koordinateneinträge unterscheiden (3 oder 6, je nachdem welches Referenzsystem) und der transformationsalgorithmen unterscheiden, daher werden gemeinsame Funktionen von der Basisklasse geerbt.

Das ist eigentlich eine Argumentation gegen Vererbung.

Da komm ich nicht ganz mit. Wenn ich in verschiedenen Klassen ein und dielbe Funktion nutzen möchte, wäre es nicht sinnvoll sie von einer Basisklasse zu vererben und nur die Besonderheiten (in meinem Fall die Transformationen) in jeder Subklasse neu zu implementieren?
Was wäre die Alternative?

EDIT://

Und eigentlich gehts ja auch nicht um die Vererbung oder list vs. vector sondern darum welche Verwaltungsart ich wählen soll. Also praktisch eine Liste aus Pointern auf Klassen oder eine Klasse mit einer Liste aus std::array. Was hätte welche vorteile? Würde sich ersteres deutlich auf den Speicherverbauch auswirken? Gibt es eine Möglichkeit die logische Trennung in verschiedene Klassen beizubehalten und gleichzeitig eine einfache Implementation zu finden?

otze

fast alle operationen, ausser löschen in der Mitte, sind bei einem vektor schnller. vergiss nieemals, dass du bei einer Liste

1. 16 Byte overhead hast (zu deinen 24 Byte nutzdaten und 8 Byte pointer die auch nur overhead sind))
2. jedes Element ein new braucht(ungefähr 10 fache kosten wie ein Element an einen vektor anzuhängen).
3. die Liste dir den Speicher fragmentiert und einfach alles lahm wird (in der Praxis so faktor 3-10 Unterschid im Vergleich zum iterieren über einen vektor)

Freddy_Kay

otze schrieb:

fast alle operationen, ausser löschen in der Mitte, sind bei einem vektor schnller. vergiss nieemals, dass du bei einer Liste

1. 16 Byte overhead hast (zu deinen 24 Byte nutzdaten und 8 Byte pointer die auch nur overhead sind))
2. jedes Element ein new braucht(ungefähr 10 fache kosten wie ein Element an einen vektor anzuhängen).
3. die Liste dir den Speicher fragmentiert und einfach alles lahm wird (in der Praxis so faktor 3-10 Unterschid im Vergleich zum iterieren über einen vektor)

ich bestehe nicht auf listen, mir ist ziemlich egal welchen container ich nutze. Nur den zweiten Punkt verstehe ich nicht. Ich hab doch in beiden Fällen ein new um mein "koordinatenobjekt" anzulegen oder meinst du was andres?

otze

bei der liste lgt die liste selber(!) noch ein Objkt an. Und das new von deinem Objkt solltest du dir auch sparen.

Freddy_Kay

otze schrieb:

bei der liste lgt die liste selber(!) noch ein Objkt an. Und das new von deinem Objkt solltest du dir auch sparen.

das ist richtig. Allerdings, und korrigier mich falls ich falsch liege, speichert QList falls es einen Pointer übergeben bekommt, direkt den Pointer und nicht einen pointer auf den Pointer. Daher ist der overhead hierfür etwas kleiner, da die zweite liste nicht existiert.

Ich hab ja schon mehrmals gefragt, warum genau ich mir das new für mein Objekt sparen soll. nehmen wir folgendes an:

void irgendeineFunktion(){
//rechnet hübsch mit fancy algorithmen und kriegt ein ergebnis in vektorform. Dieses soll nun in die Liste eingetragen werden

    KoordintenImICRFSystem Ergebnis;

    MeinVEKTORmitDenKoordinaten.push_back(Ergebnis);

}

Wenn ich korrekt verstanden hab was du meinst, dann wird hier ein Objekt Ergebnis auf dem Stack erstellt per value an vektor übergeben, dabei kopiert und eingefügt, und dann sobald die funktion durchlaufen wurde das ursprüngliche objekt wieder gelöscht (wenn bei C++ auch komplexe Objekte per value übergeben werden können, soweit ich weiß ist das ja nicht überall so). Was hab ich da gewonnen?
Und existiert das Objekt im vektor, dann nicht auch auf dem Stack? Wie gesagt hab ich eine ganze menge dieser Vektoren, und stoße mit dem Speicherplatz im stack andie grenzen.

Freddy_Kay schrieb:

Wenn ich korrekt verstanden hab was du meinst, dann wird hier ein Objekt Ergebnis auf dem Stack erstellt per value an vektor übergeben, dabei kopiert und eingefügt, und dann sobald die funktion durchlaufen wurde das ursprüngliche objekt wieder gelöscht (wenn bei C++ auch komplexe Objekte per value übergeben werden können, soweit ich weiß ist das ja nicht überall so). Was hab ich da gewonnen?

Wenn du Designentscheidungen und (premature) Optimierungen auf Vermutungen beruhst, wird das nie was.

Sorry, schnapp dir ein Buch und lerne, wie das in C++ funktioniert oder belass es bei Java.

Freddy_Kay

gehjavaschreiben schrieb:

Freddy_Kay schrieb:

Wenn ich korrekt verstanden hab was du meinst, dann wird hier ein Objekt Ergebnis auf dem Stack erstellt per value an vektor übergeben, dabei kopiert und eingefügt, und dann sobald die funktion durchlaufen wurde das ursprüngliche objekt wieder gelöscht (wenn bei C++ auch komplexe Objekte per value übergeben werden können, soweit ich weiß ist das ja nicht überall so). Was hab ich da gewonnen?

Wenn du Designentscheidungen und (premature) Optimierungen auf Vermutungen beruhst, wird das nie was.

Sorry, schnapp dir ein Buch und lerne, wie das in C++ funktioniert oder belass es bei Java.

sehr hilfreich. vielen dank. statt mir vor die nase zu halten ich sollte ein buch lesen nur weil ich die Vorgehensweise eines STL Containers nicht vollständig gekannt habe, hättest du mir auch die suche ersparen können und mir sagen können wies funktioniert.

im übrigen geht's nicht darum festzulegen ob listen oder Vektoren besser sind sondern ob es besser ist einen Container mit komplexen / eignen Klassen zu verwenden (von mir aus auch ohne new ;-)) oder aber einen Container "nur" mit nem std::array.

dabei geht es nur zum Teil um Optimierung. es geht nur darum festzustellen we´lches davon mehr Overhead produziert. Mir ist das nicht ganz klar, lässt sich von erfahrenen benutzern aber sicherlich abschätzen oder es wird zumindest einer sagen können warum es eben nicht abschätzbar ist.

Im übrigen finde ich das absolut nicht voreilig das in diesem Stadium zu fragen. daran hängt der rest der Implementierung. es ist nicht unbedingt schwer von listen auf vektorn zu schwenken aber es wäre schon ein erheblicher aufwand ob ich meine eigenen Klassen verwende oder aber nur die std::Arrays. das wollte ich vermeiden indem ich von vornherein die wahrscheinlich richtige Entscheidung für für die eine oder die andere schnittstelle treffe.

falls du also eine antwort auf den ersten post von mir kennst, wäre ich sehr verbunden wenn du deine weiheit mit mir teilst

otze

Ein Listenelement sieht so aus:

class Element{
    DeinTyp payload;
    Element* prev;
    Element* next; 
};

Wenn du nun ein Element mit new anlegst und den zeiger anlegst, passiert folgeendes:

1. du legst dein Objekt mit new an
2. du fügst einen Zeiger in die Liste ein
3. die liste legt ein Element mit new an
DeinTyp ist dabei Objekt*
4. Das Element wird in die liste eingefügt.
macht also: 3 pointer (prev,next,payload) und dein element mit 3 doubles.

wenn du jtzt dein element OHNE new anlegst, dann wird das direkt als DeinTyp im element gespeichert -> nur noch ein new.
Nimmst du jtzt einen vektor, wird das element einfach am Ende angefügt -> kein new, ausser dein array ist komplett voll (der fall tritt aber nur selten auf)

und es wird für dich absolut keinen Sinn machen, auf eigene Container umzusteigen, das packst du noch nicht.

hustbaer

@otze
QList ist keine solche Liste.
QList ist ein Vektor aus Zeigern auf die Elemente.
Also eher mit std::deque vergleichbar.

Ich würde bei solchen Berechnungen nicht am Anfang auf Optimierungen setzen. Versuch erst mal das Problem sauber zu lösen und dies vielleicht sogar richtig. Wenn es richtig vorliegt kannst du immer noch optimieren.

Da du aber noch Probleme hast deine Objekte auseinander zu halten solltest du lieber überlegen was in diesem Fall deine Objekte sind und wie diese zur Lösung beitragen können.

Es hilft einfach nichts alles so schnell wie möglich machen zu wollen wenn es noch nicht funktioniert.

Nur wenn etwas funktioniert kann man die Laufzeit messen. Nur wenn mal etwas funktioniert hat kannst du auch die Fehler erkennen die durch die Optimierung auftreten werden.

ScottZhang

Freddy_Kay schrieb:

[...] nur in der Anzahl der eigentlichen Koordinateneinträge unterscheiden (3 oder 6, je nachdem welches Referenzsystem) [...]

Wieso unterscheidet sich deine Anzahl der Freiheitsgrade je nach Koordinatensystem

ichhoffedasistrichtig schrieb:

Ich würde bei solchen Berechnungen nicht am Anfang auf Optimierungen setzen. Versuch erst mal das Problem sauber zu lösen und dies vielleicht sogar richtig. Wenn es richtig vorliegt kannst du immer noch optimieren.

Da du aber noch Probleme hast deine Objekte auseinander zu halten solltest du lieber überlegen was in diesem Fall deine Objekte sind und wie diese zur Lösung beitragen können.

Es hilft einfach nichts alles so schnell wie möglich machen zu wollen wenn es noch nicht funktioniert.

Nur wenn etwas funktioniert kann man die Laufzeit messen. Nur wenn mal etwas funktioniert hat kannst du auch die Fehler erkennen die durch die Optimierung auftreten werden.

das ist nicht der Punkt. Ich halte meine Objekte durchaus auseinander. Ich wusste allerdings nicht dass der normale std::vector seine Elemente automatisch auf dem heap ablegt. Und selbst das ist nichtmal der Punkt.

ich kann mir vorstellen dass es auch ohne Laufzeituntersuchung möglich ist festzustellen obs sinnvoller ist eine Liste aus komplexen Objekten anzulegen oder ein objekt mit einer liste aus std::Arrays. nichts anderes hab ich oben gefragt. selbst wenn man nicht bestimmen kann welchen unterschied dass bei der berechnungszeit macht, so kann doch sicherlich einer abschätzen was mehr speicher schluckt. was oben ja bereits ansatzweise geschehen ist und mir gesagt wurde ich solle den 'einfachen' std::vector nehmen. ich meine es ist jetzt auch für einen nicht Informatiker nicht so ohne weiteres ersichtlich wie ein Compiler bei der Erstellung von Klassen vorgeht. legt er zum Beispiel für jede Instanz speicher für die Funktionen fest? oder gibt es nur einen speicherort für di Funktionen und jede Instanz springt dort nur rein und der einzige Speicherplatz der bei der Instanz selbst vorgesehen ist ist dann der für die sprungadressen? oder gilt das nur für statische Funktionen oder liegt da ein ganz anderes System zu grunde? sowas steht nicht grad im galileo computing. sowas müsste sich durchaus auch ohne leistungsanalyse ergeben können.

im übrigen habe ich bereits eine fertige funktionierende Implementierung. allerdings ziemlich unaufgeräumt undkommentiert und nur runterprogrammiert. was ich grade mache ist das sauber aufzuziehen, da man da nicht mehr durchblickt. dort hab ich auch Vektoren verwendet, allerdings nicht mit präalloziertem speicher, daher ist das Programm auch sehr langsam und hängt 80% der zeit in der speicherallozierung fest. Und wie gesagt ändern sich je nach vorgehen die Schnittstellen und ich müsste dann wieder durch jede Funktion gehen und schauen dass ich die richtigen Objekte übergebe bzw. die Schnittstelle richtig bediene. Den aufwand wollte ich mir wenns ichs denn schon wieder mache nach Möglichkeit sparen.

ScottZhang schrieb:

Freddy_Kay schrieb:

[...] nur in der Anzahl der eigentlichen Koordinateneinträge unterscheiden (3 oder 6, je nachdem welches Referenzsystem) [...]

Wieso unterscheidet sich deine Anzahl der Freiheitsgrade je nach Koordinatensystem

Die Freiheitsgrade sind immer 6. Die Objekte repräsentieren aber keine Freiheitsgrade sondern referenzsysteme. In einigen referenzsystemen ist eine Unterscheidung in Geschwindigkeit und postion mit jeweils 3 Koordinaten nicht möglich oder ergibt keinen sinn, oder lässt sich nicht berechnen (z.B. Position eines Raumflugkörpers in Keplerelementen oder im körperfesten bezugssystem oben wäre das das RSW System und anderes). deswegen können einige Systeme in 2x3 Komponenten zerlegt werden und andere nicht.
es werden allerdings nur die drei translatorischen Freiheitsgrade berechnet. die rotatorischen sind zunächst ausgenommen, da unerheblich. daher auch nur ´die Position und deren Ableitungen. Letztlich ist mit 6 Koordinaten ein zustandsvektor gegeben, während 3 Koordinaten keinen vollständigen zustand beschreiben (wie gesagt ´Rotation ausgenommen).