Nochmals Datenstrukturen

[Ishildur]

@Volkard
Guten Abend und herzlich willkommen in meiner Fragestunde :p

Ich dachte, ein RedBlackTree sei ein BinaryTree.

Ja genau das ist er, ein RedBlackTree ist ein Balanced BinaryTree. Eigentlich sogar ein logischer 2-4 Tree, aber physikalisch ein Balanced BinaryTree.
Nun ich versuche die Frage anderst zu stellen. Was ist der Vorteil eines Unbalanced BinaryTrees gegenüber eines Balanced Trees => wieso sollte man überhaupt unbalanced BinaryTrees verwenden? Gibt es hierfür eine sinnvolle Anwendung? Beispiel:
for(uint32 i=0;i<1024;++i) MyUnbalancedBinaryTree->Insert(i);
for(uint32 i=0;i<1024;++i) MybalancedBinaryTree->Insert(i);

Beim Unbalanced, also herkömmlichen BinaryTree habe ich nun O(n) Zugriffszeit, weil der Baum zu einer LinkedList (ausser dass er 3mal soviel Speicher frisst) degeneriert ist, jeder Node hat nämlich immer nur ein weiterer Node auf der Rechten Seite.
Bei BalancedTree (AVL oder RedBlackTree) habe ich O(log(n)) Zugriffszeit, weil der Baum balanciert und somit eine Tiefe von ca. log(n) anstatt n hat.

Wenn die Zahlen wirklich schön zufällig hineingeschrieben werden, dann sind die Zugriffszeiten bei beiden identisch. Das Insert und Remove allerdigns auch, weil ja in diesem Fall nichts ausbalanciert werden muss.

Wieso also eine BinaryTree (unbalanced) verwenden?

Das wegen der Hashtable habe ich immer noch nicht ganz verstanden. Nehmen wir einmal an, ich hätte ein Dictionary mit 1024 Commands für einen Parser. Ist da einmal hashen:

uint32 hashCode(const char *p,uint32 len){
 uint32 h = 0;

 for(uint i=0;i<len;++i){
  h = (h << 5) | (h >> 27);
  h += p[i];
 }

nicht deutlich schneller als in Worstcase 1024 String vergleiche?

[volkard]

Ishildur schrieb:

Beispiel:
for(uint32 i=0;i<1024;++i) MyUnbalancedBinaryTree->Insert(i);
for(uint32 i=0;i<1024;++i) MybalancedBinaryTree->Insert(i);

Beim Unbalanced, also herkömmlichen BinaryTree habe ich nun O(n) Zugriffszeit, weil der Baum zu einer LinkedList (ausser dass er 3mal soviel Speicher frisst) degeneriert ist, jeder Node hat nämlich immer nur ein weiterer Node auf der Rechten Seite.
Bei BalancedTree (AVL oder RedBlackTree) habe ich O(log(n)) Zugriffszeit, weil der Baum balanciert und somit eine Tiefe von ca. log(n) anstatt n hat.

Ja.
Beispiel:
for(uint32 i=0;i<1024;++i) MyUnbalancedBinaryTree->Insert(i161%1000);
for(uint32 i=0;i<1024;++i) MybalancedBinaryTree->Insert(i161%1000);
Nu ist der BalancedTree vielleicht halb so schnell wie der rohe Binärbaum.
(sauschnellen operator new vorausgesetzt)
Weil er eben nicht buchhaten muß.

Ishildur schrieb:

Wenn die Zahlen wirklich schön zufällig hineingeschrieben werden, dann sind die Zugriffszeiten bei beiden identisch. Das Insert und Remove allerdigns auch, weil ja in diesem Fall nichts ausbalanciert werden muss.

O()-mäßig sind sie gleich. Gemessen können inserts um ein if schneller sein und Suchen werden um ein if lahmer sein.

Ishildur schrieb:

Wieso also eine BinaryTree (unbalanced) verwenden?

Würde ich nich tun. Kann mir nichts in der Praxis vorstellen.

[volkard]

Ishildur schrieb:

Nehmen wir einmal an, ich hätte ein Dictionary mit 1024 Commands für einen Parser. Ist da einmal hashen:

uint32 hashCode(const char *p,uint32 len){
 uint32 h = 0;

 for(uint i=0;i<len;++i){
  h = (h << 5) | (h >> 27);
  h += p[i];
 }

nicht deutlich schneller als in Worstcase 1024 String vergleiche?

Nicht im Durchschnitt wenn die Daten len=65536 und die String-Daten zufällig sind. Ganz erst recht nicht, wenn der Baum ballanciert ist und man nur 10 Stringverhleiche braucht, die im Normalfall beim ersten Byte schon erkennen, on > oder < oder ==.
Die Hashtable müßte bei

for(;;)
{
   URL=readURL();
   sendData(hashtable[URL]);
}

immer die gesamte URL hashen, was normalerweise supi ist. Hätte man eine andere Datenlage, wo die Anfragen nicht 20 oder 30 Bytes groß sind, sondern tausende von Bytes groß, wäre man angeschmiert, weil bei jeder ANfrage die Schleife

uint32 hashCode(const char *p,uint32 len){
 uint32 h = 0;

 for(uint i=0;i<len;++i){
  h = (h << 5) | (h >> 27);
  h += p[i];
 }

bin hinten laugen müßte.

[Ishildur]

Hehe, du bis echt überzeugend Ich spiele gerade mit dem Gedanken, für meine Bachelorarbeit die Datenstrukturen Hashmap und BinaryTree einfach zu streichen und stattdessen einen RedBlackTree zu implmentieren und mal pauschal überall zu verwenden, wo ein Dictionary erforderlich ist. Natürlich werde ich nur gegen das Dictionary Interface programmieren, dann könnte ich im schlimmsten Fall später doch noch eine Hashtable dahinterstellen, sollte der RedBlackTree aus irgendeinem Grund nicht so richtig wollen

Könntest du mir vielleicht noch einen Typ geben, ob man eine Queue besser mit einer LinkedList oder einem DynamicArray implementiert? Ich hatte mich gestern mal an die Implementation mit einem zirkulären DynamicArray gewagt, der Code sieht aber irgendwie wahnsinnig umständlich aus. Ich frage mich, ob man das nicht einfacher implementieren könnte...

// ---------------------------------- public method "Dequeue" ---------------------------------
// This method returns the item on the top of this Queue and removes it.
// In debug mode, an exception is thrown if this Queue is currently empty.
// Author: Samuel Lörtscher
// --------------------------------------------------------------------------------------------
template<class T> T Queue<T>::Dequeue(void){
 // Assert that this Queue is currently not empty.
 Assert(this->cItm,EmptyQueueException,0x00);

 // copy the item located at the front of this Queue
 T itm = this->arItm[this->iFro];

 // adjust the front index and the item counter
 this->iFro = (this->iFro+1)%this->cCap;
 --this->cItm;

 // check if shrinking is enabled and if the currently stored item would
 // only need half the space (in this case, reallocation is necessary)
 if(this->bShr && this->cCap > this->cIni && this->cItm < this->cCap >> 1){
  // reallocate a new memory block with half the size of the current capacity
  T *pNew = new T[this->cCap >> 1];

  // check if the rear comes before the front
  if(this->iRea < this->iFro){
   // rearrange the entire memory
   memcpy(pNew,&this->arItm[this->iFro],(this->cCap-this->iFro)*sizeof(T));
   if(this->iRea) memcpy(&pNew[this->cCap-this->iFro],this->arItm,this->iRea*sizeof(T));
  }
  // otherwise simply copy all items like in a traditional c-array
  else memcpy(pNew,&this->arItm[this->iFro],(this->cItm)*sizeof(T));

  // delete the old memory block and reassing the new one
  delete []this->arItm;
  this->arItm = pNew;

  // finally adjust the front and rear index and the current capacity
  this->iFro = 0;
  this->iRea = this->cItm;
  this->cCap >>= 1;
 }

 // finally return the item which was at the front of this Queue
 return itm;
}
// --------------------------------------------------------------------------------------------

[unskilled]

rück mal bitte mehr als ein zeichen ein, so erkennt doch keiner was

was mir aber auf den ersten blick auffällt:
memcpy(pNew,&this->arItm[this->iFro],(this->cCap-this->iFro)*sizeof(T));
bäm!
undefiniertes verhalten, wenn T kein POD ist - aber warst das nicht du, der in dem anderen thread das gefragt hatte? oder bild ich mir das gerad ein? ^^

bb

[Ishildur]

Guten morgen Unskilled
Ja was di POD's betrifft hast du natürlich recht. Es ist in der Tat so, dass ich ausschliesslich PDO's oder Zeiger auf nicht POD's übergebe. Das ist natürlich sehr gefährlich und möglicherweise auch der falsche Weg. Ich gehe aber doch richtig in der Annahme, dass eine for schleife, welche 1000 Assignment operatoren aufruft, DEUTLICH ineffizienter wird als ein memcpy?

Gruss Samuel

[volkard]

Ishildur schrieb:

Könntest du mir vielleicht noch einen Typ geben, ob man eine Queue besser mit einer LinkedList oder einem DynamicArray implementiert?

Array? Wenn es voll ist und wachsen muß, müssen alle Daten umkopiert werden. Und weil man bei pop die Daten nicht immer vorrutschen lassen will, läßt man es auch immer wieder vollaufen.
Verkettete Liste? Man zahlt pro Objekt ein new+delete und hat bei int als Nutzdaten gleich mal 28 Bytes overhead, 700%.
Machs kombiniert. Lauter 8192 (manche nehmen auch nur 128) Bytes große Mini-Arrays, die verkettet sind oder durch eine verkettet Liste verwaltet werden. Macht im Durchschnitt einen Speicheroverhead von einer halbe Seite plus wenige Promill der Nutzdaten. Laufzeit ist schneller, da kaum new und nie Umkopieren.

[volkard]

Ishildur schrieb:

Ich gehe aber doch richtig in der Annahme, dass eine for schleife, welche 1000 Assignment operatoren aufruft, DEUTLICH ineffizienter wird als ein memcpy?

Dein Freund der Compiler hat eine POD-Kopierschleife gefälligst zu erkennen und memcpy draus zu machen, ohne daß Du eingreifen mußt.

[Ishildur]

Hmm, aber ich habe das Array ja zirkulär gemacht, damit sollte es eigentlich nicht ständig überlaufen und es sollte auch nichts verschoben bei einem Dequeue?

[volkard]

Ishildur schrieb:

Hehe, du bis echt überzeugend

Danke.

Ishildur schrieb:

// ---------------------------------- public method "Dequeue" ---------------------------------
// This method returns the item on the top of this Queue and removes it.
// In debug mode, an exception is thrown if this Queue is currently empty.
// Author: Samuel Lörtscher
// --------------------------------------------------------------------------------------------
template<class T> T Queue<T>::Dequeue(void){
 // Assert that this Queue is currently not empty.
 Assert(this->cItm,EmptyQueueException,0x00);

 // copy the item located at the front of this Queue
 T itm = this->arItm[this->iFro];
 
 // adjust the front index and the item counter
 this->iFro = (this->iFro+1)%this->cCap;
 --this->cItm;

 // check if shrinking is enabled and if the currently stored item would
 // only need half the space (in this case, reallocation is necessary)
 if(this->bShr && this->cCap > this->cIni && this->cItm < this->cCap >> 1){
  // reallocate a new memory block with half the size of the current capacity
  T *pNew = new T[this->cCap >> 1];
  
  // check if the rear comes before the front
  if(this->iRea < this->iFro){
   // rearrange the entire memory
   memcpy(pNew,&this->arItm[this->iFro],(this->cCap-this->iFro)*sizeof(T));
   if(this->iRea) memcpy(&pNew[this->cCap-this->iFro],this->arItm,this->iRea*sizeof(T));
  }
  // otherwise simply copy all items like in a traditional c-array
  else memcpy(pNew,&this->arItm[this->iFro],(this->cItm)*sizeof(T));

  // delete the old memory block and reassing the new one
  delete []this->arItm;
  this->arItm = pNew;

  // finally adjust the front and rear index and the current capacity
  this->iFro = 0;
  this->iRea = this->cItm;
  this->cCap >>= 1;
 }

 // finally return the item which was at the front of this Queue
 return itm;
}
// --------------------------------------------------------------------------------------------

Ich kann Deinen Code nur mot größter Mühe lesen.
this->cCap >>= 1;
this-> bringt nix, ist für mich ungewohntes Rauschen
c ist UN und damit eh gestorben
Cap sagt hingegen nicht aus, was die Bedeutung ist

=1 ist verschleiertes /2

Na, dann hoffe ich mal, Du kannst meinen Code besser lesen als och Deinen. Ich habs auch mal gemacht. Ungetestet. Und meine schrumpft nicht auf Verdacht, sondern immer nur wenn der Schreibzeiger hinten angekpmmen ist.

template<typename T>
class Queue{//FIFO
	private:
	T* memoryBegin;
	T* memoryEnd;
	T* readPos;
	T* writePos;
	void refresh(){//Kopiert alle Daten in neuen Speicherblock
		size_t dataSize=writePos-readPos;
		size_t memorySize=std::max(dataSize*2,16);
		T* newMemoryBegin=new T[memorySize];
		std::uninitialized_copy(readPos,writePos,newMemoryBegin);//hier drin memcpy für PODs gewünscht
		std::destroy(readPos,writePos);
		delete[] memoryBegin;
		memoryBegin=newMemoryBegin;
		memoryEnd=newMemoryBegin+memorySize;
		readPos=newMemoryBegin;
		writePos=newMemoryBegin+dataSize;
	}
	public:
	Queue(){
		memoryBegin=0;
		readPos=0;
		writePos=0;
	}
	~Queue(){
		std::destroy(readPos,writePos);
	}
	void push(T const& t){
		if(writePos==end)
			refresh();
		new(*writePos) T(t);
		++writePos;
	}
	T& peek(){
		return *readPos;
	}
	void pop(){
		assert(!isEmpty());
		++readPos;
	}
	bool isEmpty(){
		return readPos==writePos;
	}
};

Hmm, aber ich habe das Array ja zirkulär gemacht, damit sollte es eigentlich nicht ständig überlaufen und es sollte auch nichts verschoben bei einem Dequeue?

Uups, meine ist nicht zirkulär. Mal sehen, ob ich das noch einbazen kann.

[volkard]

Die Änderungen waren minimal.

template<typename T>
class Queue{//FIFO
	private:
	T* memoryBegin;
	T* memoryEnd;
	T* readPos;
	T* writePos;
	void refresh(){//Kopiert alle Daten in neuen Speicherblock
		size_t dataSize=writePos-readPos;
		size_t memorySize=std::max(dataSize*2,16);
		T* newMemoryBegin=new T[memorySize];
		if(readPos<=writePos)
			std::uninitialized_copy(readPos,writePos,newMemoryBegin);//hier drin memcpy für PODs gewünscht
			std::destroy(readPos,writePos);
		else{
			T* tmp=std::uninitialized_copy(readPos,memoryEnd,newMemoryBegin);
			std::uninitialized_copy(memoryBegin,writePos,tmp);
			std::destroy(readPos,memoryEnd);
			std::destroy(memoryBegin,writePos);
		}
		delete[] memoryBegin;
		memoryBegin=newMemoryBegin;
		memoryEnd=newMemoryBegin+memorySize;
		readPos=newMemoryBegin;
		writePos=newMemoryBegin+dataSize;
	}
	public:
	Queue(){
		memoryBegin=0;
		readPos=0;
		writePos=0;
	}
	~Queue(){
		if(readPos<=writePos)
			std::destroy(readPos,writePos);
		else{
			std::destroy(readPos,memoryEnd);
			std::destroy(memoryBegin,writePos);
		}
		delete[] memoryBegin;
	}
	void push(T const& t){
		if(writePos==readPos)
			refresh();
		new(*writePos) T(t);
		++writePos;
		if(writePos==memoryEnd)
			writePos=memoryBegin;
	}
	T& peek(){
		return *readPos;
	}
	void pop(){
		assert(!isEmpty());
		++readPos;
		if(readPos==memoryEnd)
			readPos=memoryBegin;
	}
	bool isEmpty(){
		return readPos==writePos;
	}
};

Ungetestet und nicht excrptionsicher.

[volkard]

Ishildur schrieb:

Hmm, aber ich habe das Array ja zirkulär gemacht, damit sollte es eigentlich nicht ständig überlaufen und es sollte auch nichts verschoben bei einem Dequeue?

Hab ich jetzt auch probiert. Aber ich sehe nicht, daß das schneller ist als die kombinierte Version. Ich sehe zwei ifs in push statt nur einem. Das macht mich traurig. if(&&) zähle ich auch als zwei. Du zahlst sogar noch eine Division. Aha! Man kann die Größe zwingen, daß sie eine Zweierpotenz ist umd statt % ein leckeres & nehmen. Dann ist die zirkuläre Queue auch bei nur einem if angekommen.
Bis heute habe ich das nicht gesehen und die andere Version hat sich schneller angefühlt. Nun fühlen sie sich gleich an. Evtl die zirkuläre sogar schneller, weil mehr cache-Treffer? Aber bis zu 100% Speicheroverhead ist noch dabei.
Es bleibt mir wohl nichts anderes übrig, als beide Versionen zu bauen und dem Anwender zu überlassen, selber auszumessen, welche er nehmen will.