Thomas Kramer

IT-COW | All posts tagged 'Processing'

Original umgesetzter Sparse-Table-Algorithmus

By Administrator at September 03, 2012 15:20
Filed Under: Algorithmen, Java, Projekte

Ich habe festgestellt dass ich meine Sparse Table-Algorithmen 1 2 nicht originalgetreu umgesetzt habe. Sie lieferten natürlich schon hundertprozentig korrekte Ergebnisse.

 

Ich hatte immer eine Schleife ausführen lassen die aufeinanderfolgende Blöcke auswählt, ich kam so auf mehr Schritte als notwendig waren. Im Original-Algorithmus werden immer genau zwei Blöcke ausgewählt und miteinander verglichen, die sich sogar überschneiden können. Der kleinste Block bezieht sich auf lediglich ein Array-Element, es kann mit dem M-Array also immer der gesamte Bereich abgedeckt werden.

 

Ich habe es nun originalgetreu umgesetzt, mit binär ausgeführter Zweierlogarithmus-Bestimmung aus den Bit Twiddling Hacks und Loop Unrolling.

 

Meine alten Zeiten waren:

 

- Bei 1.000.000 Knoten und 1.000.000 RMQ-Abfragen eine Vorverarbeitungszeit von 5,590 Sekunden und eine Abfragezeit von 4,502 Sekunden.

 

Meine neuen Ausführungszeiten sind, wieder auf meinem fünf Jahre alten Turion 64x2 1,6 GHZ-Notebook:

 

- Bei 1.000.000 Knoten und 1.000.000 RMQ-Abfragen eine Vorverarbeitungszeit von 5,133 Sekunden und eine Abfragezeit von 1,090 Sekunden.

 

Der Algorithmus ist jetzt bereits sehr schnell – man vergleiche meine Ergebnisse mit der ursprünglichen linearen Minimumsbestimmung, die mit kleineren Optimierungen eine Abfragezeit von 22 Sekunden bei 100.000 RMQ-Abfragen ergab (dafür natürlich komplett ohne Präprozessing, aber insgesamt trotzdem wesentlich langsamer).

 

In der Bachelor-Arbeit von Antonia Kresse geht es noch einen Schritt weiter, um die Vorverarbeitungszeit des Sparse Table-Algorithmus speziell für die jeweilige +/-1-Differenz des RMQ_L-Arrays von O(n log(n)) auf O(n) zu verringern – vergleiche Kapitel 4.2.1.

 

Mit diesen Optimierungen wäre der Algorithmus aber nicht mehr universell einsetzbar sondern auf LCA-Abfragen beschränkt. Optimal scheint der Algorithmus von Bender und Farach-Colton zu sein, der auf den kartesischen Baum setzt – zu diesem hätte ich gerne noch mehr (deutsche) Dokumentation.

 

Für die meisten Anwendungsfälle dürfte aber bereits dieser Sparse Table-Algorithmus schnell genug sein.

 

Update 04.09.2012: Ich habe gerade noch versucht die Logarithmus-Bestimmung gemäß den Bit Twiddling Hacks mit einer vorberechneten Logarithmus-Tabelle zu beschleunigen, aber das ergab im Vergleich zu vorher bei 1.000.000 RMQ-Abfragen lediglich einen Zeitvorteil von 0,008 Sekunden und kann vernachlässigt / ignoriert werden. Es lohnt sich nicht da noch nach Verbesserungen zu suchen, die einfachste binäre Variante ist schnell genug.

 

Relevant wäre nur noch eine Verbesserung der Vorverarbeitungszeit.

 

Update 27.07.2013: Ich habe noch Details verbessert:

 

1. Bei der Erzeugung der Knoten lasse ich den Wurzelknoten jetzt außerhalb der Schleife erzeugen weil er eine Sonderbehandlung benötigt - Einsparung einer If-Abfrage innerhalb der Schleife.

2. Die jeweilige Ebene der Knoten lasse ich nun von 0 an zählen statt ab 1, weil das in den Ausarbeitungen zu dem Thema so üblich ist. Auf die Ergebnisse hat das übrigens keinen Einfluss. Vorweggenommen übrigens von dieser Variante.

 

Update 15.07.2014: Fehler beseitigt: Die Bestimmung des am weitesten links und weitesten rechts liegenden Knotens kann nicht bereits in der Einfuegen-Routine geschehen, ich habe das nun in eine separate Routine finde_MinMax_Versatz ausgelagert.

 

/************************************************************************************
             Visualisierung eines binären Suchbaumes in Processing
                 mithilfe des Reingold-Tilford-Algorithmus
              und Suche des LCA über den Sparse-Table-Algorithmus
                             von Thomas Kramer
                          Version 4.8 - 14.07.2014
************************************************************************************/

/* Konfiguration */
   int Baumelemente = 1000000;
   /* wenn Zentrierung aktiviert wird, werden die Mausabfragen
      und das wiederholte Zeichnen deaktiviert */

   boolean Zentrierung = true;

   /* Zeichnen einschalten? */
   boolean zeichnen = false;  
   /* RMQ-Abfragen einschalten? */
   boolean RMQ_Praeprocessing = true;
   boolean RMQ_Abfragen = true;
   /* beide LCA-Routinen ausführen und somit auf Übereinstimmung checken? */
   boolean RMQ_Check = false;
  
   /* debugging-Ausgabe */
   boolean debug = 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_M       = new int  [2*Baumelemente-1][(int) Math.ceil(Math.log(2*Baumelemente-1)/Math.log(2.0))];
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;

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

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 damit es nicht automatisch während der Zeitmessungen geschieht */
  System.gc();

  /*-----------------------------------------------------------------------------
   *  Startzeit nehmen für Erzeugen der Zufallszahlen
   *-----------------------------------------------------------------------------*/
                   
   completeTimeBefore = System.currentTimeMillis();                     
  
  /*-----------------------------------------------------------------------------
   *  einmalige Zufallszahlen erzeugen
   *-----------------------------------------------------------------------------*/
                 
  Zufallszahlen = new HashSet<Integer>();
  while (Zufallszahlen.size() < Baumelemente)
    Zufallszahlen.add((int) random(unten, oben));      
     
  /*-----------------------------------------------------------------------------
   *  Endzeit messen für Erzeugen der Zufallszahlen
   *-----------------------------------------------------------------------------*/
  
  nimmZeit("Erzeugen der Zufallszahlen");      
  
  /*-----------------------------------------------------------------------------
   *  Beginn des RT-Algorithmus
   *-----------------------------------------------------------------------------*/

  completeTimeBefore = System.currentTimeMillis();                   
   
  /*-----------------------------------------------------------------------------
   *  Knoten erzeugen, gehört mit zum RT-Algorithmus
   *-----------------------------------------------------------------------------*/

  Iterator<Integer> it = Zufallszahlen.iterator();
 
  /* Wurzelknoten erzeugen */
  Wurzel = Einfuegen(null, null, it.next(), 0, 0);   
  /* Initialisierungswerte setzen */
  kleinster_Versatz=Wurzel;
  groesster_Versatz=Wurzel;                   
 
  int i = 1; 
  shuffledList = new tBaum[Baumelemente-1];
  while (it.hasNext())
  { 
    Einfuegen(Wurzel, null, it.next(), 0, i);
    shuffledList[i-1]=letzter_Knoten;    
    i++;
  }   

  nimmZeit("Zwischenergebnis, Erzeugen der Knoten");     
 
  berechne_Versatz(Wurzel);
  finde_MinMax_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);
    fillRMQ_R_Array();
    praeprocessM(RMQ_M, RMQ_L, 2*Baumelemente-1);   
   
    /* Endzeit nehmen und Ausgabe */
    nimmZeit("Erstellung der RMQ-Arrays");
    /*-----------------------------------------------------------------------------
     *  Debug-Ausgabe der RMQ-Arrays
     *-----------------------------------------------------------------------------*/
         
     if (debug)
     {  
       String DebugString1;
       String DebugString2;
       String DebugString3;
       String DebugString4;   
       String DebugString5;          
       DebugString1="Index  ";
       DebugString2="RMQ_E: ";
       DebugString3="RMQ_L: ";
       DebugString5="RMQ_M: ";          
       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*2-1); r++)      
       {
         for (int s=0; s<=4; s++)
         {
           DebugString5 += r + "-" + ((int) (pow(2,s))+r-1);          
           DebugString5 += "=" + RMQ_M[r][s] + ", ";         
         }
       }
       for (int r=0; r<Baumelemente; r+=1)
       {
         DebugString4+=RMQ_R[r] + ", ";
       }

       println(DebugString1);
       println(DebugString2);
       println(DebugString3);
       println(DebugString5);       
       println(DebugString4);     
     } 
    /*-----------------------------------------------------------------------------
     *  RMQ-Abfragen beantworten
     *-----------------------------------------------------------------------------*/

    if (RMQ_Abfragen && RMQ_Praeprocessing)
    {
      /* Zuerst Liste mit Knoten shufflen */
      Collections.shuffle(Arrays.asList(shuffledList));
     
      /* Startzeit nehmen  */
      completeTimeBefore = System.currentTimeMillis();     
     
      int tag1 = 0;
      int tag2 = 0;
      int temp1 = 0;
      int temp2 = 0;
      boolean resultCheck = true;
      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;

        temp1 = LCA1(tag1, tag2).tag;
        if (RMQ_Check)
        {
          temp2 = LCA2(tag1, tag2).tag;       
          if (temp1 != temp2)
          {
            println("Fehler! Keine Übereinstimmung bei " + tag1 + ", " + tag2 +
                    " (LCA1-Ergebnis = " + temp1 + ", LCA2-Ergebnis = " + temp2 + ")");
            resultCheck = false;
          }
        }
        i++;
        x--;    
      }
     
      if (RMQ_Check && resultCheck)
      {
        println("RMQ-Check ohne Fehler ausgeführt!");
      }
     
      /* 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 */ 
    ausgegeben = false;
    completeTimeBefore = System.currentTimeMillis();       
    ZeigeBaum(Wurzel, 0, 0);
    /* Endzeit nehmen und Ausgabe */
    nimmZeit("Baumzeichnen");
    ausgegeben = true;   
  }
  /*-----------------------------------------------------------------------------
   *  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) = " + LCA1(7,8).tag, ((screen.width)/2)-20, (screen.height)-150);
    text("LCA(4,6) = " + LCA1(4,6).tag, ((screen.width)/2)-20, (screen.height)-130);
    text("LCA(3,4) = " + LCA1(3,4).tag, ((screen.width)/2)-20, (screen.height)-110);
    text("LCA(5,8) = " + LCA1(5,8).tag, ((screen.width)/2)-20, (screen.height)-90);
    text("LCA(7,9) = " + LCA1(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++;
    /* Integer-Division durch 2*/
    Versatz=(Versatz>>1);
    /* 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;
    Knoten.tag = tag;
    /* Versatz mit Initialisierungswerten versehen */
    Knoten.Versatz = Versatz;    
    /* Vorsicht mit Post-Inkrement bei einer globalen Variable! (Ebene) */
    EbenenInsgesamt = max(Ebene + 1, EbenenInsgesamt);   
   
    letzter_Knoten = Knoten;
  } else
  {
    Ebene++;
    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--;
  }
  return Knoten;
}

/* Bestimmung der Knoten mit dem kleinsten und groessten Versatz, kann nicht
* bereits in der Einfuegen-Routine geschehen weil
* berechne_Konturen den Versatz nachträglich korrigiert, allerdings nicht für
* alle Knoten sondern nur für Knoten die 2 Unterknoten haben.
*/

void finde_MinMax_Versatz(tBaum Knoten)
{
    if (Knoten != null)
    {
        /* kleinsten/größten Versatz bestimmen */
        if (Knoten.Versatz < (kleinster_Versatz).Versatz)
            kleinster_Versatz = Knoten;
        if (Knoten.Versatz > (groesster_Versatz).Versatz)
            groesster_Versatz = Knoten;

        finde_MinMax_Versatz(Knoten.links);
        finde_MinMax_Versatz(Knoten.rechts);
    }
}

/* 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+1) * Hoehe) + ((Knoten.Ebene+1) * ZwischenAbstandOben);
   
    if (GesamtPositionLinks < 0 )
    {
        println("unter null " + GesamtPositionLinks);
        println(Knoten.Versatz);
    }   
  }
  else {
    GesamtPositionLinks=((screen.width / 2) - mouseX) - AbstandLinks + BenutzteFelder;
    GesamtPositionOben=((screen.height / 2) - mouseY) - AbstandOben + ((Knoten.Ebene+1) * Hoehe) + ((Knoten.Ebene+1) * 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 != 0)
    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++;
    RMQ_E[Zaehler] = Knoten;
    RMQ_L[Zaehler] = Knoten.Ebene;  
   
    elementsProcessed.put(Knoten.tag, Zaehler);
   
    if (Knoten.links!=null)
    {
      Zaehler=Euler_Tour(Knoten.links, Zaehler)+1;
      RMQ_E[Zaehler]=Knoten;
      RMQ_L[Zaehler]=Knoten.Ebene;        
    }

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

void praeprocessM(int[][] M, int A[], int N)

  int i, j;
  
  for (i = 0; i < N; i++)
  {
     M[i][0] = i;
  }

  for (j = 1; (1 << j) <= N; j++)
  {
    for (i = 0; i + (1 << j) - 1 < N; i++)
    {
      if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
      {
        M[i][j] = M[i][j - 1];
      } else {
        M[i][j] = M[i + (1 << (j - 1))][j - 1];
      }
    }
  }
}

/* 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 Sparse Table-Algorithmus den Lowest Common Ancestor ermitteln */
tBaum LCA1(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;
 
  /* Start- und Endwert für Schleife setzen */
  int start;
  int ende;
  int temp1 = RMQ_R[tag1];
  int temp2 = RMQ_R[tag2];
  if (temp1 < temp2)
  {
    start = temp1;
    ende = temp2;
  } else {
    start = temp2;
    ende = temp1;
  } 
 
  /* Logarithmus-Bestimmung, mit Loop Unrolling */  
  temp1 = ende - start;     
  temp2 = temp1;
  int r = 0;

  while ((temp2 >>= 1) > 0)
  {
    r++;
    if ((temp2 >>= 1) > 0)
    {
      r++;
    }
    if ((temp2 >>= 1) > 0)
    {
      r++;
    }
    if ((temp2 >>= 1) > 0)
    {
      r++;
    }
  } 

  int lowest_index = 0; 
  temp1 = RMQ_M[start][r];
  temp2 = RMQ_M[ende - (1 << r) + 1][r];   
  if (RMQ_L[temp1] <= RMQ_L[temp2]) 
  {
    lowest_index = temp1;   
  } else {
    lowest_index = temp2;
  } 
  
  /* 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 ((result.tag == tag1) || (result.tag == tag2))
    if (result.Vater != null )
       result = result.Vater;
  return result;
}

/* mittels RMQ-Algorithmus den Lowest Common Ancestor ermitteln */
tBaum LCA2(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;
  int start=min(RMQ_R[tag1], RMQ_R[tag2]);
  int ende=max(RMQ_R[tag1], RMQ_R[tag2]);
  int rest = (ende - start + 1) & 3;
  int endSchleife = ende - rest + 1;

  for (int i = start; i<=endSchleife - 4; i += 4)
  {
    if (RMQ_L[i]<lowest)
    {
      lowest=RMQ_L[i];
      lowest_index=i;
    }
   
    if (RMQ_L[i+1]<lowest)
    {
      lowest=RMQ_L[i+1];
      lowest_index=i+1;
    }   

    if (RMQ_L[i+2]<lowest)
    {
      lowest=RMQ_L[i+2];
      lowest_index=i+2;
    }

    if (RMQ_L[i+3]<lowest)
    {
      lowest=RMQ_L[i+3];
      lowest_index=i+3;
    }
  }
  // Rest abarbeiten
  if (rest > 0)
  {
    for (int i=endSchleife; i<=ende; 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;
}

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

 

Monats-Liste