Thomas Kramer

IT-COW | All posts tagged 'binare-Suchbaume'

Eine andere Variante meines RMQ-Algorithmus

By Administrator at August 22, 2012 21:05
Filed Under: Algorithmen, Java, Projekte

Ich habe außerdem getestet ob noch eine andere bestimmte Algorithmus-Variante schneller ist gegenüber meiner vorherigen Version.

 

Im RMQ_L-Array (Integer) wird die Ebene (Level) jedes Knotens separat gespeichert. Wenn man sich dieses Array genauer anschaut bemerkt man dass sich die jeweilige Ebene im Vergleich zum Vorgänger-Knoten (Euler Tour-Reihenfolge) immer um +1 oder –1 unterscheidet.

 

Entsprechend kann man sich sparen den absoluten Wert der Ebene für jeden Knoten einzeln zu speichern und berücksichtigt z. B. nur eine Steigerung oder Senkung gegenüber dem Vorgänger-Knoten. Ich habe infolge dieser Überlegung das RMQ_L-Array in eines vom Typ Boolean umgewandelt. Als direkte Schlussfolgerung ergibt sich damit bereits ein verringerter RAM-Bedarf, der aber marginal ist.

 

Wenn man dann die RMQ-Abfrage auf das RMQ_L-Array macht merkt man sich zuerst die Startebene vom Startknoten und zählt im weiteren Verlauf der Schleife die +1 und –1-Veränderungen in zwei separaten Integer-Variablen. Dann nimmt man (Startebene + Increments – Decrements) und hat auf diese Weise die Ebene des aktuellen Knotens, diesen Wert nimmt man dann für die Minimum-Bestimmung.

 

Ich habe zwei verschiedene Varianten davon umgesetzt und jeweils die Geschwindigkeit gemessen, Variante 2 benutzt vierfaches Loop-Unrolling und Variante 1 kommt ohne aus. Die Testergebnisse auf meinem Turion 64x2-Notebook waren bei 100.000 Knoten und 100.000 RMQ-Abfragen:

 

Variante 1: 01:28 Minuten

Variante 2: 03:25 Minuten

 

Die vorherige Variante meines RMQ-Algorithmus kam auf dem gleichen Rechner unter denselben Testbedingungen mit nur 22-24 Sekunden aus. Damit sind beide Varianten langsamer als zuvor - ich führe das im Wesentlichen darauf zurück dass ein heutiger 32/64-Bit-Rechner 32-Bit-Integers in nur einem Rechenschritt verarbeiten kann und Byte-Arrays sich damit nur noch in Bezug auf Speicherverbrauch, aber nicht mehr bei der Rechenzeit auswirken. Dazu kommt noch dass sich aufgrund der Vorgehensweise die Anzahl Rechenoperationen erhöht, was sich offenbar stärker auswirkt.

 

Interessant ist außerdem dass die Loop-Unrolling-Variante (2) hier sogar langsamer ist als die Version ohne (1). Das wird bei Variante 2 an der erhöhten Anzahl Objekt-Zugriffe auf das RMQ_E-Array liegen; durch ein Integer-Array lässt sich ohne den ganzen Objekt-Kontext einfach schneller iterieren.

 

Wenn man bei Variante 1 die drei Rechenbefehle increments++, decrements++ und temp=…. in der Schleife weglässt verringert sich die Laufzeit wieder auf ca. 33 Sekunden und damit kommen wir wieder in die Laufzeiten der Version des vorherigen Blog-Eintrags. Rechenoperationen sind nunmal langsamer als Vergleiche. Damit erübrigt sich aber auch eine weitere Variante, die ich eigentlich noch geplant hatte.

 

Damit sind beide Varianten langsamer als die Version des vorherigen Blog-Eintrags, aber interessant war die Umsetzung schon. Beide Varianten sind im Quellcode unten in der LCA-Routine, Variante 1 ohne Loop-Unrolling ist derzeit ausgeklammert.

 

Übrigens fällt mir noch eine weitere Optimierungs-Möglichkeit ein, man könnte die Min-/Max-Suche über das Array rekursiv statt iterativ lösen, ich finde die iterative Variante aber eingängiger und glaube auch nicht dass das einen wesentlichen Unterschied macht.

 

Noch eine Randbemerkung - im Vergleich zur vorherigen Variante des vorherigen Blog-Eintrags habe ich noch weitere Veränderungen vorgenommen, die aber bei Tests keinerlei Performance-Einfluss (zumindest bei 100.000 Knoten/RMQ-Abfragen) zeigten:

 

Dazu gehörte 1. den Garbage-Collector von Java vor Zeitmessungen gezielt aufzurufen, um reproduzierbare Performance-Werte zu erhalten. Als 2. habe ich die Arraylist ZList durch das Array shuffledList ersetzt, weil indexbasierter Zugriff auf Arrays einen Tacken schneller sein soll als bei Arraylisten. Und als 3. habe ich die zwei Min/Max-Befehle in der LCA-Routine wieder durch eine If – Abfrage ersetzt weil die zwei Werte miteinander korrespondieren und ich ohne einen Vergleich einsparen kann (dank Else-Zweig, wenn der eine Wert größer ist als der andere wurde gleichzeitig auch der Kleinere bestimmt).

 

/************************************************************************************
             Visualisierung eines binären Suchbaumes in Processing
                 mithilfe des Reingold-Tilford-Algorithmus
                 und Suche des LCA über den RMQ-Algorithmus
                             von Thomas Kramer
                          Version 2.20 - 22.08.2012
************************************************************************************/

/* Konfiguration */
   int Baumelemente = 100000;
   /* wenn Zentrierung aktiviert wird, werden die Mausabfragen deaktiviert */
   boolean Zentrierung = true;
   /* RMQ-Abfragen einschalten? */
   boolean RMQ_Praeprocessing = true;
   boolean RMQ_Abfragen = true;
   /* Debugging-Ausgabe */
   boolean debug = 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 = 10000000;
   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 */

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;
  }
  public int getEbene()
  {
    return this.Ebene - 1;    
  }
};

/* 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];
boolean[]   RMQ_L       = new boolean[(2*Baumelemente)-1];
int    []   RMQ_R       = new int[Baumelemente];
Hashtable<Integer, Integer> elementsProcessed = new Hashtable<Integer, Integer>();
HashSet<Integer> Zufallszahlen = new HashSet<Integer>();
tBaum[] shuffledList = new tBaum[Baumelemente-1];
long completeTimeBefore = 0;
long completeTimeAfter  = 0;
long completeTimeDiff = 0;

/* 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;

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);
  /* Garbage Collector gezielt aufrufen dammit es nicht automatisch während der Zeitmessungen geschieht */
  System.gc();
  /*-----------------------------------------------------------------------------
   *  einmalige Zufallszahlen erzeugen
   *-----------------------------------------------------------------------------*/
                   
  Zufallszahlen = new HashSet<Integer>();
  while (Zufallszahlen.size() < Baumelemente)
    Zufallszahlen.add((int) random(unten, oben));        
  /*-----------------------------------------------------------------------------
   *  Startzeit messen für RT-Algorithmus
   *-----------------------------------------------------------------------------*/
   
  completeTimeBefore = System.currentTimeMillis();                     
  /*-----------------------------------------------------------------------------
   *  Knoten erzeugen
   *-----------------------------------------------------------------------------*/
  
  int i = 0;
  Iterator<Integer> it = Zufallszahlen.iterator();
  shuffledList = new tBaum[Baumelemente-1];
  while (it.hasNext())
  {   
    if (i == 0)
    {
      Wurzel = Einfuegen(null, null, it.next(), 0, i);     
      /* Initialisierungswerte setzen */
      kleinster_Versatz = Wurzel;
      groesster_Versatz = Wurzel;                     
    }
    else {
      Einfuegen(Wurzel, null, it.next(), 0, i);
      shuffledList[i-1] = letzter_Knoten;
    }                       
    i++;
  }  
  /*-----------------------------------------------------------------------------
   *  Versatz berechnen
   *-----------------------------------------------------------------------------*/

  berechne_Versatz(Wurzel);
  /* 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);   
  /*-----------------------------------------------------------------------------
   *  Endzeit messen für RT-Algorithmus
   *-----------------------------------------------------------------------------*/  
  nimmZeit("RT-Algorithmus");
  /*-----------------------------------------------------------------------------
   *  Variablen für das Zeichnen einmalig setzen
   *-----------------------------------------------------------------------------*/       
  MaxElemente = (groesster_Versatz).Versatz + GesamtVersatz;
  MaxElementePlatz = (MaxElemente * Breite)+((MaxElemente - 1) * ZwischenAbstandLinks);       
  /*-----------------------------------------------------------------------------
   *  Euler-Tour-Arrays erstellen
   *-----------------------------------------------------------------------------*/   
  if (RMQ_Praeprocessing)
  {
    /* Startzeit nehmen */
    completeTimeBefore = System.currentTimeMillis();                          
    elementsProcessed.clear();
    Euler_Tour(Wurzel, -1, -1);
    fillRMQ_R_Array();
    /* Endzeit nehmen und Ausgabe */
    nimmZeit("Erstellung der RMQ-Arrays"); 
    /*-----------------------------------------------------------------------------
     *  Debug-Ausgabe der RMQ-Arrays
     *-----------------------------------------------------------------------------*/           
     if (debug)
     {   
       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
     *-----------------------------------------------------------------------------*/

    if (RMQ_Abfragen)
    {
      /* Zuerst Liste mit Knoten shufflen */
      Collections.shuffle(Arrays.asList(shuffledList));
      /* Startzeit nehmen  */
      completeTimeBefore = System.currentTimeMillis();       
      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 = shuffledList[i].tag;
        tag2 = shuffledList[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 */
      nimmZeit("RMQ-Abfragen");
    }
  }
  /*-----------------------------------------------------------------------------
   *  Maus auf Mittelposition setzen (innerhalb des Fensters)
   *-----------------------------------------------------------------------------*/

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

  if (Zentrierung)
    noLoop();    
}

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 */   
    completeTimeBefore = System.currentTimeMillis();         
    ZeigeBaum(Wurzel, 0, 0);
    ausgegeben = true;
    /* Endzeit nehmen und Ausgabe */
    nimmZeit("Baumzeichnen");
  }
  /*-----------------------------------------------------------------------------
   *  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);
  }
}

void berechne_Versatz(tBaum Knoten)
{
  /* PostOrder-Druchlauf -> linker Teilbaum, rechter Teilbaum, Wurzel */
  if (Knoten!=null)
  {
    berechne_Versatz(Knoten.links);                 
    berechne_Versatz(Knoten.rechts);     
    berechne_Konturen(Knoten);   
  }
}

void berechne_Konturen(tBaum Knoten)
{
   /* berechne Konturen, nur notwendig wenn aktueller Knoten zwei Söhne hat */
  if (Knoten.links!=null && Knoten.rechts!=null)
  {
    int linke_Kontur=0;
    int rechte_Kontur=0;
    /* finde die maximalen Ebenen für die Unterbäume links und rechts, separat */
    /* übernimm davon den niedrigeren Wert */
    int minLevelinsgesamt=min(Knoten.linksEbenen, Knoten.rechtsEbenen);     
    /* bestimme den maximalen und minimalen Versatz jeder Kontur bis zu der bestimmten Ebene (einschließlich) */
    linke_Kontur  = finde_Versatz(Knoten.links, +1, minLevelinsgesamt, (Knoten.links).Versatz);   
    rechte_Kontur = finde_Versatz(Knoten.rechts, -1, minLevelinsgesamt, (Knoten.rechts).Versatz);  
    /* Korrigierungs-Versatz berechnen */
    int Versatz=((linke_Kontur-rechte_Kontur))+2;  
    /* Ergebnis ist ungerade? */
    if ((Versatz & 1)!=0)
      Versatz+=1;
    /* Integer-Division */
    Versatz=(Versatz>>1);
    /* Test-Ausgabe */
    if (Versatz <0)
      println("abs()-Funktion sollte doch verwendet werden!");
    /* diesen Versatz dem linken Teilbaum als negativen Wert aufaddieren, dem rechten Teilbaum
       als positiven Wert */

    setze_Wert(Knoten.links,-Versatz);
    setze_Wert(Knoten.rechts,Versatz);
  }
}

/* berechne die Tiefe der jeweiligen Kontur des Knotens */
int finde_Max_Ebene(tBaum Knoten)
{
  if (Knoten == null)
    return 0;
  return max(finde_Max_Ebene(Knoten.links), finde_Max_Ebene(Knoten.rechts)) + 1;
}

/* finde den minimalen/maximalen Versatz für den jeweilig angegebenen
   Unterbaum (Kontur) heraus - bis zu einer bestimmten Ebene (einschließlich) */

int finde_Versatz(tBaum Knoten, int Richtung, int biszuEbene, int Versatz)
{
  int result=Versatz;
  if (Knoten!=null)
  {  
    /* Richtung: -1=suche Minimum, +1=suche Maximum */
    if (Richtung==-1)
    {
      result=min(Knoten.Versatz,result);
    } else
    {
      result=max(Knoten.Versatz,result);
    }  
    /* noch nicht in der letzten zu berücksichtigenden Ebene? */
    if (Knoten.Ebene<biszuEbene)
    {
      result=finde_Versatz(Knoten.links, Richtung, biszuEbene, result);
      result=finde_Versatz(Knoten.rechts, Richtung, biszuEbene, result);
    }  
  }
  return result;
}

/* 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)
{
  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;
    if ((Ebene + 1) > EbenenInsgesamt)
      EbenenInsgesamt = (Ebene + 1);
    /* 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;          
    }
    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, int vorgaengerEbene)
{
  if (Knoten!=null)
  {
    Zaehler += 1;
    RMQ_E[Zaehler] = Knoten;
    // separate Wurzel-Abfrage unnötig, es wird bei der RMQ-Abfrage exklusive des Start-Knotens berechnet
    if (RMQ_E[Zaehler].getEbene() > vorgaengerEbene)
    {
      // Steigerung
      RMQ_L[Zaehler] = true;
    } else {
      // Senkung
      RMQ_L[Zaehler] = false;     
    }
    elementsProcessed.put(Knoten.tag, Zaehler); 
    if (Knoten.links!=null)
    {
      Zaehler=Euler_Tour(Knoten.links, Zaehler, Knoten.getEbene())+1;
      RMQ_E[Zaehler]=Knoten;
      vorgaengerEbene = (Knoten.links).getEbene();     
      if (RMQ_E[Zaehler].getEbene() > vorgaengerEbene)
      {
        // Steigerung
        RMQ_L[Zaehler] = true;
      } else {
        // Senkung
        RMQ_L[Zaehler] = false;             
      }     
    }

    if (Knoten.rechts!=null)
    {
      Zaehler=Euler_Tour(Knoten.rechts, Zaehler, Knoten.getEbene())+1;     
      RMQ_E[Zaehler]=Knoten;
      vorgaengerEbene = (Knoten.rechts).getEbene();
      if (RMQ_E[Zaehler].getEbene() > vorgaengerEbene)
      {
        // Steigerung
        RMQ_L[Zaehler] = true;
      } else {
        // Senkung
        RMQ_L[Zaehler] = false;     
      }     
    }   
  }
  return Zaehler;
}

/* fülle Repräsentanten-Array, welche das erste Vorkommen jedes Knotens enthält */
void fillRMQ_R_Array()
{
  for (int r = 0; r < Baumelemente; r += 1)
  {
    RMQ_R[r] = elementsProcessed.get(r);
  }
}

/* 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 */

  tBaum result=null;          
  int start;
  int ende;
  if (RMQ_R[tag1] < RMQ_R[tag2])
  {
    start = RMQ_R[tag1];
    ende = RMQ_R[tag2];   
  } else {
    start = RMQ_R[tag2];
    ende = RMQ_R[tag1];   
  } 
  int StartEbene = 0;
  int increments = 0;
  int decrements = 0; 
  int aktueller_Durchlauf = start;
  int temp = 0; 

/* 
  // Variante 1, benötigt 1 Minuten 28 bei 100.000 RMQ-Abfragen
  StartEbene = RMQ_E[start].getEbene();   
  int lowest = StartEbene;
  int lowest_index = start;
  // wenn jetzt bereits Startwert > Endwert wird die Schleife nicht mehr ausgeführt
  for (int i = start + 1; i <= ende; i += 1)
  {
      if (RMQ_L[i])
      {
        increments++;
      } else {
        decrements++;
      }
      temp = (StartEbene + increments - decrements);
      if (temp < lowest)
      {
        lowest = temp;
        lowest_index = i;
      }                       
  }
*/

  // Variante 2
  // 3 Minuten 25 bei 100.000 RMQ-Abfragen
  int lowest=Baumelemente;
  int lowest_index = 0;
  int rest = (ende - start + 1) & 3;
  int endSchleife = ende - rest + 1; 
  for (int i = start; i <= endSchleife - 4; i += 4)
  {         
      StartEbene = RMQ_E[i].getEbene();   
      if (StartEbene < lowest)
      {
        lowest = StartEbene;
        lowest_index = i;
      }
      increments = 0;
      decrements = 0;     
      /////////////////////////////////////////////////////////
      aktueller_Durchlauf = i + 1;
      if (RMQ_L[aktueller_Durchlauf])
      {
        increments++;
      } else {
        decrements++;
      }
      temp = (StartEbene + increments - decrements);
      if (temp < lowest)
      {
        lowest = temp;
        lowest_index = aktueller_Durchlauf;
      }                 
      /////////////////////////////////////////////////////////
      aktueller_Durchlauf = i + 2;
      if (RMQ_L[aktueller_Durchlauf])
      {
        increments++;
      } else {
        decrements++;
      }
      temp = (StartEbene + increments - decrements);
      if (temp < lowest)
      {
        lowest = temp;
        lowest_index = aktueller_Durchlauf;
      }             
      /////////////////////////////////////////////////////////
      aktueller_Durchlauf = i + 3;
      if (RMQ_L[aktueller_Durchlauf])
      {
        increments++;
      } else {
        decrements++;
      }
      temp = (StartEbene + increments - decrements);
      if (temp < lowest)
      {
        lowest = temp;
        lowest_index = aktueller_Durchlauf;
      }                            
  }
  // Rest abarbeiten
  if (rest > 0)
  {
    for (int i=endSchleife; i<=ende; i+=1)
    {     
      if (RMQ_E[i].getEbene() < lowest)
      {
        lowest = RMQ_E[i].getEbene();
        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;
}

/* Zeitmessung ausgeben, completeTimeBefore muss vorher separat genommen werden */
void nimmZeit(String AusgabeString)
{
  completeTimeAfter = System.currentTimeMillis();    
  completeTimeDiff   = completeTimeAfter - completeTimeBefore;    
  /* Ausgabe für Gesamtdurchlauf formatieren */
  String timeString = String.format("\n\nZeit benötigt für %s: %02d min, %02d sec, %03d milliseconds",
    AusgabeString,
    TimeUnit.MILLISECONDS.toMinutes(completeTimeDiff),
    TimeUnit.MILLISECONDS.toSeconds(completeTimeDiff) -
      TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(completeTimeDiff)),
    completeTimeDiff % 1000);  
  println(timeString);     
}

 

Tag-Wolke

Monats-Liste