Thomas Kramer

IT-COW | Ein schneller <O(N), O(sqrt(N))> – RMQ-Algorithmus

Ein schneller <O(N), O(sqrt(N))> – RMQ-Algorithmus

By Administrator at August 26, 2012 18:25
Filed Under: Algorithmen, Java, Projekte

Inspiriert von topcoder.com habe ich den anfangs aufgeführten RMQ-Algorithmus mit einer Laufzeit von <O(N), O(sqrt(N))> implementiert und auf mein LCA-Programm angewandt. Im Link wird nur die Idee für den Algorithmus erläutert, der Quellcode stammt von mir.

 

Range Minimum Query bezeichnet die Idee innerhalb eines Arrays und zwischen zwei bestimmten Indexpositionen den niedrigsten Wert und dessen Index zu bestimmen – eine typische Minimumsuche. Die gängigen Lösungen im Internet sehen ein streng lineares Vorgehen durch das Array vor, es gibt aber auch schnellere Varianten aus dem Bioinformatikbereich – Links dazu habe ich in den vorangegangenen Blog-Einträgen gegeben, die (deutsche) Referenz zu dem Thema stellt das Skript “Algorithmen auf Sequenzen” der Ludwig-Maximilians-Universität München dar.

 

Die Vorgehensweise um den Lowest Common Ancestor in einem Baum mittels Euler-Tour und RMQ zu bestimmen habe ich bereits in früheren Beiträgen erläutert. Mittels einer LCA-Abfrage wird der tiefste gemeinsame Vorfahre zweier Knoten in einem Baum bestimmt. In meinen vorherigen Binärbaum-Programmen habe ich den LCA auf RMQ reduziert – alle vorherigen Varianten benutzten aber die lineare Minimumsuche im RMQ_L-Array (mit kleineren Tricks wie Loop-Unrolling), die Idee für die nachfolgend vorgestellte Variante geht schneller vor.

 

Die Idee für diesen Algorithmus scheint mir nur auf topcoder.com gelistet zu sein, in den Universitätsskripten habe ich sie nicht gefunden aber auch noch nicht gezielt danach gesucht. Die Idee funktioniert folgendermaßen:

 

Es wird zunächst ein Präprozessing durchgeführt, eine Vorverarbeitung. Man geht das RMQ_L-Array in einer Schleife durch, in ⌊√(N)⌋-Intervallen, wobei N die Arraylänge kennzeichnet – und in jedem dieser Intervalle wird das jeweilige Minimum bestimmt und im RMQ_M-Array zwischengespeichert. Beginnt ein neuer Block wird der Vergleichswert wieder zurückgesetzt und der Indexzähler für das RMQ_M-Array um eins inkrementiert.

 

Bei einer RMQ-Abfrage muss man dann zunächst bestimmen ob die Start- und End-Werte innerhalb von solchen Blöcken liegen, das erreicht man mit Modulo-Abfragen. Wenn ((Start % Inkrement) == 0) oder ((Ende % Inkrement) < (Inkrement - 1)) zutreffen kann ich nicht auf das RMQ_M-Array zugreifen und muss wieder linear das RMQ_L-Array in diesen Bereichen nach den niedrigsten Werten durchsuchen.

 

Ein Teil der Minimumsuche wird demnach in das Präprozessing vorverlagert, das interessante daran ist aber dass sich die Vorverarbeitungszeit kaum nennenswert steigert und man bei der Gesamtlaufzeit einen tatsächlichen Geschwindigkeitsvorteil erreicht. Diese Variante ist bereits erheblich schneller als die lineare Minimumbestimmung und stellt einen interessanten Kompromiss zwischen Implementierungskomplexität und Schnelligkeit dar.

 

Ich habe nun diesen Algorithmus auf die LCA-Abfragen meines Binärbaumprogrammes angewandt. Ich habe einen zusätzlichen RMQ-Check eingebaut, der optional die Ergebnisse der alten LCA-Routine mit den Ergebnissen der neuen Variante vergleicht und bei einer Abweichung Fehlermeldungen ausgibt. Ich habe auf diese Weise tatsächlich noch einen Fehler beheben können, die Übereinstimmung liegt nun bei hundert Prozent.

 

Zu dem Laufzeitverhalten, die alte Variante benötigte auf meinem fünf Jahre alten Turion 64x2 1,6 GHZ-Notebook bei 100.000 Knoten und 100.000 RMQ-Abfragen wie gesagt um die 22 Sekunden, mit minimalen Optimierungen wie binärem Modulo und Loop-Unrolling.

 

Die neuen Laufzeiten sind:

 

- Bei 100.000 Knoten und 100.000 RMQ-Abfragen eine Vorverarbeitungszeit von 0,213 Sekunden und eine Abfragezeit von 0,454 Sekunden.

- Bei 200.000 Knoten und 200.000 RMQ-Abfragen eine Vorverarbeitungszeit von 0,636 Sekunden und eine Abfragezeit von 1,305 Sekunden.

- Bei 300.000 Knoten und 300.000 RMQ-Abfragen eine Vorverarbeitungszeit von 0,312 Sekunden und eine Abfragezeit von 2,362 Sekunden.

- Bei 400.000 Knoten und 400.000 RMQ-Abfragen eine Vorverarbeitungszeit von 1,351 Sekunden und eine Abfragezeit von 3,810 Sekunden.

- Bei 500.000 Knoten und 500.000 RMQ-Abfragen eine Vorverarbeitungszeit von 0,611 Sekunden und eine Abfragezeit von 5,437 Sekunden.

 

Bei Abweichungen unter einer Sekunde bitte eventuelle Messungenauigkeiten beachten. Ich denke die Geschwindigkeit des Algorithmus kann sich bereits sehen lassen. Das Verfahren hätte sich auch im Informatik-Studium gut gemacht, dort wurde das aber nicht gelehrt.

 

Noch etwas zu der benötigten Größe des RMQ_M-Arrays, diese beträgt [(int) Math.ceil((double) (2*Baumelemente-1) / ((int) sqrt(2*Baumelemente-1)))] – hierbei muss man beachten keine Integer-Division durchzuführen, daher habe ich den Dividenden explizit nach double gecastet. Das Ergebnis muss aufgerundet werden, daher die Nutzung der Math.ceil-Funktion.

 

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

/* Konfiguration */
   int Baumelemente = 500000;
   /* wenn Zentrierung aktiviert wird, werden die Mausabfragen deaktiviert */
   boolean Zentrierung = true;
   /* 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;
   /* 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 */

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

/* 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  [(int) Math.ceil((double) (2*Baumelemente-1) / ((int) sqrt(2*Baumelemente-1)))];
int[]   RMQ_R       = new int  [Baumelemente];
int increment = (int) sqrt(Baumelemente*2-1);  

Hashtable<Integer, Integer> elementsProcessed = new Hashtable<Integer, Integer>();
HashSet<Integer> Zufallszahlen = new HashSet<Integer>();
ArrayList<tBaum> ZList = new ArrayList<tBaum>();
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 damit 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();
  ZList = new ArrayList<tBaum>();  
  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);
      ZList.add(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);
    fillRMQ_R_Array();
    praeprocessM(RMQ_L, RMQ_M);   
    /* 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<(((int) sqrt(Baumelemente*2-1))+1); r+=1)
       {
         DebugString5+=RMQ_M[r] + ", ";         
       }
       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)
    {
      /* Zuerst Liste mit Knoten shufflen */
      Collections.shuffle(ZList);
      /* 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 = ZList.get(i).tag;
        tag2 = ZList.get(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 */ 
    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) = " + 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+=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)
{
  if (Knoten!=null)
  {
    Zaehler += 1;
    RMQ_E[Zaehler] = Knoten;
    RMQ_L[Zaehler] = Knoten.Ebene-1;  
    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-1;        
    }

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

void praeprocessM(int[] L, int[] M)

  /* Startwert für Minimumsuche */
  int lowest = Baumelemente;
  /* Ende im Array festlegen */
  int arrayEnding = Baumelemente*2-2; 
  /* Indexvariable für RMQ_L */
  int r = 0;
  /* Indexvariable für RMQ_M */
  int s = 0;

  int temp;
  do
  {
    temp = RMQ_L[r];
    if (temp < lowest)
    {
      /* neuer niedrigster Wert im Block gefunden */
      lowest = temp;
      RMQ_M[s] = r;
    }
     /* noch nicht alle Indizes abgehandelt,
        Berechnungen einsparen falls doch, deswegen if-Abfrage */
  
    if (r < arrayEnding)
    {   
      /* Erkennen eines neuen Blocks */
      if (((r+1) % increment) == 0)
      {
        /* neuer Block beginnt, also muss Minimum wieder zurückgesetzt und s erhöht werden */
        lowest = Baumelemente;       
        s++;       
      }     
    }
    r++;   
  }  
  while (r <= arrayEnding); 
}

/* 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 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; 
  } 
  int startBlock = start / increment;
  int endBlock = ende / increment;     
  /* Startwert für Minimumsuche */
  int lowest = Baumelemente;
  int lowest_index = 0;    
  /////////////////////////////////////////////////////////////////////////
  /* bei 20 Elementen gibt es bspw. 6er Blöcke (increment).
  wenn ich jetzt als tag1=5 und als tag2=12 festlege wird
  der Bereich 6-11 vom Inhalt von M[1] bereits abgedeckt
  und RMQ_L[5] und RMQ_L[12] muss ich separat abfragen */

  /* ich lege also hier den Block innerhalb von tag1 und tag2
  fest der vollständig vom M-Array abgefangen wird */

  /* liegt der Anfang innerhalb eines Blocks, wenn ja nimm als Anfang den
     nächsten Block */

  int rest = start % increment;
  if (rest > 0)
  {
    startBlock++;
  }

  /* liegt das Ende innerhalb eines Blocks, wenn ja nimm als Ende den
     vorherigen Block */
 
  rest = ende % increment;
  if (rest < (increment-1))
  {
    endBlock--;
  }
  /* Indexvariablen */
  int r = 0;
  int s = startBlock;     
  /* bei Grenzüberschreitungen ist die Distanz nicht groß genug für einen vollständigen Block */
  if (((startBlock * increment) > ende) ||
      ((endBlock * increment + increment - 1) < start) ||
      (endBlock < startBlock))
  {
    /* Alles auf einmal durchsuchen */
    for (r = start; r <= ende; r++)
    {   
      temp1 = RMQ_L[r];
      if (temp1 < lowest)
      {
        lowest = temp1;
        lowest_index = r;
      }      
    }
  } else {
    /* Ersten Teil vor erstem Block durchsuchen */
    temp2 = startBlock * increment;
    for (r = start; r < temp2; r++)
    {
      temp1 = RMQ_L[r];
      if (temp1 < lowest)
      {
        lowest = temp1;
        lowest_index = r;
      }                
    } 
    /* danach alle Blöcke durchsuchen */
    do
    {
      temp1 = RMQ_L[RMQ_M[s]];
      if (temp1 < lowest)
      {
        lowest = temp1;
        lowest_index = RMQ_M[s];
      }                
      s++;
    }
    while (s <= endBlock);
    /* danach Rest durchsuchen */
    temp2 = endBlock * increment + increment;
    for (r = temp2; r <= ende; r++)
    {
      temp1 = RMQ_L[r];
      if (temp1 < lowest)
      {
        lowest = temp1;
        lowest_index = r;
      }                
    }          
  }
  /* 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);   
}

 

Kommentar schreiben




  Country flag
biuquote
  • Kommentar
  • Live Vorschau
Loading


Tag-Wolke

Monats-Liste