Nochmals Datenstrukturen



  • Guten Abend allerseits
    Ich habe nun das Studium für derjenigen für unsere Bachelorarbeit erforderlichen Datenstrukturen beinahe abgeschlossen. Dennoch sind einige Fragen hartnäckig offen geblieben:

    1. Was ist der Vorteil einer BinaryTree gegenüber einem RedBlackTree. Nun gut, ich kann mir vorstellen, dass der RedBlackTree ein wenig länger für das Einfügen und Entfernen von Elementen benötigt, weil er sich ja hierbei noch ausbalancieren muss. Auf der anderen Seite sollte ja im Gegenzug der Zugriff deutlich schneller ausfallen, weil die Suchtiefe geringer sein wird. Nun denke ich, dass doch in der Regel deutlich öfters auf eine Datenstruktur lesend als schreibend zugegriffen wird. Hat vielleicht jemand ein konkretes Beispiel eines Anwendungsfalles, wo ein BinaryTree einem RedBlackTree zu bevorzugen ist?

    2. Was ist der Vorteil eines BinaryTree gegenüber einer HashMap für ein Dictionary? Soviel ich weiss, ist ja die std::map der STL als BinaryTree implementiert? Aber warum dann nicht gleich ein RedBlackTree?

    3. Wieso sollte man einen Heap als LinkedList anstatt als Dynamisches Array implementieren? Ein dynamisches Array sollte doch deutlich schneller sein und aufgrund der Tatsache, dass ein Heap als kompletter Tree implementiert werden kann und sollte, auch deutlich weniger Memoryspeicher benötigen?

    Gruss Samuel



    1. naja - es ist auch mehr speicherplatz der belegt wird usw.
      das man immer mehr liest als schreibt, würde ich so auch nicht verallgemeinern wollen. außerdem ist der redblack eben wesentlich schwerer zu implementieren als nen normaler baum...
      bsp. für normale bäume: stammbäume, ... - hier fallen mir vor allem dinge ein, die man gar nicht wirklich sortieren kann...

    2. Was ist der Vorteil eines BinaryTree gegenüber einer HashMap für ein Dictionary? Soviel ich weiss, ist ja die std::map der STL als BinaryTree implementiert? Aber warum dann nicht gleich ein RedBlackTree?

    hört sich alles ein wenig konfus an...
    erst mal:
    ist ein redblack tree ja nen spezieller binary tree... zweitens ist hashmap was ganz anderes:
    http://en.wikipedia.org/wiki/Hash_table
    hat unter anderem den vorteil, dass das einfügen richtig schnell(bei nem perfekten hash-algo O(1)) ist, das suchen nach einem bestimmten Objekt auch O(1) ist und das durchiterieren auch nicht länger dauern sollte als bei nem baum... das problem ist eben nur, dass es nicht für jeden datentypen nen perfekten hash-algo gibt...
    und so weit ich weiß, ist für std::map keine Implementierung vorgeschrieben, nur Komplexitäten 😉

    3. Wieso sollte man einen Heap als LinkedList anstatt als Dynamisches Array implementieren? Ein dynamisches Array sollte doch deutlich schneller sein und aufgrund der Tatsache, dass ein Heap als kompletter Tree implementiert werden kann und sollte, auch deutlich weniger Memoryspeicher benötigen?

    weil man sonst den speicher am stück braucht? und unter umständen richtig viel kopieren müsste!?
    und so was:
    "Ein dynamisches Array sollte doch deutlich schneller sein" ist doch ne doofe aussage...
    durchiterieren sollte sich nix nehmen, zugriffszeiten könnten beim vector besser sein(aber auch nur, wenn die daten geordnet sind).
    einfügen / löschen (nicht am ende) ist bei der liste schneller etc
    es kommt halt immer auf die aufgaben an, was schneller ist usw.
    wenn man z.bsp. ein spiel programmiert, was konstant 60fps haben soll, ists nich so klug, in nen vector große daten (nicht ans ende) zu schreiben - dann hat man zwar zu 90% vll so gar 65fps aber in den anderen 10% dann plötzlich performance-einbußen, die den spielfluss komplett stören...

    da ins besondere deine letzte frage etwas sehr eigenartig formuliert war, bin ich mir nicht sicher, ob meine antworten zu deinen fragen passt ;o) aber ich red mich dann einfach mit "falsches forum, besser wäre RudP. das hat nix mit C++ zu tun..." raus ;o)

    bb

    edit: worauf ich bei 3. hinaus wollte: bei einer liste kennt man die Zeiten für Einfügen, Löschen, ... bei einem Baum oder Array oder was auch immer, können die aber sehr stark schwanken - wäre zumindest ein Grund für die Liste - aber nat. könnte man dort auch nen Baum nehmen (was ja ohnehin schon klar ist, da ne Liste ja nix anderes ist, als nen (entarteter) binärer Baum). allerdings muss ich gestehen, dass mir die Frage bei jedem Mal durchlesen wieder anders zu sein scheint ;o)



  • @unskilled
    Hallo "Skilled" 😉
    Erstmal vielen Dank für dein Interesse. Ja vermutlich ist die Frage 3 ein wenig ungeschickt formuliert. Soweit ich es im Moment verstehe, muss eben bei einem Heap bei Insert Operationen nichts kopiert werden (ausser es muss dynamisch vergrössert werden), weil jedes Element zuerst einmal an die letzte Stelle eingefügt wird und schliesslich ein BubbleUp durchgeführt wird, um die interne Ordnung wieder herzustellen. Ein Heap wird also nie zu einer Sequenz oder fast Sequenz degenerieren, wie dies bspw. bei einem BinaryTree passieren kann. Was das dynamische Vergrössern angeht, so bin ich mir nicht so sicher, ob die zehntausende New's und delete's und der daraus resultierenden Heap Fragmentierung beim Einfügen und Entfernen von Elementen bei einer verketteten Liste nicht plötzlich mehr zu Lasten der Performance gehen als die paar wenige new's und memcpy's bei einer DynamicList... Währe dann zumindest noch abzukären... 😉

    So nun aber zu den Zugriffszeiten bei einem Heap:
    Einfügen und Enternen:
    Dynamic Array: O(1) für das auffinden des letzten Nodes + O(log(n)) bei einem Worstcase BubbleUp = O(1+log(n)) = O(log(n))
    LinkedList: O(log(n) für das Auffinden des letzten Nodes + O(log(n)) bei einem Worstcase BubbleUp = O(2*log(n)) = O(log(n))

    Remove Operationen verhalten sich IMHO Identisch und Top ist bei beiden Implementierungen O(1).
    Das Asymptotische Wachstum scheint also bei beiden Implementierungen identisch zu sein, aber die effektive Laufzeit unterscheidet sich doch schon stark:
    n = 1024;
    Dynamic Array Einfügen & Entfernen: 1+log(1024) = 1+10 = 11
    LinkedList Einfügen & Entfernen: 2*log(1024) = 2*10 = 20

    Wir sehen, die Implementierung mit der Verketteten Liste hat zwar ein identisches asymptotisches Wachstum, auf welches immer so gerne verwiesen wird, in der Realität benötigt sie jedoch beinahe doppelt so lange für schreibende Zugriffe in einen Heap, welche die Grundlage einer PriorityQueue ist. Hinzu kommt noch, dass das BubbleUp verfahren bei einer VerkettetenList noch zusätzlich deutlich aufwändiger ist als bei einem Dynamischen Array.

    Bitte erhängt mich nicht, wenn ich was falsches geschrieben habe. Ich möchte das Geschriebene nicht als Tatsache deklarieren sondern lediglich meine Gedanken zu diesem Thema zum Ausdruck bringen...

    Gruss Samuel



  • Ishildur schrieb:

    1. Was ist der Vorteil einer BinaryTree gegenüber einem RedBlackTree.

    Versteh die Frage nicht. Ich dachte, ein RedBlackTree sei ein BinaryTree.

    Ishildur schrieb:

    Nun gut, ich kann mir vorstellen, dass der RedBlackTree ein wenig länger für das Einfügen und Entfernen von Elementen benötigt, weil er sich ja hierbei noch ausbalancieren muss. Auf der anderen Seite sollte ja im Gegenzug der Zugriff deutlich schneller ausfallen, weil die Suchtiefe geringer sein wird.

    Naja, wenn die Einfügungen zufällig sind, hat man nur als durchschnittliche Tiefe (also Zugriffsteit) nur eins mehr zu erwarten als bei einem optimal ballancierten Baum.

    Ishildur schrieb:

    Nun denke ich, dass doch in der Regel deutlich öfters auf eine Datenstruktur lesend als schreibend zugegriffen wird. Hat vielleicht jemand ein konkretes Beispiel eines Anwendungsfalles, wo ein BinaryTree einem RedBlackTree zu bevorzugen ist?

    Wenn man zufällig weiß, daß die Daten zufällig kommen und daß sauwenig gelesen wird, züm Beispiel nur am Ende um die sortierten Daten auszugeben. Man müßte sich noch Randbedingungen ausdenken, die vector&sort verbieten, zum Beispiel Daten, die nur sehr langsam kopiert werden können oder gar gar nicht geswapped werden können.

    Ishildur schrieb:

    2. Was ist der Vorteil eines BinaryTree gegenüber einer HashMap für ein Dictionary?

    Daß man nicht hashen muß. Zum einen ist die Wahl einer guten Hashfunktion eine Kunst und wenn man sich vergreift, hat man O(n) statt O(1). Zum anderen gibt es dumme Umstände, zum Beispiel liegen in meinem Dictionary alle meine mp3-files. strcmp gibt nach dem ersten byte-Unterschied ein Ergebnis, bei 2^30 zufälligen files normalerweise nach 4 bytes. die files immer zu hashen dauert ewig und dann noch drei tage.

    Ishildur schrieb:

    3. Wieso sollte man einen Heap als LinkedList anstatt als Dynamisches Array implementieren?

    Die Frage verstehe ich gar nicht. Ist Heap im Sinne von Freispeichermanagement gemeint? Oder als der nette Binärbaum mit Heap-Bedingung? Im letzteren Fall gibt es ungefäht null Gründe für di Listen, außer obengenannten "Man müßte sich noch Randbedingungen ausdenken, die HeapAsArray verbieten, zum Beispiel Daten, die nur sehr langsam kopiert werden können oder gar gar nicht geswapped werden können."



  • @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?



  • 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(i
    161%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.



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



  • 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;
    }
    // --------------------------------------------------------------------------------------------
    


  • 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



  • 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



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



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



  • 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?



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



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



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


Anmelden zum Antworten