Codequalität
-
volkard schrieb:
das erste member hat potentiell den schnellsten zugriff, denn da muß keine arithmetik mehr geschehen zwischen dem objektzeiger und dem zeiger aufs member.
also sucht man sich aus, ob index oder next den ehrenplatz bekommen soll. falls man jetzt schon abschätzen kann, welches attribut deutlich häufiger verwendet wird. kann man's nicht, isses vermutlich auch nicht deutlich messbar. dann läßt man es oder verschiebt die reihenfolgenfestlegung bis man einen praxisnahen datensatz hat und mißt kurz.Macht das wirklich einen Geschwindigkeits-Unterschied, der in der Praxis relevant ist? Ich bezweifle nicht, daß der Zugriff auf das erste Member schneller sein kann, aber trotzdem wäre das so ziemlich das letzte, worüber ich mir beim Schreiben des Codes Gedanken machen würde (das böse P-Wort spare ich mir jetzt mal ;)).
volkard schrieb:
padding wird überraschend bei int(32)index, double(64)daten, T*(32)next, wenn der compiler die daten 64-aligned halten will, dann steht da int(32)index, dummy(32), double(64)daten, T*(32)next, dummy(32). und weil vermutlich sizeof(T*)==sizeof(size_t) ist man's vermutlich immer los, wenn die daten am ende stehen.
Nur daß ich das richtig verstehe: es geht dir um den Speicherbedarf des Objekts, nicht um die Geschwindigkeit der Zugriffe?
-
dooooomi schrieb:
Macht das wirklich einen Geschwindigkeits-Unterschied, der in der Praxis relevant ist?
nicht relevant, unter besten umständen vielleicht ein prozent. aber hier kostenlos und unbedenklich. später denke ich nicht mehr dran, da mach ichs gleich.
dooooomi schrieb:
volkard schrieb:
padding wird überraschend bei int(32)index, double(64)daten, T*(32)next, wenn der compiler die daten 64-aligned halten will, dann steht da int(32)index, dummy(32), double(64)daten, T*(32)next, dummy(32). und weil vermutlich sizeof(T*)==sizeof(size_t) ist man's vermutlich immer los, wenn die daten am ende stehen.
Nur daß ich das richtig verstehe: es geht dir um den Speicherbedarf des Objekts, nicht um die Geschwindigkeit der Zugriffe?
ja.
-
Hallo volkard,
... das ist mal ausführlich ^^Zunächst muss ich allerdings mal ein Missverständnis korregieren: Das ganze soll einen Vektor im mathematischen sinne darstellen. Size ist somit die Dimension des Vektors. Das ganze sollte so umgesezt werden, dass Elemente, die 0 sind nicht gespeichert werden (aber es gibt eben dennoch alle Elemente im Bereich 0 <= x < size). Dementsprechend macht meine Implementierund dann hoffentlich auch wieder an vielen Stellen Sinn.
Von deinen Tips habe ich noch einige umgesetzt:
- Node habe ich nun als Memberklasse von SparseVector implementier (da muss ja eh kein anderer dran) und die ganzen Getter/Setter entfernt (Klasse private aber alle Attribute public)
- copy-ctor: Anfangsinitialisierung von size entfernt.
- getSize konstant deklariert
Weiter schreibst du aber noch, dass du die ganzen Operatoren global deklarieren würdest. Warum?
-
Hador_ schrieb:
Weiter schreibst du aber noch, dass du die ganzen Operatoren global deklarieren würdest. Warum?
wenn du mal nen ctor baust, der zum beispiel einen vector<int> nimmt.
dann kannste ja machen
vector<int> a=holeVectorVonFremdanbieter();
SparseVector<int> b;
//...b initialisieren
SparseVector<int> c=b+a;
aber nicht
SparseVector<int> c=a+b;
das verwirrt.
also globaler op+ sind linker und rechter operand gleicher.
-
Hador_ schrieb:
Size ist somit die Dimension des Vektors.
ok.
Das ganze sollte so umgesezt werden, dass Elemente, die 0 sind nicht gespeichert werden (aber es gibt eben dennoch alle Elemente im Bereich 0 <= x < size). Dementsprechend macht meine Implementierund dann hoffentlich auch wieder an vielen Stellen Sinn.
ja, aber meinen vorschlag beim operator+ mag ich nochmal darlegen.
erstmal vorweg: wenn der vector immer sortiert vorliegen würde, wären die suchläufe im durchschnitt nur halb so lang bei treffern und genausolang bei nichttreffern. es kostet also wohl nix dazu, die liste als sortierte liste zu machen. und es ist auch ohne großen aufwand machbar.
nun nehme ich mal an, ich hab zwei dünn besetzte vektoren jeweils mit dimension 1000 und jeweils nur 50 komponeneten, die ungleich 0 sind.
das sollte doch dein hauptanwendungsgebiet sein, hoffe ich.
dein operator+ läuft in der äüßeren schleife von 0 bis 999 und sucht für beide vektoren von anfang bis ende, was zusammen 100 angeschaute elemente ergibt. also 1000-mal müssen alle elemente angeschaut werden.
mein gegenvorschlag braucht nur einmal alle elemente anzuschauen. der geht ungefähr wie der merge-schritt im merge-sort.
-
volkard schrieb:
erstmal vorweg: wenn der vector immer sortiert vorliegen würde, wären die suchläufe im durchschnitt nur halb so lang bei treffern und genausolang bei nichttreffern. es kostet also wohl nix dazu, die liste als sortierte liste zu machen. und es ist auch ohne großen aufwand machbar.
Die Liste ist doch sortiert
volkard schrieb:
dein operator+ läuft in der äüßeren schleife von 0 bis 999 und sucht für beide vektoren von anfang bis ende, was zusammen 100 angeschaute elemente ergibt. also 1000-mal müssen alle elemente angeschaut werden.
mein gegenvorschlag braucht nur einmal alle elemente anzuschauen.Da hast du recht. das könnte man noch beschleunigen, indem man die Listen beider Vektoren durchgeht, bei gleichem Index addiert und ansonsten das jeweilige Element direkt einfügt.
-
Hador_ schrieb:
Die Liste ist doch sortiert
das war mir völlig klar, als ich deinen code gelesen hab. aber vor lauter spannender prroblemchen bei mir hab ich's glatt wieder verdrängt.
