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

[Freddy_Kay]

Hallo Leute!

Ich stehe konkret vor folgendem Problem und kann mich irgendwie nicht entscheiden wie ich weiter vorgehen soll.
Ich schreibe ein Programm, das die Bewegungen eines Objekten im Raum berechnet. Die Position und die Bewegung des Objektes wird in Koordinaten in verschiedenen Referenzsystemen angegeben (kartesisch mit unterschiedlichen Festlegungen des Ursprungs oder der rotation, sphärische usw.). Zwischen diesen Referenzsystemen bestehen bestimmte Bedingungen wodurch man in der Lage ist die Koordinaten in andere Systeme zu transformieren, im Grunde also ganz normale Mechanik.

Soviel zum Problem, nun die Umsetzung: Ich habe versucht die logische Trennung auch Programmtechnisch umzussetzen, sprich: jede "Koordinatenart" ist in einer Klasse repräsentiert. Jede dieser Klassen hat Funktionen zur Transformation in andere Klassen und einige gemeinsame Funktionen die das rausgeben der Daten etc. regeln. Nun gibt es eine ganze Menge von Koordinatensets pro Berechnung, z.B. wird die Bewegung über eine zeit von 10 Tagen berechnet und dabei pro Sekunde ein Sample gemacht. Jedes dieser Sample besteht dabei aus 6 Koordinaten (3 für die Position und 3 für die Geschwindigkeit). Die Beschleunigung wird aus den Randbedingungen berechnet und ist nicht Teil eines Sets (ist aber auch egal, nur der Vollständigkeit halber erwähnt).

Die eigentliche Frage ist nun welche Verwaltungsart für diese Koordinatensets sinnvoll wäre.

Bisher hab ich mir das so gedacht:

class BaseKoordinaten {
    public:
        void setCoords(std::array<double, 3> &coords){
            Coordinates = coords;
        };
        std::array<double, 3> get_Coords(){
            return Coordinates;
        };

    private:
        std::array<double, 3> Coordinates;
};

class KoordintenImICRFSystem : BaseKoordinaten {
    public:
        KoordinatenImGEOSystem* cast2GEOSystem(){
            KoordinatenImGEOSystem *result = new KoordinatenImGEOSystem();
            //Transformationsalgorithmus
            return result;
        };

//Ein paar sinnvolle Funktionen und blabla

};

class KoordinateImGEOSystem : BaseKoordinaten {
//Im Prinzip dasselbe wie oben nur halt für andere Referenzsysteme

};

Als ich mir das ausgedacht hab, hab ich den Vorteil gesehen, dass die logische Trennung der Koordinaten vom Compiler überwacht werden kann. Wenn also irgendeine Berechnung im Programm eine bestimmte Koordinatenart erfordert muss ich oder irgendein anderer der daran arbeitet ganz bewusst die richtigen Koordinaten auswählen, was weniger Raum für Fehler lässt. Allerdings würde das bei der Berechnung erfordern, dass für jede Koordinate eine eigene Instanz angelegt werden muss (inkl. der Funktionen usw.), also sowas in der Art (ich nutze übrigens Qt für die GUIs):

void main{
    QList<KoordintenImICRFSystem*> KoordinatenListePosition;
    QList<KoordintenImICRFSystem*> KoordinatenListeGeschwindigkeit;
    for (int i = 0; i < 100000; i++){
        //Koordinaten werden berechnet
        KoordintenImICRFSystem * coordsPos = new KoordintenImICRFSystem();
        KoordintenImICRFSystem * coordsVel = new KoordintenImICRFSystem();
        KoordinatenListePosition.append(coordsPos);
        KoordinatenListeGeschwindigkeit.append(coordsVel);
    }
}

Es sieht für mich als Laien sehr aufwändig und das sieht so aus als würde das ganze eine Menge Overhead produzieren. Glaubt ihr es ist sinnvoller statt eine Liste der Koordinatenobjekte anzulegen sowas zu machen:

class BaseKoordinaten {
    public:
        void addCoords(std::array<double, 3> &coords){
            Coordinates.append(coords);
        };
        QList<std::array<double, 3>>* get_Coords(){
            return &Coordinates;
        };

    private:
        QList<std::array<double, 3>> Coordinates;
};

Ich verliere hierbei den Vorteil, dass wenn ich bestimmte Koordinaten an eine Funktion übergebe vom Compiler überprüft werden kann ob das die richtigen Koordinaten für die Funktion sind, da ja nur ein std::array übergeben wird. Im Grunde könnte man sich die ganzen Subklassen sparen und nur die BaseKoordinaten implementieren und dann dort auch die ganzen Transformationen, die dann auch nur ein std::array zurückgeben.

Wäre das performance und Speicher technisch deutlich besser / einfacher? Wäre das problem mit dem Overhead gar nicht so groß wie ich das grad denke. Hab ich mich hier in was verrannt?
Der Grund warum ich das so ausführlich gepostet habe, ist einfach dass ich hier voll aufm Schlauch stehe... es gibt sicher eine ganz simple Möglichkeit den Vorteil den ich in der ersten Möglichkeit habe auch zu behalten ohne einen Riesenhaufen von Instanzen anzulegen.

[Marthog]

Warum Vererbung und warum die ganzen new Aufrufe?

Und warum verwendest du QList statt der STL?

[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.

[gehjavaschreiben]

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.

[ichhoffedasistrichtig]

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

[Freddy_PW_verlegt_Kay]

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).