Thomas Kramer

IT-COW | All posts tagged 'Reingold-Tilford-Algorithmus'

Portierung des Reingold-Tilford-Algorithmus von Java/Swing auf C++/Qt

By Administrator at Juli 15, 2014 20:53
Filed Under: Algorithmen, C(++), Projekte

Nebenbei habe ich meine alte Implementierung des Reingold-Tilford-Algorithmus von Java/Swing auf C++ unter der Verwendung des GUI-Frameworks Qt portiert. Als Entwicklungsumgebung dienten QtCreator 3.0.1 und Qt 5.2.1.

 

Folgende Schwierigkeiten traten bei der Portierung auf C++ zutage:

 

1. Der C++-Zufallszahlengenerator rand() erzeugt nur 15bittige Zufallszahlen (bis 32767), für größere Zufallszahlen muss mit Bit-Shifting gearbeitet werden. Für eine 32bittige Zufallszahl müssen demnach drei Zufallszahlen generiert und miteinander verwoben werden:

 

int rnd1 = rand();
int rnd2 = rand();
int rnd3 = rand();

unsigned int bigrnd = ((rnd1 & 0x03) << 30) + (rnd2 << 15) + rnd3;
bigrnd = (bigrnd % (Zahlenobergrenze-Zahlenuntergrenze+1)) + Zahlenuntergrenze;

 

Dadurch werden zunächst die letzten beiden Bit von der ersten Zufallszahl abgeschnitten (0x03 entspricht binär 11), dann um 30 Stellen nach links verschoben, darauf die ganze 15-stellige zweite Zufallszahl addiert welche mittig eingewoben wird und auf das Ergebnis rechtsseitig die letzten 15 Bit der dritten Zufallszahl addiert. Mittels Modulo wird dann auf die tatsächliche Zahlenobergrenze abgeschnitten.

 

In Java ist dies bedeutend einfacher zu realisieren:

 

(int) random(Zahlenuntergrenze, Zahlenobergrenze)

 

2. Fehlermeldungen durch sich gegenseitig referenzierende Header-Dateien, als Lösung können Forward declarations verwendet werden.

 

3. Zeiger-Referenzen und –Dereferenzierung, das Projekt war diesbezüglich eine gute Übung für mich.

 

4. C(++)-typisch müssen die erzeugten Objekte händisch wieder freigegeben werden; es gibt standardmäßig keinen Garbage Collector. Die Vor- und Nachteile von GCs werden in diesem Eintrag auf Stackoverflow ausführlich erläutert, als Alternative werden auch Smart Pointers aufgeführt.

 

Smart Pointers sind Objekte welche Pointer mit einem Referenzzähler kapseln und wenn alle Referenzen entfernt wurden das zugrundeliegende Objekt automatisch löschen. In C++ 11 wurde dazu u. a. die Klasse shared_ptr eingeführt.

 

Leider kann shared_ptr nur bei einzelnen Objekten den Speicher korrekt freigeben, bei Arrays muss ein eigener Deleter übergeben werden.

 

Ein Beispiel wie das aussehen kann:

 

#include <tr1/shared_ptr.h>
#include <tr1/memory>

using namespace std::tr1;

template< typename T >
struct array_deleter
{
  void operator ()( T const * p)
  {
     delete[] p;
  }
};

tr1::shared_ptr<tBaum> p1(new tBaum[rows], array_deleter<tBaum>());

 

Der zweite Parameter ist optional und wird nur bei Arrays benötigt.

 

Leider habe ich noch keine Möglichkeit gefunden einen Shared Pointer zunächst lediglich zu deklarieren und die zugrundeliegende Variable (deren Pointer verwaltet werden sollen) später zu übergeben, etwa weil ein Array benötigt wird und dessen Größe erst noch berechnet werden muss.

 

Folgender Befehl funktioniert leider nicht:

 

std::tr1::shared_ptr<tBaum> p1;
p1 = new shared_ptr(new tBaum[rows], array_deleter<tBaum>());

 

Daher habe ich in meinem Projekt vorerst noch auf die Benutzung von Smart Pointern verzichtet und die Objekte auf die klassische Weise freigegeben, im Destruktor.

 

Für den Fall dass ich irgendwann den Boehm Garbage Collector verwenden will verlinke ich zwei lesenswerte Artikel, da hilfreiche Artikel dazu recht schwer zu finden sind: 1 2

 

5. Die Äquivalente zu Hashtables/HashMaps und HashSets in Java sind in C++ erst ab Version 11 mit unordered_map und unordered_set verfügbar und mussten davor erst durch Bibliotheken wie Boost eingebunden werden.

 

Für die Unterschiede zwischen map und unordered_map möchte ich auf diesen Stackoverflow-Eintrag verweisen, die Performance-Unterschiede werden hier erläutert.

 

6. Das Koordinatensystem von QGraphicsScene beginnt mit negativen x- und y-Koordinaten für die linke obere Ecke, anders als bei Swing in Java. Das Blog-Posting von Maya Posch verdeutlicht dies, allerdings scheint ihr nicht bekannt gewesen zu sein dass optional als Konstruktor von QGraphicsScene ein eigenes Koordinatensystem übergeben werden kann.

 

An der Stelle hatte ich in Unkenntnis dessen zuerst ebenfalls den parameterlosen Konstruktor benutzt und mit Matrizen-Transformationen auf QGraphicsScene getestet, welches eine translate-Methode beinhaltet. Leider hat diese Translate-Methode einen Bug, so dass sie auf einzelne Items, aber nicht auf QGraphicsScene angewandt einen Effekt ausübt.

 

Alternativ zu den Translate-Methoden können auch über die QTransform-Klasse (QMatrix gilt als deprecated) eigene Transformations-Matrizen berechnet werden; in diesem Blog befindet sich ein Beispiel dazu. Drehung/Skalierung und Scherung funktioniert, aber Verschiebung (Translation) wird auch über diesen Weg von QGraphicsScene ignoriert.

 

Da ein eigenes Koordinatensystem bei dem Konstruktor von QGraphicsScene übergeben und einzelne Objekte direkt verschoben werden können ist das Problem unwichtig, aber das muss man eben auch erst einmal wissen.

 

Im Großen und Ganzen waren dies die aufgetretenen Probleme bei der Portierung meines Binärbaum-Programms auf C++/Qt, für die ich immerhin fünf Tage benötigt habe.

 

Nachfolgend ein Performance-Vergleich auf meinem Notebook mit Pentium DualCore T4200@2 GHZ unter Windows 7 64 Bit. Als Test-Parameter habe ich jeweils 1.000.000 Knoten erzeugen und genausoviele RMQ-Abfragen durchführen lassen, natürlich ohne Zeichnen:

 

C++/Qt:

 

Berechnung Zeit
Erzeugen der Zufallszahlen: 0 Sekunden
Zwischenergebnis, Erzeugen der Knoten: 1096 Sekunden = 18,27 Minuten
RT-Algorithmus: 1098 Sekunden = 18,30 Minuten
Erstellung der RMQ-Arrays: 2 Sekunden
RMQ-Abfragen: 0 Sekunden

 

Java/Swing:

 

Berechnung Zeit
Erzeugen der Zufallszahlen: 00 min, 00 sec, 792 milliseconds
Erzeugen der Knoten: 01 min, 25 sec, 586 milliseconds
RT-Algorithmus:   01 min, 54 sec, 864 milliseconds
Erstellung der RMQ-Arrays: 00 min, 04 sec, 041 milliseconds
RMQ-Abfragen: 00 min, 00 sec, 839 milliseconds

 

Wie man sieht ist die C++-Version wesentlich langsamer, das kann eigentlich nur an der Implementierung des unordered_set liegen da der Algorithmus unverändert ist. Das Einfügen in unordered_set ist schnell wie man an der Erzeugung der Zufallszahlen sehen kann, aber danach iteriert er durch das Set und dies scheint recht langsam zu erfolgen, jedenfalls signifikant langsamer als bei der Implementierung des HashSets in Java.

 

Die unordered_map ist dagegen ähnlich schnell wie in Java, wie an der Zeitangabe zur Erstellung der RMQ-Arrays ersehen kann.

 

Der Reingold-Tilford-Algorithmus ist leider auf Bäume zweiten Grades beschränkt; für Bäume beliebigen Grades muss der Walker-Algorithmus verwendet werden. Was die relativ großen Lücken zwischen den Knoten betrifft so ist es auch die Vorgabe des Reingold-Tilford-Algorithmus, dass jeder Unterbaum genau symmetrisch darzustellen ist.

 

Mangels Dokumentation – selbst im Englischen sehr rar gesät – bin ich leider noch nicht dazu gekommen den Walker-Algorithmus zu implementieren, werde dies aber irgendwann noch nachholen. In Java habe ich das Zeichnen unbegrenzter Bäume bereits mittels der Abego TreeLayout-Bibliothek realisieren können.

 

Neue Funktionen

 

Gegenüber meinen alten Binärbaum-Varianten ist nun alternativ auch die Vorgabe der Anzahl Ebenen möglich, über die der generierte Zufallsbaum verfügen soll.

 

Download der C++/Qt-Version

 

Wegen der dynamisch eingebundenen Qt-Bibliotheken ist das Archiv etwas größer, 18 MB:

 

Binärbaum-Demo

 

Ohne kommerzielle Lizenz müssen gemäß den Lizenzbedingungen von Qt entweder der Quellcode freigegeben oder die benötigten Bibliotheken dynamisch eingebunden werden, über externe DLLs.

 

Download der Java-Version:

 

Als Referenz diente die letzte Processing-Version meines Algorithmus. Processing verwendet Java als Programmiersprache.

 

Monats-Liste