AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Binärbäume iterativ speichern

Ein Thema von new32 · begonnen am 19. Jun 2008 · letzter Beitrag vom 5. Jul 2008
Antwort Antwort
Seite 1 von 2  1 2   
new32

Registriert seit: 10. Mai 2005
160 Beiträge
 
Delphi 7 Enterprise
 
#1

Binärbäume iterativ speichern

  Alt 19. Jun 2008, 18:01
Da ich oft genug von Problemen deiser Art gelesen habe und mit den meisten iterativen Lösungen (virtuellen Stack anlegen...) unzufrieden war, hier meine Lösung für dieses Problem:

Der Typ auf dem der Baum basiert:
Code:
typedef struct _DB {         //a simple DataBase
   struct _DB *parent;      //if(parent==0) "root of the db"
   struct _DB *sChild, *bChild;   //sChild->key < key; bChild->key > key
   char *key;
   char *value;
DB;
Die rekursive Lösung:
Code:
int DBRSave(DB *db, FILE *f){      //kann zu Stacküberlauf führen!
   size_t lng;
   if(db->key && db->value && strlen(db->key) && strlen(db->value)){
      lng=strlen(db->key);
      fwrite(&lng, sizeof(size_t), 1, f);
      fwrite(db->key, lng, 1, f);

      lng=strlen(db->value);
      fwrite(&lng, sizeof(size_t), 1, f);
      fwrite(db->value, lng, 1, f);
   }
   if(db->sChild) DBRSave(db->sChild, f);
   if(db->bChild) DBRSave(db->bChild, f);
   return 0;
}
Sollte sich selbst erklären.


Die iterative Lösung
Code:
int DBISave(DB *db, FILE *f){
   size_t lng;
   int bigPart=0;
   DB *prevDB;
   while(1){
      do{
         if(db->key && db->value && strlen(db->key) && strlen(db->value)){
            lng=strlen(db->key);
            fwrite(&lng, sizeof(size_t), 1, f);
            fwrite(db->key, lng, 1, f);

            lng=strlen(db->value);
            fwrite(&lng, sizeof(size_t), 1, f);
            fwrite(db->value, lng, 1, f);
         }
      } while(db->sChild && (db=db->sChild)); //Zweite "Bedingung" wichtig!
      prevDB=NULL;
      while(db->parent &&
               (prevDB==db->bChild ||
                !db->bChild)
          ){
         prevDB=db;
         db=db->parent;
      }   
                
      if(!db->parent){
         if(bigPart) return 0;
         else bigPart=1;
      }
      db=db->bChild;
   }
}
Zum Ablauf:
Zu erst arbeitet sich die Funktion von der Wurzel bis zum kleinsten Eintrag vor.
Dann geht es wieder hoch. So lange bis ein größerer Eintrag (bChild) gefunden wurde.
Von diesem Eintrag ausgehend, wieder zum kleinsten Eintrag dieses Zweiges.
Dieser Vorgang wird solange wiederholt, bis alles abgearbeitet ist!

Vorteile:
Schneller, weniger Arbeitsspeicher, kein Stacküberlauf

Nachteil:
Schwieriger zu verstehen




Und zu guter Letzt die Delphi-Version:
Delphi-Quellcode:
type
   size_t=ulong;
   lpDB=^DBr;
   DBr = record //a simple DataBase
     parent:lpDB; //if(parent==0) "root of the db"
     sChild, bChild:lpDB; //sChild->key < key; bChild->key > key
     key:PCHAR;
     value:PCHAR;
   end;

function DBISave(db:lpDB; var f:FILE):integer;
var
lng:size_t;
bigPart:integer;
prevDB:lpDB;
help:boolean;
begin
   bigPart:=0;
   while true do begin
      repeat
         if(db.key<>nil) and (db.value<>nil) and (strlen(db.key)>0) and (strlen(db.value)>0) then begin
            lng:=strlen(db.key);
            blockwrite(f, lng, sizeof(size_t));
            blockwrite(f, db.key^, lng);

            lng:=strlen(db.value);
            blockwrite(f, lng, sizeof(size_t));
            blockwrite(f, db.value^, lng);
         end;
         if db.sChild<>nil then begin db:=db.sChild; help:=true end else help:=false;
      until help=false;
      prevDB:=nil;
      while((db.parent<>nil) and
               ((prevDB=db.bChild) or
                (db.bChild=nil))
          ) do begin
         prevDB:=db;
         db:=db.parent;
      end;

      if(db.parent=nil) then begin
         if(bigPart=1) then begin
           result:=0;
           exit;
         end else bigPart:=1;
      end;
      db:=db.bChild;
   end;
end;
Angehängte Dateien
Dateityp: pas db_142.pas (4,0 KB, 4x aufgerufen)
~?&/%§$§%\&?~
8)
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.622 Beiträge
 
Delphi 2007 Enterprise
 
#2

Re: Binärbäume iterativ speichern

  Alt 19. Jun 2008, 18:25
Fragen:
1) Klappen beide Verfahren auch für nicht voll besetzte/ausgeglichene Bäume?
2) Die jeweiligen Funktionen zum Lesen wären nett. Kann man zwar ableiten, der Vollständigkeit wegen aber wäre es sinnvoll.
3) Die Beschränkung auf binäre Bäume finde ich schade. Magst des nicht aufbohren?
4) Delphi-Versionen wären Zucker
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
new32

Registriert seit: 10. Mai 2005
160 Beiträge
 
Delphi 7 Enterprise
 
#3

Re: Binärbäume iterativ speichern

  Alt 19. Jun 2008, 18:58
zu 1: sollte eigentlich immer funktionieren
getestet mit mehr als 1 Mio. (fast 2 Mio.) Einträgen
Aber natürlich können noch Fehler drin sein (gestern erst geschrieben)

zu 2: ich hab die Funktionen (fast) 1:1 aus einem meiner Projekte kopiert. Ich kann die ganze Datei anhängen ( mit Funktionen zum suchen, hinzufügen, lesen, ... )

zu 3: mal schauen

zu 4: done
~?&/%§$§%\&?~
8)
  Mit Zitat antworten Zitat
Dax
(Gast)

n/a Beiträge
 
#4

Re: Binärbäume iterativ speichern

  Alt 3. Jul 2008, 21:04
Mir ist es bis jetzt nie untergekommen, dass ein rekursives Durchlaufen von Binärbäumen ein Stacküberlauf produziert hätte... Dazu müssten die Bäume doch ziemlich entartet sein?
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#5

Re: Binärbäume iterativ speichern

  Alt 3. Jul 2008, 22:15
*Schnipps* *Meld* *Meld*

Wozu benutzt man heutzutage noch Bäume?
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Dax
(Gast)

n/a Beiträge
 
#6

Re: Binärbäume iterativ speichern

  Alt 3. Jul 2008, 22:16
Zitat von alzaimar:
*Schnipps* *Meld* *Meld*

Wozu benutzt man heutzutage noch Bäume?
Ich benutze welche für Priority Queues Wenn du eine bessere Struktur mit ähnlicher (Programmier)komplexität kennst, bitte sag
  Mit Zitat antworten Zitat
mkinzler
(Moderator)

Registriert seit: 9. Dez 2005
Ort: Heilbronn
39.692 Beiträge
 
Delphi 10.4 Sydney
 
#7

Re: Binärbäume iterativ speichern

  Alt 3. Jul 2008, 22:17
Zitat:
Wozu benutzt man heutzutage noch Bäume?
Implizit ständig
Markus Kinzler
  Mit Zitat antworten Zitat
new32

Registriert seit: 10. Mai 2005
160 Beiträge
 
Delphi 7 Enterprise
 
#8

Re: Binärbäume iterativ speichern

  Alt 4. Jul 2008, 19:16
Zitat von Dax:
Mir ist es bis jetzt nie untergekommen, dass ein rekursives Durchlaufen von Binärbäumen ein Stacküberlauf produziert hätte... Dazu müssten die Bäume doch ziemlich entartet sein?
Richtig, aber leider ist mir genau das passiert:
Eines meiner Programme (ein Offlinebrowser) legt alle gefundenen URLs in einem Baum ab, der als eine Art Index URL mit lokalen Namen verbindet.

Und ab einer gewissen Zahl Einträgen is das Programm beim Speichern regelmäßig abgestürzt.

Und ich kann mir vorstellen, dass es andere Probleme gibt, bei denen dei Bäume ahnlich "entarten"
~?&/%§$§%\&?~
8)
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#9

Re: Binärbäume iterativ speichern

  Alt 5. Jul 2008, 09:18
Du must eben ausgeglichene/ausgleichende Bäume (aka AVL-Bäume, Red-Black-Trees) verwenden. Die entarten nicht.

Wieso verwendest Du nicht
a) eine TStringlist (oder schneller: THashedStringlist in IniFiles)
b) eine Hashmap
c) eine Skiplist


Bis 10.000 Einträgen reicht a) (Variante 'THashedStringlist'), danach b) oder c).

Im Anhang ein AVL-Unit
Angehängte Dateien
Dateityp: rar avltrees_227.rar (7,3 KB, 10x aufgerufen)
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
new32

Registriert seit: 10. Mai 2005
160 Beiträge
 
Delphi 7 Enterprise
 
#10

Re: Binärbäume iterativ speichern

  Alt 5. Jul 2008, 10:34
AVL-Bäume beruhen doch auf dem selben Prinzip. Nur das Löschen funktioniert anders.
[verbessere mich wenn ich mich irre] und löschen muss ich nicht, also sollte der Baum (einigermaßen) ausgeglichen sein.

Aber mein Baum fasst auch mehr als 1 Mio. Einträge!
Und das mit ner Liste; naja. Da macht das Arbeiten nurnoch wenig spaß!
immerhin komme ich noch auf fast 1000 Einträge pro Sek.
Und das Speichern läuft noch mal um Faktor 100 schneller.

Ne Liste hab ich parallel laufen. die wird aber nicht durchsucht, sondern nur abgearbeitet (Stapel)
~?&/%§$§%\&?~
8)
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 19:34 Uhr.
Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf