![]() |
Binärbäume iterativ speichern
Liste der Anhänge anzeigen (Anzahl: 1)
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:
Die rekursive Lösung:
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;
Code:
Sollte sich selbst erklären.
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; } Die iterative Lösung
Code:
Zum Ablauf:
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; } } 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; |
Re: Binärbäume iterativ speichern
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 ;) |
Re: Binärbäume iterativ speichern
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 :!: |
Re: Binärbäume iterativ speichern
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?
|
Re: Binärbäume iterativ speichern
*Schnipps* *Meld* *Meld*
Wozu benutzt man heutzutage noch Bäume? |
Re: Binärbäume iterativ speichern
Zitat:
|
Re: Binärbäume iterativ speichern
Zitat:
|
Re: Binärbäume iterativ speichern
Zitat:
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" |
Re: Binärbäume iterativ speichern
Liste der Anhänge anzeigen (Anzahl: 1)
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 :gruebel: Bis 10.000 Einträgen reicht a) (Variante 'THashedStringlist'), danach b) oder c). Im Anhang ein AVL-Unit |
Re: Binärbäume iterativ speichern
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) |
Re: Binärbäume iterativ speichern
Zitat:
Zitat:
Genauergesagt werden sie kaum langsamer, es ist egal, ob die Liste 1000 oder 100.000.000 Einträge umfasst. ![]() Verabschiede Dich also vom Irrglauben, Liste=lahm... |
Re: Binärbäume iterativ speichern
:shock:
Nich schlecht, diese Liste! Mal sehen, ob ich das noch ändere. Zu dem Suchen in meinem Baum: Da ich mit Zeichenketten arbeite und die (natürlich) in den tieferen Ebenen des Baumes immer änlicher werden und sich z.B. erst ab dem 30. Zeichen unterscheiden, speichere ich beim Erstellen immer die Position des Zeichens, an der der 1. Unterschied zum Vorgänger gefunden wird. Dadurch vermeide ich, dass immer wieder die gleichen Anfänge verglichen werden müssen. Beispiel: ![]() 99% aller Seiten auf deisem Server fangen mit diesem Präfix an. An der Stelle muss man sehen, ob sich die Skip-listen bewähren: weil sich der Vorgänger ändert(andern kann), muss man da immer voll vergleichen. Zu den Hash-Tabellen: da ich nicht weiß, wie groß des ding wird, habe ich mich für einen Baum entschieden. |
Re: Binärbäume iterativ speichern
Zitat:
Allerdings würde für deinen Fall ein DAWG bzw. Prefix-Trie noch besser sein. Das ist eine Struktur, die sich die von Dir beschriebene Redundanz (identische Stringanfänge) zu Nutze macht. Dadurch wird das Wörterbuch sehr kompakt und zweitens noch schneller. Ich meine, hier in der DP von Hagen (negaH) eine DAWG-Implementierung gefunden zu haben. |
Re: Binärbäume iterativ speichern
da muss man mal ausprobieren, was besser ist.
Beide basieren ja auf einer Baumstruktur und beide Verfahren haben ihre Vor und Nachteile. Allerdings wirds langsam Off-toppic. Da sollte man besser einen ergenen Thread für auf machen. Das iterative Speichern funktioniert ja bei beiden Ansätzen :wink: |
Re: Binärbäume iterativ speichern
Zitat:
Zitat:
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 16:42 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz