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 2 von 2     12
alzaimar
(Moderator)

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

Re: Binärbäume iterativ speichern

  Alt 5. Jul 2008, 13:14
Zitat von new32:
AVL-Bäume beruhen doch auf dem selben Prinzip.
Auch beim Einfügen wird ausgeglichen.
Zitat von new32:
Aber mein Baum fasst auch mehr als 1 Mio. Einträge!
Gerade dann werden Skiplisten Hashmaps viel schneller als Bäume. Bei 1 Mio Einträgen geschätzte 1000 mal schneller (kann auch mehr sein).
Genauergesagt werden sie kaum langsamer, es ist egal, ob die Liste 1000 oder 100.000.000 Einträge umfasst.
Hier habe ich einen Performancevergleich geschrieben...
Verabschiede Dich also vom Irrglauben, Liste=lahm...
"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
 
#12

Re: Binärbäume iterativ speichern

  Alt 5. Jul 2008, 14:49


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: http://de.wikipedia.org/wiki/...
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.
~?&/%§$§%\&?~
8)
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

Re: Binärbäume iterativ speichern

  Alt 5. Jul 2008, 15:22
Zitat von new32:
Zu den Hash-Tabellen: da ich nicht weiß, wie groß des ding wird, habe ich mich für einen Baum entschieden.
Die von mir implementierte Hashmap wächst dynamisch mit.

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.
"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
 
#14

Re: Binärbäume iterativ speichern

  Alt 5. Jul 2008, 15:36
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
~?&/%§$§%\&?~
8)
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

Re: Binärbäume iterativ speichern

  Alt 5. Jul 2008, 19:56
Zitat von new32:
da muss man mal ausprobieren, was besser ist.
Nee, muss man nicht.
Zitat von new32:
Allerdings wirds langsam Off-toppic.
Stimmt.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
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 20:32 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