Codequalität

[volkard]

Hador_ schrieb:

volkard schrieb:

wohl besser, du implementiertst den copy-ctor normal und dern op= mit copy&swap?

Aber im op= muss doch nicht immer jedes Element neu erzeugt werden, im cp-ctor aber schon. Deshalb wäre eine solche Implementierung doch langsamer.
Gibt es denn sonst noch Vorteile, die für eine Implementierung in deinem Sinne sprechen?

oh, du verwendest ja die alten knoten weiter.
ich nehme meinen vorschlag zurück. aber irgendwie fühle ich mich unwohl dabei. weiß auch nicht, warum.

[Nexus]

Hador_ schrieb:

Wie sollte ich es denn machen?

Zum Beispiel so:

throw invalid_argument("Argument must be greater than zero!");

[Hador_]

So, ich habe nun (fast) alle Anregungen mal umgesetzt. Damit sieht das ganze nun so aus:

#ifndef SPARSEVEKTOR_HPP_INCLUDED
#define SPARSEVEKTOR_HPP_INCLUDED

#include <stdexcept>

// A linked-list node for the sparse vector elements
template <class T> class Node {
	public:
		// Node constructor - simply initializes the data-members.
		Node(int idx, T val, Node *nxt)
		: index(idx), value(val), next(nxt) {}

		Node()
		: index(-1), next(NULL) {}

		inline int getIndex() const {
			return index;
		}

		inline void setIndex(const int idx) {
			index = idx;
		}

		inline Node * getNext() const {
			return next;
		}

		inline void setNext(Node<T> * nextNode) {
			next = nextNode;
		}

		inline T getValue() const {
			return value;
		}

		inline void setValue(const T val) {
			value = val;
		}

		bool operator == (const Node<T> & n) const {
			return (index == n.index) && (value == n.value);
		}

		bool operator != (const Node<T> & n) const {
			return !(*this == n);
		}

	private:
		int index; // Element number, in the range [0, size)
		T value; // The value of this element.
		Node *next; // A pointer to the next node in the linked-list.
};

template <class T> class SparseVector {
	public:
		SparseVector(const int size = 1)
		: size(size), elements(new Node<T>()) {
			if (size <= 0)
				throw std::invalid_argument("Argument must be greater than zero!");
		}

		SparseVector(const SparseVector<T> & spvc)
		: size(spvc.size), elements(new Node<T>()) {
			*this = spvc;
		}

		~SparseVector() {
			Node<T> * aktElem = elements;
			while (aktElem) {
				Node<T> * nextElem = aktElem->getNext();
				delete aktElem;
				aktElem = nextElem;
			}
		}

		void print(std::ostream & out, const std::string seperator) {
			for (int i = 0; i < size; i++) {
				out << getElement(i) << seperator;
			}
		}

		T getElement(const int col) const {
			if ((col < 0) || (col >= size))
				throw std::out_of_range("Not a valid vector element!");
			Node<T> * elem = elements;
			while ((elem) && (elem->getIndex() < col))
				elem = elem->getNext();
			if (elem && (elem->getIndex() == col))
				return elem->getValue();
			return 0;
		}

		void setElement(const int col, const T value) {
			if ((col < 0) || (col >= size))
				throw std::out_of_range("Not a valid vector element!");
			Node<T> * lastElem = elements;
			Node<T> * aktElem = elements->getNext();
			while ((aktElem) && (aktElem->getIndex() < col)) {
				lastElem = aktElem;
				aktElem = aktElem->getNext();
			}
			if (!aktElem || (aktElem->getIndex() != col)) {
				if (value != 0)
					lastElem->setNext(new Node<T>(col, value, aktElem));
			} else if (value == 0) {
				lastElem->setNext(aktElem->getNext());
				delete aktElem;
			} else {
				aktElem->setValue(value);
			}
		}

		inline int getSize() {
			return size;
		}

		SparseVector & operator = (const SparseVector & spvc) {
			if (this == &spvc)
				return *this;
			size = spvc.size;

			Node<T> * aktElem = elements;
			Node<T> * newElem = spvc.elements->getNext();

			// overwrite existing nodes
			while (aktElem->getNext() && newElem) {
				aktElem = aktElem->getNext();
				aktElem->setIndex(newElem->getIndex());
				aktElem->setValue(newElem->getValue());
				newElem = newElem->getNext();
			}
			if (newElem) { // add new nodes
				while (newElem) {
					aktElem->setNext(new Node<T>(*newElem));
					newElem = newElem->getNext();
					aktElem = aktElem->getNext();
				}
			} else { // delete existing nodes
				aktElem = aktElem->getNext();
				while (aktElem) {
					Node<T> * nextElem = aktElem->getNext();
					delete aktElem;
					aktElem = nextElem;
				}
			}
			return *this;
		}

		bool operator == (const SparseVector & spvc) const {
			if (spvc.size != size)
				return false;
			Node<T> * aElem = elements->getNext();
			Node<T> * bElem = spvc.elements->getNext();
			while (aElem && bElem && (*aElem == *bElem)) {
				aElem = aElem->getNext();
				bElem = bElem->getNext();
			}
			return !aElem && !bElem;
		}

		bool operator != (const SparseVector & spvc) const {
			return !(*this == spvc);
		}

		SparseVector operator + (const SparseVector & spvc) const {
			checkDimensionError(spvc);
			SparseVector result(*this);
			return result += spvc;
		}

		SparseVector operator - (const SparseVector & spvc) const {
			checkDimensionError(spvc);
			SparseVector result(*this);
			return result -= spvc;
		}

		SparseVector & operator += (const SparseVector & spvc) {
			checkDimensionError(spvc);
			for (int i = 0; i < size; i++) {
				setElement(i, getElement(i) + spvc.getElement(i));
			}
			return *this;
		}

		SparseVector & operator -= (const SparseVector & spvc) {
			checkDimensionError(spvc);
			for (int i = 0; i < size; i++) {
				setElement(i, getElement(i) - spvc.getElement(i));
			}
			return *this;
		}
	private:
		int size;
		Node<T> * elements;

		inline void checkDimensionError(const SparseVector & spvc) const {
			if (size != spvc.size)
				throw std::invalid_argument("Dimension must be the same!");
		}
};

#endif // SPARSEVEKTOR_HPP_INCLUDED

Danke auf jeden Fall schonmal für die vielen Kommentare - wer weitere hat: immer her damit ^^

Gruß Lars

[volkard]

#ifndef SPARSEVEKTOR_HPP_INCLUDED
#define SPARSEVEKTOR_HPP_INCLUDED

#include <stdexcept>

// A linked-list node for the sparse vector elements
template <class T> class Node {
	public:
		// Node constructor - simply initializes the data-members.
		Node(int idx, T val, Node *nxt)
		: index(idx), value(val), next(nxt) {}
//T const& val, damits schneller geht bei z.B. sttrings
//size_t idx, oder? sind negative indizes möglich?

		Node()
		: index(-1), next(NULL) {}
//wozu? ist zeitverschwendung und bringt nichmal sicherheit. 

		inline int getIndex() const {
			return index;
		}
//die zugriffsfunktionen alle weg, dafür die attribute public machen. 
//die main() kommt eh NIE ein Node-Objet in die hand. was soll passieren?

		inline void setIndex(const int idx) {
			index = idx;
		}

		inline Node * getNext() const {
			return next;
		}

		inline void setNext(Node<T> * nextNode) {
			next = nextNode;
		}

		inline T getValue() const {
			return value;
		}
//T const&, aber egal, fliegt ja weg

		inline void setValue(const T val) {
			value = val;
		}

		bool operator == (const Node<T> & n) const {
			return (index == n.index) && (value == n.value);
		}
//wozu?

		bool operator != (const Node<T> & n) const {
			return !(*this == n);
		}

	private:
		int index; // Element number, in the range [0, size)
		T value; // The value of this element.
		Node *next; // A pointer to the next node in the linked-list.
//umsortieren zu index,next,value oder next,index,value. je nachdem, was 
//schneller sein soll, index oder next. value ans ende, weil größe unbekannt, 
//um kein überraschendes padding hervorzuholen
};

template <class T> class SparseVector {
	public:
		SparseVector(const int size = 1)
		: size(size), elements(new Node<T>()) {
			if (size <= 0)
				throw std::invalid_argument("Argument must be greater than zero!");
		}
//warum nicht size=0?

		SparseVector(const SparseVector<T> & spvc)
		: size(spvc.size), elements(new Node<T>()) {
			*this = spvc;
		}
//warum zuerst size und elements setzen und dann doch op= aufrufen?

		~SparseVector() {
			Node<T> * aktElem = elements;
			while (aktElem) {
				Node<T> * nextElem = aktElem->getNext();
				delete aktElem;
				aktElem = nextElem;
			}
		}

		void print(std::ostream & out, const std::string seperator) {
			for (int i = 0; i < size; i++) {
				out << getElement(i) << seperator;
			}
		}

		T getElement(const int col) const {
//T const& getEle...
			if ((col < 0) || (col >= size))
				throw std::out_of_range("Not a valid vector element!");
//<0 fällt weg wegen size_t
			Node<T> * elem = elements;
			while ((elem) && (elem->getIndex() < col))
				elem = elem->getNext();
			if (elem && (elem->getIndex() == col))
				return elem->getValue();
			return 0;
		}
//gefällt mir gar nicht. wenn du 0 geben willst bei nichtfund, dann nimme nen 
//zeiger als rückgabe. 
//war nicht eher (suchschleifenidiom: gehe über alle elemente - if hatwas - return -  sag hatnix)
for(Node<T> * elem = elements;elem!=0;elem=elem->next)
   if(elem->index==col)
      return &elem->value;
return 0;
//gemeint?
//andererseite, wer bei indexgrenzenfehlern ne exceptions wirft, darf hier auch 
//eine werfen. ich würde bei beiden arten von fehler keine werfen. 
		void setElement(const int col, const T value) {
//const T& value
			if ((col < 0) || (col >= size))
				throw std::out_of_range("Not a valid vector element!");
			Node<T> * lastElem = elements;
			Node<T> * aktElem = elements->getNext();
			while ((aktElem) && (aktElem->getIndex() < col)) {
				lastElem = aktElem;
				aktElem = aktElem->getNext();
			}
			if (!aktElem || (aktElem->getIndex() != col)) {
				if (value != 0)
					lastElem->setNext(new Node<T>(col, value, aktElem));
			} else if (value == 0) {
//bedenklich. oder willste nen zeiger als value nehmen? wäre auch nicht hübsch. 
//oder ist die klasse in wirklichkeit ein SparseNumericVector, der nur 
//zahlentypen tragen soll?
				lastElem->setNext(aktElem->getNext());
				delete aktElem;
			} else {
				aktElem->setValue(value);
			}
		}
//scheint gut

		inline int getSize() {
//size_t getSize() const
//man schreibt inline nicht mehr
			return size;
//wurde size überhaupt beim insert upgedated? nee, gell?
//und warum nicht? weil size eh nix bringt, füchte ich. 
		}

		SparseVector & operator = (const SparseVector & spvc) {
			if (this == &spvc)
				return *this;
			size = spvc.size;

			Node<T> * aktElem = elements;
			Node<T> * newElem = spvc.elements->getNext();

			// overwrite existing nodes
			while (aktElem->getNext() && newElem) {
				aktElem = aktElem->getNext();
				aktElem->setIndex(newElem->getIndex());
				aktElem->setValue(newElem->getValue());
				newElem = newElem->getNext();
			}
			if (newElem) { // add new nodes
				while (newElem) {
					aktElem->setNext(new Node<T>(*newElem));
					newElem = newElem->getNext();
					aktElem = aktElem->getNext();
				}
			} else { // delete existing nodes
				aktElem = aktElem->getNext();
				while (aktElem) {
					Node<T> * nextElem = aktElem->getNext();
					delete aktElem;
					aktElem = nextElem;
				}
			}
			return *this;
		}

		bool operator == (const SparseVector & spvc) const {
//global machen, oder?
			if (spvc.size != size)
				return false;
			Node<T> * aElem = elements->getNext();
			Node<T> * bElem = spvc.elements->getNext();
			while (aElem && bElem && (*aElem == *bElem)) {
				aElem = aElem->getNext();
				bElem = bElem->getNext();
			}
			return !aElem && !bElem;
//also return aElem || bElem//ka, was hübscher ist
//ich hätte vermutlich eher geschrieben
//for(;aElem!=0 or bElem!=0;aElem=aElem->next,bElem=bElem->next)
//   if(aElem->index!=bElem->index)
//     if(!(aElem->value==bElem->value))//bzw != bei SparseNumericVector
//        return false
//return true;
		}

		bool operator != (const SparseVector & spvc) const {
//auch global?
			return !(*this == spvc);
		}

		SparseVector operator + (const SparseVector & spvc) const {
//auch global. 
			checkDimensionError(spvc);
			SparseVector result(*this);
//nachlesen, ob du hier die RVO kaputtmachst. evtl die beiden zeilen 
//vertauschen. war da nicht sowas?
			return result += spvc;
		}

		SparseVector operator - (const SparseVector & spvc) const {
			checkDimensionError(spvc);
			SparseVector result(*this);
			return result -= spvc;
		}

		SparseVector & operator += (const SparseVector & spvc) {
			checkDimensionError(spvc);
			for (int i = 0; i < size; i++) {
//nee, ganz gewiss ne schleife über die Nodes, nicht über die 
//sparsen indizes. 
//und hier liegt der hund begraben!!!
//deswegen also die nutzlose size. aha!
//ja, das mach mal runter von O(anzahlKnoten*maxIndex) zu O(anzahlKnoten)
				setElement(i, getElement(i) + spvc.getElement(i));
			}
			return *this;
		}

		SparseVector & operator -= (const SparseVector & spvc) {
			checkDimensionError(spvc);
			for (int i = 0; i < size; i++) {
//auch hund
				setElement(i, getElement(i) - spvc.getElement(i));
			}
			return *this;
		}
	private:
		int size;
		Node<T> * elements;

		inline void checkDimensionError(const SparseVector & spvc) const {
			if (size != spvc.size)
				throw std::invalid_argument("Dimension must be the same!");
		}
};

#endif // SPARSEVEKTOR_HPP_INCLUDED

[dooooomi]

volkard schrieb:

//umsortieren zu index,next,value oder next,index,value. je nachdem, was 
//schneller sein soll, index oder next. value ans ende, weil größe unbekannt, 
//um kein überraschendes padding hervorzuholen

Kannst du das ein bißchen näher erläutern? Warum sollte das Padding (mit Standard-Compiler-Optionen) zum Problem werden? Und vor allem, welchen Unterschied macht die Reihenfolge von index und next?

[volkard]

//nur mal in notepad hingehudelt:
//annahme: die nodes liegen nach index sortiert im vector vor

elem* appendOne(elem* dst,size_t index,T const& value)
{
   dst->next=new Node(0,index,value);
   return dst->next;
}

elem* appendCopy(elem* dst,elem* src)
{
   while(src!=0)
      dst=appendOne(dst,src->index,src->value);
}

elem* add(elem* pa,elem* pb)
{
   while(pa!=0 and pb!=0)
   {
      if(pa->index==pb->index)
      {
         pc=appendOne(pc,pa->value+pb->value);
         pa=pa->next;
         pb=pb->next;
      }
      else if(pa->index<pb->index)
      {
         pc=appendOne(pc,pa->value);
         pa=pa->next;
      }
      else
      {
         pc=appendOne(pc,pb->value);
         pb=pb->next;
      }
   }
   if(pa!=0)
      pc=appendCopy(pc,pa)
   if(pb!=0)
      pc=appendCopy(pc,pb)

}

vector operator+(vector a,vector b)
{
   return vector(add(a->start,b->start));
}

[volkard]

dooooomi schrieb:

volkard schrieb:

//umsortieren zu index,next,value oder next,index,value. je nachdem, was 
//schneller sein soll, index oder next. value ans ende, weil größe unbekannt, 
//um kein überraschendes padding hervorzuholen

Kannst du das ein bißchen näher erläutern? Warum sollte das Padding (mit Standard-Compiler-Optionen) zum Problem werden? Und vor allem, welchen Unterschied macht die Reihenfolge von index und next?

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

[dooooomi]

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?

[volkard]

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.

[Hador_]

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?

[volkard]

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.

[volkard]

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.

[Hador_]

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.

[volkard]

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.