Thomas Kramer

IT-COW | All posts tagged 'Levelorder'

JAMon-Profiling des multithreaded RT-Algorithmus

By Administrator at Januar 10, 2012 20:54
Filed Under: Algorithmen, Java, Programmierung allgemein

Mittlerweile habe ich mich in das JAMon-API eingearbeitet und habe ein Profiling auf meine Variante drei vom multithreaded Reingold-Tilford-Algorithmus angewandt.

 

Bis zu zehn Monitore wende ich an, nachfolgend die Ergebnisse bei 500.000 Knoten auf meinem Pentium-DualCore T4200@2 GHZ-Notebook (ohne Zeichnen):


JAMon Label=Zufallszahlen-Generierung, Units=ms.: (LastValue=567.0, Hits=1.0, Avg=567.0, Total=567.0, Min=567.0, Max=567.0, Active=0.0, Avg Active=1.0, Max Active=1.0, First Access=Tue Jan 10 21:05:50 CET 2012, Last Access=Tue Jan 10 21:05:50 CET 2012)

JAMon Label=Erzeugung der Knoten, Units=ms.: (LastValue=20406.0, Hits=1.0, Avg=20406.0, Total=20406.0, Min=20406.0, Max=20406.0, Active=0.0, Avg Active=1.0, Max Active=1.0, First Access=Tue Jan 10 21:06:10 CET 2012, Last Access=Tue Jan 10 21:06:10 CET 2012)

JAMon Label=Versatz-Berechnung - LevelOrder-Traversierung insgesamt, Units=ms.: (LastValue=9882.0, Hits=1.0, Avg=9882.0, Total=9882.0, Min=9882.0, Max=9882.0, Active=0.0, Avg Active=1.0, Max Active=1.0, First Access=Tue Jan 10 21:06:20 CET 2012, Last Access=Tue Jan 10 21:06:20 CET 2012)

JAMon Label=Multithreading - finde max im linken Unterbaum, Units=ms.: (LastValue=53.0, Hits=124732.0, Avg=9.732354167334766, Total=1213936.0, Min=0.0, Max=119.0, Active=0.0, Avg Active=297.14911971266395, Max Active=427.0, First Access=Tue Jan 10 21:06:10 CET 2012, Last Access=Tue Jan 10 21:06:20 CET 2012)

JAMon Label=Multithreading - finde min im rechten Unterbaum, Units=ms.: (LastValue=53.0, Hits=124732.0, Avg=9.72946797934772, Total=1213576.0, Min=0.0, Max=119.0, Active=0.0, Avg Active=297.14911971266395, Max Active=427.0, First Access=Tue Jan 10 21:06:10 CET 2012, Last Access=Tue Jan 10 21:06:20 CET 2012)

JAMon Label=Versatz-Korrektur, Units=ms.: (LastValue=56.0, Hits=124732.0, Avg=0.05093320078247763, Total=6353.0, Min=0.0, Max=56.0, Active=0.0, Avg Active=1.0, Max Active=1.0, First Access=Tue Jan 10 21:06:10 CET 2012, Last Access=Tue Jan 10 21:06:20 CET 2012)

Per Stoppuhr habe ich 32 Sekunden insgesamt gemessen - die Rangfolge der Laufzeitergebnisse nach Rechenzeit sieht folgendermaßen aus:

 

1. Erzeugung der Knoten: 20,4 Sekunden

2. Levelorder-Traversierung insgesamt mit Versatz-Berechnung: 10 Sekunden

3. Zufallszahlen-Generierung im Vorfeld: 0,5 Sekunden

 

Die Multithreading-Operationen sind in 2. bereits enthalten und können nicht separat berücksichtigt werden weil JAMon mit Total=1213936.0 ms für die Suche im linken (A) und Total=1213576.0 ms für die Suche im rechten (B) Unterbaum Quatsch ausgibt, die gesamte Ausführungszeit betrug lediglich 32 Sekunden.

 

Interessant ist aber die Anzahl der gleichzeitig aktiven Threads, die gemäß Max Active jeweils maximal 427 betrug. Die beiden Threads pro Knoten (A und B) wurden insgesamt jeweils 124732 mal gestartet (Hits).

 

Zusammenfassend lässt sich sagen dass sich die Erzeugung der neuen Leveltable beim Erstellen der Knoten - die die Knoten pro Ebene enthält (Hilfskonstrukt für die Levelorder-Traversierung) - sicher noch optimieren lässt. Die Singlethread-Variante benötigte bei gleicher Knotenmenge -insgesamt- 8-10 Sekunden auf der gleichen Maschine, so dass der Algorithmus dort massiv langsamer geworden ist - das Multithreading alleine ist gar nicht so langsam, bringt aber für sich alleine bei diesem Algorithmus auch keinen Geschwindigkeitsvorteil denn dafür ist die Rechenlast beim RT-Algorithmus zu gering.

 

Die Regel Nr. 5 vom RT-Algorithmus wurde nicht mitgemessen weil das erst beim Zeichnen geschieht um einen separaten Rekursionsdurchlauf einzusparen.

 

Außerdem möchte ich auf die Laufzeitergebnisse in dem anderen Thread verlinken, damals noch bezogen auf die Singlethread-Variante (und auf das andere Notebook).

 

Update 31.01.2012: Hier habe ich noch einen interessanten Tipp gefunden: "Call system.gc() before every timing run to minimize inconsistent results due to garbage collection in the middle of a run."

 

Update 12.06.2012: Bezüglich der Levelorder-Traversierung ist es sinnvoller von der Java-BaumStruktur DefaultMutableTreeNode abzuleiten und dann Funktionen wie getPreviousSibling() zu benutzen um andere Knoten auf der gleichen Ebene zu finden, anstatt selbst derartige Hilfsfunktionen zu implementieren.

 

/************************************************************************************
             Visualisierung eines binären Suchbaumes in Processing
            mithilfe des multithreaded Reingold-Tilford-Algorithmus
                 und Suche des LCA über den RMQ-Algorithmus
                
                        - und Monitoring via JAMon -
                             von Thomas Kramer
                          Version 1.5 - 10.01.2012
 ************************************************************************************/


/* Konfiguration */
   int Baumelemente = 500000;
   /* wenn Zentrierung aktiviert wird, werden die Mausabfragen deaktiviert */
   boolean Zentrierung = true;
  
   /* RMQ-Abfragen einschalten? */
   boolean RMQ_Abfragen = false;
   /* für Laufzeittests kann es sinnvoll sein das Zeichnen generell zu unterdrücken */
   boolean zeichnen = false;
  
   /* Zufallszahlen-Unter-/Oberwert festlegen */
   int unten = 1;  
   int oben = 100000000;
     
   int AbstandOben = 50;
   int AbstandLinks = 10;
   int ZwischenAbstandOben = 25;
   int ZwischenAbstandLinks = 5;
   int Breite = 160;
   int Hoehe = 50;

   /* Farben festlegen (Schwarz, Weiss, Hintergrund-Farbe) */
   color c1 = color(0, 0, 0);
   color c2 = color(255, 255, 255);
   color c3 = color(193, 185, 185);
   color c4 = color(245, 7, 7);  
/* Konfiguration-Ende */

/* weitere globale Variablen */
int Ebene = 0;
int EbenenInsgesamt = 0;
tBaum Wurzel = null;
tBaum kleinster_Versatz = null;
tBaum groesster_Versatz = null;
tBaum letzter_Knoten = null;
tBaum[] RMQ_E       = new tBaum[(2*Baumelemente)-1];
int[]   RMQ_L       = new int  [(2*Baumelemente)-1];
int[]   RMQ_R       = new int  [Baumelemente];
HashSet<Integer> Zufallszahlen = new HashSet<Integer>();
ArrayList<tBaum> ZList = new ArrayList<tBaum>();
Hashtable<Integer, Pointer_Class> LevelTable = new Hashtable<Integer, Pointer_Class>();
Monitor mon1=null;
Monitor mon2=null;
Monitor mon3=null;
Monitor mon4=null;
Monitor mon5=null;
Monitor mon6=null;
Monitor mon7=null;
Monitor mon8=null;
Monitor mon9=null;
Monitor mon10=null;


/* Variablen für das Zeichnen */
int MaxElemente = 0;
int MaxElementePlatz = 0;
int Breite_2 = Breite / 2;
int Hoehe_2 = Hoehe / 2;
int GesamtVersatz = 0;
boolean ausgegeben = false;

import java.util.HashMap;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.TimeoutException;
import java.util.concurrent.Future;
import com.jamonapi.*;

public class tBaum
{
  /* in Inhalt wird der Zufallszahlen-Wert gespeichert */
  int Inhalt = 0;
  /* gibt die Ebene für jeden Knoten an */
  int Ebene = 0;
  /* Art gibt die Position des Knotens im Verhältnis zur Wurzel an
     -1 = linker Teilbaum, +1 = rechter Teilbaum */
 
  int Art = 0;
  int Versatz = 0;
 
  /* fürs Einreihen der Knoten brauche ich Zufallszahlen für zufällige
     Bäume, aber für den RMQ-Algorithmus ist das unpraktisch weil für das
     R-Array Knoteninhalt und Index vertauscht werden, daher Tagging-Variable */

  int tag = 0;
 
  /* Pointer für das Traversieren */
  tBaum Vater = null;
  tBaum links = null;
  tBaum rechts = null;
 
  /* speichert die jeweilige Tiefe des linken und des rechten Unterbaumes */ 
  Integer linksEbenen = 0;
  Integer rechtsEbenen = 0; 

  public int getTag()
  {
    return this.tag;
  }
};

/* Hilfsklasse für Levelorder-Traversierung */
/* jede Instanz beinhaltet alle Knoten einer Ebene */
public class Pointer_Class
{
  ArrayList<tBaum> Liste = new ArrayList<tBaum>();
   
  public void add(tBaum Knoten)
  {
    Liste.add(Knoten); 
  }
 
  public ArrayList<tBaum> getList()
  {
    return this.Liste;
  }
}

/* im linken Unterbaum muss das Maximum gefunden werden */
public class finde_linken_Versatz implements Callable
{
  tBaum Knoten = null;
  tBaum EndKnoten = null;
  Integer bisZuEbene = 0;
  Integer Versatz = 0;

  /* leerer Konstruktor */    
  public finde_linken_Versatz()
  {
  }
 
  public void setze_Daten(tBaum Knoten, Integer bisZuEbene, Integer Versatz)
  {
    this.Knoten = Knoten;
    this.EndKnoten = Knoten;   
    this.bisZuEbene = bisZuEbene;
    this.Versatz = Versatz;
  } 

  /* rekursive Methode */   
  private Integer finde_Versatz(tBaum Knoten, Integer Versatz)   
  {
    int result = Versatz;
 
    if (Knoten != null)
    {  
      result = max(Knoten.Versatz, result); 
      if (result == Knoten.Versatz)
      {
        EndKnoten = Knoten;
      }
 
      // noch nicht in der letzten zu berücksichtigenden Ebene?
      if (Knoten.Ebene < this.bisZuEbene)
      {
        result = finde_Versatz(Knoten.links, result);
        result = finde_Versatz(Knoten.rechts, result);
      }        
    }
     
    return result;
  }
   
  public Integer call()
  {
     return finde_Versatz(this.Knoten, this.Versatz);
  }
}

/* im rechten Unterbaum muss das Minimum gefunden werden */
public class finde_rechten_Versatz implements Callable
{
  tBaum Knoten = null;
  tBaum EndKnoten = null
  int bisZuEbene = 0;
  int Versatz = 0;
 
  /* leerer Konstruktor */
  public finde_rechten_Versatz()
  {
  }
 
  public void setze_Daten(tBaum Knoten, Integer bisZuEbene, Integer Versatz)
  {
    this.Knoten = Knoten;
    this.EndKnoten = Knoten;       
    this.bisZuEbene = bisZuEbene;
    this.Versatz = Versatz;
  } 
   
  /* rekursive Methode */
  private Integer finde_Versatz(tBaum Knoten, Integer Versatz)   
  {
    int result = Versatz;
 
    if (Knoten != null)
    {  
      result = min(Knoten.Versatz, result); 
      if (result == Knoten.Versatz)
      {
        EndKnoten = Knoten;
      }     
 
      // noch nicht in der letzten zu berücksichtigenden Ebene?
      if (Knoten.Ebene < this.bisZuEbene)
      {
        result = finde_Versatz(Knoten.links, result);
        result = finde_Versatz(Knoten.rechts, result);
      }        
    }
     
    return result;
  }
   
  public Integer call()
  {
     return finde_Versatz(this.Knoten, this.Versatz);
  }
}

void setup() {
  if (Baumelemente > abs(oben - unten))
    throw new IllegalArgumentException("Fehler! Es werden einmalige Zufallszahlen benötigt und die Anzahl Knoten ist größer als das Zufallszahlen-Intervall!");
   
  if ((Baumelemente * 1.2) > abs(oben - unten))
    println("Achtung, die Anzahl Baumknoten ist nicht mindestens 20% größer als das Zufallszahlen-Intervall, das kann die Geschwindigkeit deutlich herabsetzen!"); 

  /* Größe des Screens setzen */
  size(screen.width, screen.height);
 
  /* Bildschirm löschen */
  background(c3);
 
  /*-----------------------------------------------------------------------------
   *  einmalige Zufallszahlen erzeugen
   *-----------------------------------------------------------------------------*/
                   
  mon1=MonitorFactory.start("Zufallszahlen-Generierung");
 
  Zufallszahlen = new HashSet<Integer>();
  while (Zufallszahlen.size() < Baumelemente)
    Zufallszahlen.add((int) random(unten, oben));        
   
  mon1.stop();   
 
  /*-----------------------------------------------------------------------------
   *  Knoten erzeugen
   *-----------------------------------------------------------------------------*/
  
  mon2=MonitorFactory.start("Erzeugung der Knoten");                
 
  int i = 0;
  Iterator it = Zufallszahlen.iterator();
  ZList = new ArrayList<tBaum>();    
 
  while (it.hasNext())
  {   
    if (i == 0)
    {
      Wurzel = Einfuegen(null, null, (Integer) it.next(), 0, i);     
      /* Initialisierungswerte setzen */
      kleinster_Versatz=Wurzel;
      groesster_Versatz=Wurzel;                     
    }
    else {
      Einfuegen(Wurzel, null, (Integer) it.next(), 0, i);
      ZList.add(letzter_Knoten);
    }                       
   
    i++;
  }  
 
  mon2.stop();
     
  /*-----------------------------------------------------------------------------
   *  Versatz berechnen
   *-----------------------------------------------------------------------------*/

  mon3=MonitorFactory.start("Versatz-Berechnung - LevelOrder-Traversierung insgesamt");
 
  LevelOrder();
 
  mon3.stop();
 
  /* kleinsten Versatz im Baum allen Knoten aufaddieren, danach hat man
     die konkrete Spaltenzahl (x-Koordinate) für jeden Knoten - beginnend mit 1 */

  GesamtVersatz=abs((kleinster_Versatz).Versatz)+1;   
 
  /* das Aufaddieren geschieht jetzt direkt in der Zeichnen-Routine,
     dadurch wird aber ein Teil des RT-Algorithmus nicht mehr mitgemessen! */

  // setze_Wert(Wurzel, GesamtVersatz);     
 
  /*-----------------------------------------------------------------------------
   *  Variablen für das Zeichnen einmalig setzen
   *-----------------------------------------------------------------------------*/
       
  MaxElemente = (groesster_Versatz).Versatz + GesamtVersatz;
  MaxElementePlatz = (MaxElemente * Breite)+((MaxElemente - 1) * ZwischenAbstandLinks);       
 
  /*-----------------------------------------------------------------------------
   *  Euler-Tour-Arrays erstellen
   *-----------------------------------------------------------------------------*/
   
  if (RMQ_Abfragen)
  {
    /* Startzeit nehmen */
    mon4=MonitorFactory.start("Euler-Tour");  
   
    Euler_Tour(Wurzel,-1);
   
    mon4.stop();
    mon5=MonitorFactory.start("RMQ-Arrays erstellen");
   
    fillRMQ_R_Array();
   
    mon5.stop(); 
 
    /*-----------------------------------------------------------------------------
     *  Debug-Ausgabe der RMQ-Arrays
     *-----------------------------------------------------------------------------*/
           
    /*
     String DebugString1;
     String DebugString2;
     String DebugString3;  
     String DebugString4;     
     DebugString1="Index  ";  
     DebugString2="RMQ_E: ";
     DebugString3="RMQ_L: ";  
     DebugString4="RMQ_R: ";     
     for (int r=0; r<(Baumelemente*2-1); r+=1)
     {
       DebugString1+=r + ", ";
       DebugString2+=RMQ_E[r].tag + ", ";
       DebugString3+=RMQ_L[r] + ", ";    
     }
     for (int r=0; r<Baumelemente; r+=1)
       DebugString4+=RMQ_R[r] + ", ";

     println(DebugString1);  
     println(DebugString2);
     println(DebugString3);  
     println(DebugString4);       
    */

    
    /*-----------------------------------------------------------------------------
     *  RMQ-Abfragen beantworten
     *-----------------------------------------------------------------------------*/

    /* Zuerst Liste mit Knoten shufflen */
    Collections.shuffle(ZList);
 
    /* Startzeit nehmen  */
    mon6=MonitorFactory.start("RMQ-Abfragen beantworten");
 
    int tag1 = 0;
    int tag2 = 0;
    int result = 0;
    i = 0;
    /* Wurzelknoten wurde ja nicht einbezogen, also Obergrenze = Anzahl -2 */
    int x = Baumelemente -2;
    /* soviele Abfragen beantworten wie Knoten-1 da sind */
    while (x >= 0)
    {
        tag1 = ZList.get(i).tag;
        tag2 = ZList.get(x).tag;
     
        /* bei Performance-Tests wollen wir die Zeit für die Bildschirmausgabe nicht mittesten */     
        /* println("LCA von " + tag1 + " und " + tag2 + " = " + LCA(tag1, tag2).tag); */     
         result = LCA(tag1, tag2).tag; 
     
        i++;
        x--;      
    } 
      
    /* Endzeit nehmen und Ausgabe */
    mon6.stop();
  }
 
  /*-----------------------------------------------------------------------------
   *  Maus auf Mittelposition setzen (innerhalb des Fensters)
   *-----------------------------------------------------------------------------*/

  mouseX=(screen.width/2);
  mouseY=(screen.height/2);
   
  /*-----------------------------------------------------------------------------
   *  erneute Aufrufe des Events draw() verhindern
   *-----------------------------------------------------------------------------*/

  if (Zentrierung)
  {
    noLoop();    
    ausgabeZeit();
  }
}

void draw()
{
  /*-----------------------------------------------------------------------------
   *  Hintergrundfarbe setzen, dabei wird auch der gesamte Bildschirm gelöscht
   *-----------------------------------------------------------------------------*/

  background(c3); 

  /*-----------------------------------------------------------------------------
   *  Überschriften setzen
   *-----------------------------------------------------------------------------*/

  fill(c2);
  textSize(20);
  text("Visualisierung eines binären Suchbaumes (Reingold-Tilford-Algorithmus) in Processing", ((screen.width)/2)-400, 50);
  textSize(15);
  text("von Thomas Kramer", ((screen.width)/2)-70, 80);
  text("(ESC zum Abbrechen)", ((screen.width)/2)-75, 110);
  textSize(13);
 
  /*-----------------------------------------------------------------------------
   *  Baum grafisch ausgeben
   *-----------------------------------------------------------------------------*/

  if (zeichnen)
  {
    /* Startzeit nehmen */   
    mon7=MonitorFactory.start("Zeichnen des Graphen");
   
    ZeigeBaum(Wurzel, 0, 0);
    ausgegeben = true;
   
    /* Endzeit nehmen und Ausgabe */
    mon7.stop();
  }
    
  /*-----------------------------------------------------------------------------
   *  RMQ-Abfragen beantworten und einzeichnen
   *-----------------------------------------------------------------------------*/
         
  if (RMQ_Abfragen)
  {
    text("Ermittlung des Lowest Common Ancestors anhand der Tags und des RMQ-Algorithmus", ((screen.width)/2)-240, (screen.height)-170);     
    text("LCA(7,8) = " + LCA(7,8).tag, ((screen.width)/2)-20, (screen.height)-150);  
    text("LCA(4,6) = " + LCA(4,6).tag, ((screen.width)/2)-20, (screen.height)-130);  
    text("LCA(3,4) = " + LCA(3,4).tag, ((screen.width)/2)-20, (screen.height)-110);  
    text("LCA(5,8) = " + LCA(5,8).tag, ((screen.width)/2)-20, (screen.height)-90);  
    text("LCA(7,9) = " + LCA(7,9).tag, ((screen.width)/2)-20, (screen.height)-70);      
  }

  /*-----------------------------------------------------------------------------
   *  aktuelle Mauskoordinaten ausgeben
   *-----------------------------------------------------------------------------*/

  if (!Zentrierung)
  {
    fill(c3);
    rect(1, 0, 80, 60);
    fill(c2);
    text("x: " + mouseX, 20, 20);
    text("y: " + mouseY, 20, 40);
  }
}

/* addiere den nach der Formel korrigierten Versatz jedem einzelnen
   Knoten der angegebenen Kontur auf */

void setze_Wert(tBaum Knoten, int Wert)
{
  if (Knoten!=null)
  {
    Knoten.Versatz += Wert;
 
    setze_Wert(Knoten.links,Wert);
    setze_Wert(Knoten.rechts,Wert);  
  }
}

/* Einfügen der Knoten, Position wird in der Routine selbst bestimmt */
tBaum Einfuegen(tBaum Knoten, tBaum Vater, int Inhalt, int Versatz, int tag)
{
  Pointer_Class KnotenMengeProEbene = null;  
 
  if (Knoten == null)
  {
    /* angegebener Knoten existiert noch nicht (Position noch nicht belegt)
       --> neuen Knoten erzeugen */

  
    Knoten = new tBaum();
    Knoten.Vater = Vater;
    Knoten.links = null;
    Knoten.rechts = null;
    Knoten.Inhalt = Inhalt;
    Knoten.Ebene = Ebene+1;
    Knoten.tag = tag;
    /* Versatz mit Initialisierungswerten versehen */
    Knoten.Versatz = Versatz;
    EbenenInsgesamt = max(EbenenInsgesamt, Knoten.Ebene);
  
    /* Position im Baum abhängig zur Wurzel bestimmen */
    Knoten.Art=0;  
    if (Wurzel != null)
    {
      Knoten.Art = (Inhalt < Wurzel.Inhalt) ? -1 : +1;                                   
     
      /* kleinsten/größten Versatz bestimmen */
      if (Knoten.Versatz < (kleinster_Versatz).Versatz)
        kleinster_Versatz = Knoten;
      if (Knoten.Versatz > (groesster_Versatz).Versatz)
        groesster_Versatz = Knoten;          
    }
   
    /* nimm alle Knoten von der aktuellen Ebene aus dem Hashtable */
    KnotenMengeProEbene = LevelTable.get(Knoten.Ebene);
    /* wenn noch nicht gespeichert neu instanziieren */
    if (KnotenMengeProEbene == null)
      KnotenMengeProEbene = new Pointer_Class();
    /* füge dieser Menge den aktuellen Knoten hinzu */
    KnotenMengeProEbene.add(Knoten); 
    /* speichere diese Menge wieder in dem Hashtable */ 
    LevelTable.put(Knoten.Ebene, KnotenMengeProEbene);   
     
    letzter_Knoten = Knoten;
  } else
  {
    Ebene += 1;
    if (Inhalt < Knoten.Inhalt)
    { /* kleineren Wert als den des aktuellen Knotens immer als linken Sohn einfügen */
      Knoten.links = Einfuegen(Knoten.links, Knoten, Inhalt, Versatz-1, tag);              
      Knoten.linksEbenen = max(Knoten.linksEbenen, letzter_Knoten.Ebene);                    
    }    
    else if (Inhalt > Knoten.Inhalt)
    { /* größeren Wert als den des aktuellen Knotens immer als rechten Sohn einfügen */
      Knoten.rechts = Einfuegen(Knoten.rechts, Knoten, Inhalt, Versatz+1, tag);     
      Knoten.rechtsEbenen = max(Knoten.rechtsEbenen, letzter_Knoten.Ebene);             
    }
    Ebene -= 1;
  }
 
  return Knoten;
}

/* Baum visuell ausgeben */
void ZeigeBaum(tBaum Knoten, int StartPosKanteLinks, int StartPosKanteOben)
{
  if (Knoten == null)   
    return;        
   
  if (!ausgegeben)
  {
    Knoten.Versatz += GesamtVersatz;
  }

  int GesamtPositionLinks = 0;
  int GesamtPositionLinks_2 = 0;
  int GesamtPositionOben = 0; 
  int GesamtPositionOben_2 = 0;
  int Zentri_Space = 0;
  int BenutzteFelder = (Knoten.Versatz - 1) * (Breite + ZwischenAbstandLinks);
  boolean Fehler = false
 
  if (Zentrierung)
  {
    Zentri_Space = (screen.width - AbstandLinks - MaxElementePlatz) / 2;
    GesamtPositionLinks = Zentri_Space + AbstandLinks + BenutzteFelder;  
    GesamtPositionOben=AbstandOben + (Knoten.Ebene * Hoehe) + (Knoten.Ebene * ZwischenAbstandOben);
  }
  else {
    GesamtPositionLinks=((screen.width / 2) - mouseX) - AbstandLinks + BenutzteFelder;
    GesamtPositionOben=((screen.height / 2) - mouseY) - AbstandOben + (Knoten.Ebene * Hoehe) + (Knoten.Ebene * ZwischenAbstandOben);
  }
  GesamtPositionLinks_2 = GesamtPositionLinks + Breite_2;
  GesamtPositionOben_2 = GesamtPositionOben + Hoehe_2;
 
  /* Erkennen, ob schon ein Knoten an die Stelle gezeichnet wurde */
  color cp = get(GesamtPositionLinks + 1, GesamtPositionOben + 1);
  if (cp == c2)
  {
    println("Fehler! Es wurde schon ein Knoten an diese Stelle gezeichnet!");
    println("betreffend Knoten: " + Knoten.Inhalt);
   
    Fehler = true;
  } 

  /* Rahmen zeichnen */
  if (Fehler)
    fill(c4);
  else
    fill(c2); 
  rect(GesamtPositionLinks,
  GesamtPositionOben,
  Breite,
  Hoehe);

  /* Inhalte einzeichnen */
  fill(c1);          
  text(Knoten.Ebene+". Ebene=" +Knoten.Inhalt + ", tag " + Knoten.tag,
  GesamtPositionLinks + 5,
  GesamtPositionOben + 15);
  line(GesamtPositionLinks,
  GesamtPositionOben_2,
  GesamtPositionLinks + Breite,
  GesamtPositionOben_2);
  line(GesamtPositionLinks_2,
  GesamtPositionOben_2,
  GesamtPositionLinks_2,
  GesamtPositionOben + Hoehe);      
  if (Knoten.links != null)
    text((Knoten.links).Inhalt,
    GesamtPositionLinks + 5,
    GesamtPositionOben_2 + 15);             
  if (Knoten.rechts!=null)
    text((Knoten.rechts).Inhalt,
    GesamtPositionLinks_2 + 5,
    GesamtPositionOben_2 + 15);                  
  if (Knoten.Ebene != 1)
    line(StartPosKanteLinks, StartPosKanteOben, GesamtPositionLinks_2, GesamtPositionOben);  

  /* Rekursionsaufrufe */
  if (Knoten.links != null)
    ZeigeBaum(Knoten.links, GesamtPositionLinks_2, GesamtPositionOben + Hoehe);
  if (Knoten.rechts != null)
    ZeigeBaum(Knoten.rechts, GesamtPositionLinks_2, GesamtPositionOben + Hoehe);             
}

/* Startwert sollte bei -1 liegen */
int Euler_Tour(tBaum Knoten, int Zaehler)
{
  if (Knoten!=null)
  {
    Zaehler+=1;
    RMQ_E[Zaehler]=Knoten;
    RMQ_L[Zaehler]=Knoten.Ebene-1; 
   
    if (Knoten.links!=null)
    {
      Zaehler=Euler_Tour(Knoten.links, Zaehler)+1;
      RMQ_E[Zaehler]=Knoten;
      RMQ_L[Zaehler]=Knoten.Ebene-1;     
    }

    if (Knoten.rechts!=null)
    {
      Zaehler=Euler_Tour(Knoten.rechts, Zaehler)+1;
      RMQ_E[Zaehler]=Knoten;
      RMQ_L[Zaehler]=Knoten.Ebene-1;     
    }
  }
 
  return Zaehler;
}

/* fülle Repräsentanten-Array, welche das erste Vorkommen jedes Knotens enthält */
void fillRMQ_R_Array()
{
  /* RMQ_R füllen. Dazu alle Knoten durchgehen... */
  int s=0;
  for (int r=0; r<Baumelemente; r+=1)
  {   
    /* ... und für jeden Knoten den ersten Eintrag im RMQ_E-Array finden ... */
    for (s=0; s<(Baumelemente*2-1); s+=1)
    {
      if (RMQ_E[s].tag == r)
        break;       
    }
    RMQ_R[r]=s;      
  }
}

/* mittels RMQ-Algorithmus den Lowest Common Ancestor ermitteln */
tBaum LCA(int tag1, int tag2)
{
  /* Suche im RMQ_R-Array zunächst die Entsprechung für tag1 und tag2 der beiden
     ausgewählten Knoten aus, suche dann innerhalb dieser Grenzen im RMQ_L-Array
     den niedrigsten Wert heraus.
    
     Anschließend wird im RMQ_E-Array der Wert aus dieser Indexposition zurückgegeben */

    
  int lowest=Baumelemente;
  int lowest_index=0;
  tBaum result=null;
 
  for (int i=min(RMQ_R[tag1], RMQ_R[tag2]); i<=max(RMQ_R[tag1], RMQ_R[tag2]); i+=1)
  {
    if (RMQ_L[i]<lowest)
    {
      lowest=RMQ_L[i];
      lowest_index=i;
    }
  }
 
  /* Default-Rückgabewert setzen gemäß Algorithmus */
  result = RMQ_E[lowest_index];    
  /* wenn Knoten B ein Sohn von A ist wird A gemäß Algorithmus zurückgeliefert,
     dann greift Ausnahmeregelung */
   
  if ((RMQ_E[lowest_index].tag == tag1) || (RMQ_E[lowest_index].tag == tag2))
    if (RMQ_E[lowest_index].Vater != null )
       result = RMQ_E[lowest_index].Vater;
 
  return result;
}

/* starte Levelorder-Traversierung */
void LevelOrder()

  ExecutorService executor = Executors.newCachedThreadPool();
  Pointer_Class KnotenMengeProEbene = null;    
  ArrayList KnotenMengeProEbene2 = null;
  tBaum Knoten[] = null;   
  finde_linken_Versatz a[] = null;
  finde_rechten_Versatz b[] = null;
  int minLevelinsgesamt = 0; 
  Future erg1[] = null;
  Future erg2[] = null;
  int Versatz = 0;
  Integer linke_Kontur = 0;
  Integer rechte_Kontur = 0;
 
  int i = 0;
  int x = 0; 
 
  i = EbenenInsgesamt -1;
  while (i >= 1)
  {
    /* nimm alle Knoten von der aktuellen Ebene aus dem Hashtable */
    KnotenMengeProEbene = LevelTable.get(i);
    KnotenMengeProEbene2 = KnotenMengeProEbene.getList();
   
    x = 0;
    Knoten = new tBaum[KnotenMengeProEbene2.size()];
    a = new finde_linken_Versatz[KnotenMengeProEbene2.size()];
    b = new finde_rechten_Versatz[KnotenMengeProEbene2.size()];
    erg1 = new Future[KnotenMengeProEbene2.size()];
    erg2 = new Future[KnotenMengeProEbene2.size()];    
    while (x < KnotenMengeProEbene2.size())
    {      
      Knoten[x] = (tBaum) KnotenMengeProEbene2.get(x);
      minLevelinsgesamt=min(Knoten[x].linksEbenen, Knoten[x].rechtsEbenen);                  
     
      /* bestimme den maximalen und minimalen Versatz jeder Kontur bis zu der bestimmten Ebene (einschließlich) */   
      /* starte dazu soviele Threads wie Knoten in der Ebene vorhanden sind */
      /* das gilt aber nur für jeden Knoten, der beide Söhne hat */
      if ((Knoten[x].links != null) && (Knoten[x].rechts != null))
      {
        a[x] = new finde_linken_Versatz();
        mon8=MonitorFactory.start("Multithreading - finde max im linken Unterbaum");
        a[x].setze_Daten(Knoten[x].links, minLevelinsgesamt, (Knoten[x].links).Versatz);
        erg1[x] = executor.submit(a[x]);
       
        b[x] = new finde_rechten_Versatz();       
        mon9=MonitorFactory.start("Multithreading - finde min im rechten Unterbaum");
        b[x].setze_Daten(Knoten[x].rechts, minLevelinsgesamt, (Knoten[x].rechts).Versatz);
        erg2[x] = executor.submit(b[x]);    
      }
     
      x++;
    }
   
    /* warte auf das Ergebnis der Threads, indem die Ergebnisse ausgelesen werden */
    try       
    {    
      x = 0;     
      while (x < KnotenMengeProEbene2.size())         
      {
        if ((Knoten[x].links != null) && (Knoten[x].rechts != null))
        {
          linke_Kontur = (Integer) erg1[x].get();
          mon8.stop();
          rechte_Kontur = (Integer) erg2[x].get();
          mon9.stop();
         
          /* Korrigierungs-Versatz berechnen */
          Versatz=(linke_Kontur - rechte_Kontur) +2;  
          /* Ergebnis ist ungerade? */
          if ((Versatz & 1) != 0)
            Versatz += 1;
          /* Integer-Division */
          Versatz=(Versatz / 2);   
  
          /* diesen Versatz dem linken Teilbaum als negativen Wert aufaddieren, dem rechten Teilbaum
             als positiven Wert */

          mon10=MonitorFactory.start("Versatz-Korrektur");
          setze_Wert(Knoten[x].links,Versatz * -1);
          setze_Wert(Knoten[x].rechts,Versatz);          
          mon10.stop();
        }
       
        x++;
      }    
    }
    catch (ExecutionException ex)
    {}
    catch (InterruptedException ex)
    {}             
              
    i--;
  } 
 
  executor.shutdown();
}

/* Zeitmessung ausgeben */
void ausgabeZeit()
{
  if (mon1 != null)
    println(mon1 + "\n");
  if (mon2 != null)   
    println(mon2 + "\n");
  if (mon3 != null)   
    println(mon3 + "\n");
  if (mon4 != null)   
    println(mon4 + "\n");
  if (mon5 != null)   
    println(mon5 + "\n");
  if (mon6 != null)   
    println(mon6 + "\n");
  if (mon7 != null)   
    println(mon7 + "\n");
  if (mon8 != null)   
    println(mon8 + "\n");
  if (mon9 != null)   
    println(mon9 + "\n");
  if (mon10 != null)   
    println(mon10 + "\n"); 
}

 

Tag-Wolke

Monats-Liste