3. Heap und std::vector und das ganze auf Pointern

Heap und std::vector und das ganze auf Pointern

  • L

    Dachte auch, dass GLIBCXX_MOVE sehr nach C++0x aussieht ;). Aber komisch, dass die g++ STL anscheinend kein swap für die heap functionen benutzt.

    0
  • M

    life du hast mich schon ein bisschen weitergebracht aber es geht immer noch nicht :D.
    Dein Copy Assignment Operator macht auf jeden Fall Sinn und der Check im CopyConstruktor auch. Das Programm rechnet schon weiter als vorher aber das push_heap beim decreaseKey übersteht es immer noch nicht.

    0
  • L

    Wenn du es selbst nicht debugged bekommst, am besten mal aktuellen Quellcode + Beispieleingabedatei anhängen.

    0
  • M

    Ok zu dem && beles ich mich morgen nochmal.

    Ich bekomm nur als Fehler ein: expected ‘,’ or ‘...’ before ‘&&’ token
    Weiterhin muss das Argument im Copy Contruktor const sein, sonst beschwert sich der Compiler: /usr/include/c++/4.4/bits/vector.tcc:306: error: no matching function for call to ‘MovableVertex::MovableVertex(const MovableVertex&)’

    @volkard: heißt das wir müssen move überladen?

    0
  • V

    life schrieb:

    Dachte auch, dass GLIBCXX_MOVE sehr nach C++0x aussieht ;). Aber komisch, dass die g++ STL anscheinend kein swap für die heap functionen benutzt.

    template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
    void
    __push_heap(_RandomAccessIterator __first,
		_Distance __holeIndex, _Distance __topIndex, _Tp __value)
    {
      _Distance __parent = (__holeIndex - 1) / 2;
      while (__holeIndex > __topIndex && *(__first + __parent) < __value)
	{
	  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
	  __holeIndex = __parent;
	  __parent = (__holeIndex - 1) / 2;
	}
      *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
    }

    Er fügt erstmal nicht ein, sondern läßt anhand des value erstmal nur das Loch hochblubbern/versickern.
    Ein swap sind drei MOVS, ein move mit ptr->revptr=this;rhs.ptr=0; dürfte ähnlich sein. Also egal. Aber wenn im Heap nur platte integers oder Zeiger sind, dürfte die move-Variante die swap-Variante plattmachen.

    0
  • L

    @Max3000: Du musst C++0x mittels Compilerflag aktivieren, wenn du '&&' verwenden willst.

    0
  • V

    Max3000 schrieb:

    @volkard: heißt das wir müssen move überladen?

    Nein. std::move benutzt automagisch lifes &&-Versionen.

    0
  • M

    Geht das ganze irgendwie auch ohne das &&?
    Mit -std=c++0x als Compiler Flag kompiliert er zwar wieder, aber es kommt immer noch ein Speicherzugriffsfehler an der selben stelle. So langsam weiß ich nicht mehr weiter :(.

    0
  • M

    @life: Dein assert im Destruktor wird irgendwie ausgelöst. Muss das wirklich

    assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this);

    sein?
    Wenn man den CopyConstruktor für ein anderes Objekt aufruft, wird ptr doch auf 0 gesetzt.

    0
  • V

    Max3000 schrieb:

    Geht das ganze irgendwie auch ohne das &&?

    Die Alternative, die ich mir ausgedacht hatte, als ich noch nicht müde war, ist sich selber einen Heap zu bauen, der swap benutzt. Und auf den Destruktor und möglichst viel Magie der MoveableVerices zu verzichten.

    0
  • M

    Ich hab grad nochmal durchdebuggt und der Fehler liegt jetzt wo anders und zwar hier:

    push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	  _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	  _DistanceType;

      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_heap(__first, __last - 1);

      _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
      std::__push_heap(__first, _DistanceType((__last - __first) - 1),
		       _DistanceType(0), _GLIBCXX_MOVE(__value));
    }

    __first sieht ganz gut aus, aber __last ist 0:

    (gdb) print __last
    $18 = (MovableVertex 😉 0x0

    , wobei ein MovableVertex* nur im Konstruktor von MovableVertex selbst 0 gesetzt wird, also:

    ~MovableVertex()
    {
    if(ref != 0)
    ref->revref = 0;
    }

    Kann es sein dass revref auf ein anderes MovableVertex zeigt und nicht einmal auf das, was gelöscht wird?

    0
  • M

    Jetzt habe ich den Fehler schon wieder wo anders.
    Und zwar kommt im Debugger nur:

    Program received signal SIGABRT, Aborted.
    0x00007ffff733d4e5 in raise () from /lib64/libc.so.6

    Mein MovableVertex sieht mitlerweile so aus:

    class MovableVertex
{
public:
  MovableVertex(Vertex* vertex) : ref(vertex) 
  {
    assert(vertex != 0);
    assert(ref->revref == 0);
    ref->revref = this;
  }
  ~MovableVertex() 
  {
    if(ref != 0)
      {
	assert(this != ref->revref);
	ref->revref = 0;
      }
  }
  MovableVertex(MovableVertex &&vertex) : ref(vertex.ref) {
    std::cout << "Copy Constructor\n";
    if(ref != 0)
      ref->revref = this;
    vertex.ref = 0;   
  }

  MovableVertex& operator=(MovableVertex &&rhs) {
    std::cout << "Assignment operator\n";
   ref = rhs.ref;
    if(ref != 0) {          
      ref->revref = this;
    }
    rhs.ref = 0;        

    return *this;
  } 

  Vertex* ref;

  friend bool operator<(const MovableVertex &v1, const MovableVertex &v2)
  {
    return v1.ref->key > v2.ref->key;
  }

  void swap(MovableVertex& a,MovableVertex& b){
    std::cout << "swap\n";
    std::swap(a.ref,b.ref);
    std::swap(a.ref->revref,a.ref->revref);
  } 
};
    0
  • V

    Mein Köpfchen qualmt, aber vielleicht habe ich ein Fehlerchen in der letzten life-Version gefunden.

    struct MovableNodePtr  { 
    Node* ptr; 

    MovableNodePtr(Node* ptr) : ptr(ptr) { //Ich heirate ihn
        assert(ptr != 0); //ja, den Mann muß es geben
        assert(ptr->revptr == 0); //und er darf noch keine Frau haben
        ptr->revptr = this; //Und er heiratet mich
    } 

    MovableNodePtr(MovableNodePtr&& rhs) : ptr(rhs.ptr) { //Ich heirate ihn auch
    	//Jetzt ist er ein Bigamist
        assert(ptr != 0); //Den Mann muß es geben
        ptr->revptr = this; //Er heiratet mich und läßt sich gleichzeitig von ihr scheiden
        rhs.ptr = 0; //Sie läßt sich von ihm scheiden. 
    } 

    MovableNodePtr& operator=(MovableNodePtr&& rhs) { 
//>>> Die folgenden 2 Zeilen fehlte!
        if(ptr)//Falls ich verheiratet bin
                ptr->revptr = 0; //Mein alter läßt sich von mir scheiden
        ptr = rhs.ptr; //Ich heirate den Neuen und lasse mich von meinem alten scheiden
        assert(ptr != 0); //Es muß den Mann geben
        ptr->revptr = this; //Der Mann heiratet mich
        rhs.ptr = 0; //sie läßt sich scheiden
        return *this; 
    } 

    ~MovableNodePtr(){ 
        assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this); 
        if(ptr != 0) { //Falls ich verheiratat war
            ptr->revptr=0; //Der Mann läßt sich von mir scheiden
        } 
    }     

    friend bool operator<(MovableNodePtr const& a,MovableNodePtr const& b){ 
        return a.ptr->key<b.ptr->key;//juhu, wir sind comp losgeworden 
    } 

private: 
    MovableNodePtr(const MovableNodePtr& rhs) { 
        assert(false);       
    } 

    MovableNodePtr operator=(const MovableNodePtr& rhs) { 
        assert(false); 
    } 

};
    0
  • M

    Ich hab den Fehler gefunden 🙂

    Lag wirklich am Destruktor.
    Ich hab ihn jetzt so:

    ~MovableVertex() 
  {
    if(ref != 0 && this == ref->revref)
      {
	  ref->revref = 0;
      }
  }

    Der revref vom vertex auf die man zeigt darf nicht auf einen anderen movablevertex zeigen. Wenn der auf einen anderen zeigt darf der pointer nicht einfach 0 gesetzt werden.

    Und der Algorithmus läuft jetzt schneller als mit dem kompletten make_heap, falls ihr euch noch an den Anfang dieses Thread erinnern könnt.

    Vielen dank für eure Hilfe.
    Hab wieder sehr viel durch euch gelernt 🙂

    Grüße

    Max

    0
  • V

    Max3000 schrieb:

    Und der Algorithmus läuft jetzt schneller als mit dem kompletten make_heap, falls ihr euch noch an den Anfang dieses Thread erinnern könnt.

    Ja, das war anzunehmen. Aber wie schnell im Vergleich zum Fibonacci-Heap?
    Weil ich auch den Verdacht hege, daß der Fibonacci-Heap eher von theoretischem Interesse ist.

    0
  • V

    Max3000 schrieb:

    Der revref vom vertex auf die man zeigt darf nicht auf einen anderen movablevertex zeigen.

    Ja, das sehe ich auch so.

    Max3000 schrieb:

    Wenn der auf einen anderen zeigt darf der pointer nicht einfach 0 gesetzt werden.

    Hätte nie passieren dürfen, daß ich auf einen Mann zeige, der nicht auf mich zeigt. Dachte ich.

    0
  • L

    volkard schrieb:

    Max3000 schrieb:

    Wenn der auf einen anderen zeigt darf der pointer nicht einfach 0 gesetzt werden.

    Hätte nie passieren dürfen, daß ich auf einen Mann zeige, der nicht auf mich zeigt. Dachte ich.

    Richtig. Da läuft irgendwas schief..

    0
  • M

    Stimmt.
    Wenn man das sauber gemacht hätte, wäre die 2. Bedingung im if überflüssig.
    Aber das schau ich mir morgen an. Jetzt ists zu spät :).

    Im laufe dieser Diskussion hatte ich noch was am FibonacciHeap geändert, der jetzt auch nicht mehr funktioniert, weil ich einige Performance-Killer da drin gefunden habe.
    Dort wollte ich ja auch die Kind-Elemente in einem std::vector speichern, aber ich muss manchmal im Algo ein Kind löschen, das heißt wieder erase auf ein Element in der Mitte einer Liste. Das geht natürlich wieder nicht weil ich einen Iterator dafür brauche.
    Da bin ich jetzt noch dran und ich werd das mal posten wenn ichs fertig habe.

    Außerdem hatte ich am Anfang dieses Threads mal nachgefragt was ich für eine Datenstruktur für folgendes nehme:

    Ich muss beim DeleteMin alle Kinder von minRoot in die RootList verschieben und die verlinken wenn 2 Elemente den selben Rang haben (Rang = Anzahl der Kindelemente).

    Dazu füg ich nacheinander die Kinder an die Rank-te Position einer Liste. Wenn das erste Kind Rang 5 hat und so, dann kann ich keinen Vector oder sowas nehmen.
    Ich habe dann std::map ausprobiert, aber das ist noch langsamer als mein ursprünglicher Array aus 100 Elementen (das ist hässlich, ich weiß). Was fällt dir spontan dazu ein was man da nehmen könnte?

    Habe vorhin auch eine C Implementierung vom FibonacciHeap gefunden wo die das auch mit einem dynamischen Array machen, aber die Größe immer unterschiedlich haben. Also irgendwie wurde der dort aus einem logarithmus-ausdruck immer berechnet. Das wäre was was ich noch versuchen könnte.

    Ok Danke für alles volkard und life.

    Grüße

    Max

    0
  • V

    life schrieb:

    Richtig. Da läuft irgendwas schief..

    Mein Fehlerfund würde es erklären. Er paßt zum Symptom.

    0
  • L

    volkard schrieb:

    life schrieb:

    Richtig. Da läuft irgendwas schief..

    Mein Fehlerfund würde es erklären. Er paßt zum Symptom.

    Imho nein. Ich stimme dir zwar zu, dass es ein Fehler ist (Inkonsistent mit Destruktor), aber im Prinzip sollte es doch egal sein, ob bei ptr->revptr 0 oder irgend ein ungültiger Wert steht: wenn man darauf zugreift macht man in beiden Fällen was falsch.

    Eigentlich sollte es doch auch so funktionieren:

    struct MovableNodePtr  {
    Node* ptr;

    MovableNodePtr(Node* ptr) : ptr(ptr) {
		assert(ptr != 0);
		ptr->revptr = this;
    }

    MovableNodePtr(MovableNodePtr&& rhs) : ptr(rhs.ptr) {
        ptr->revptr = this;        
    }

    MovableNodePtr& operator=(MovableNodePtr&& rhs) {
        ptr = rhs.ptr;
        ptr->revptr = this;		
		return *this;
    }

    ~MovableNodePtr(){

    }    

    friend bool operator<(MovableNodePtr const& a,MovableNodePtr const& b){
        return a.ptr->key<b.ptr->key;//juhu, wir sind comp losgeworden
    }

private:
    MovableNodePtr(const MovableNodePtr& rhs) {
        assert(false);      
    }

    MovableNodePtr operator=(const MovableNodePtr& rhs) {
        assert(false);
    }

};
    0
Anmelden zum Antworten