AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Object-Pascal / Delphi-Language Delphi Vergleich von Suchverfahren mit Beispielen

Vergleich von Suchverfahren mit Beispielen

Ein Thema von alzaimar · begonnen am 21. Okt 2005 · letzter Beitrag vom 18. Mär 2010
Antwort Antwort
Seite 2 von 5     12 34     Letzte » 
alzaimar
(Moderator)

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

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 10. Dez 2007, 15:16
Der B-Baum ist eine Mischung aus T-ärem Baum und Binary Search, wird also in der Performance irgendwo dazwischen sein.
Desweiteren ist der BB für Daten gedacht, die sich auf einem externen Datenträger befinden, und passt deshalb vom Konzept her hier nicht rein.

Ich vermute auch, das der Overhead etwas zu hoch ist, um mit reinen in-Memory-Lösungen mithalten zu können.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Dezipaitor

Registriert seit: 14. Apr 2003
Ort: Stuttgart
1.701 Beiträge
 
Delphi 7 Professional
 
#12

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 10. Dez 2007, 15:53
Die Suche/Einfügen/Löschen ist in einen B-Baum mit b-Einträge pro Knoten in schlechtesten Fall in O(b_log n) Schritten geschafft. Der B+ Baum hat sogar den Vorteil, dass nur die Blätter echte Daten enthalten und in einer linearen Liste verkettet sind, so dass eine Speicherung nur O(n) Speicherplatz braucht.

Dieses Video zeigt, wie ein B-Baum erstellt wird
http://youtube.com/watch?v=coRJrcIYbF4

Also warum sollte so ein Kunststück fehlen sollen?
Christian
Windows, Tokens, Access Control List, Dateisicherheit, Desktop, Vista Elevation?
Goto: JEDI API LIB & Windows Security Code Library (JWSCL)
  Mit Zitat antworten Zitat
Benutzerbild von mschaefer
mschaefer

Registriert seit: 4. Feb 2003
Ort: Hannover
1.999 Beiträge
 
Delphi XE3 Enterprise
 
#13

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 10. Dez 2007, 18:18
Zitat von Dezipaitor:
Also warum sollte so ein Kunststück fehlen sollen?
Ohne übermäßig zu Lästern würde ich es mal so beantworten: Weil Alzeimer vielleicht keine Zeit hat und Du es nicht umsetzen magst (kannst?).
Gib Ihm kein Viedeo sondern Deine Implementierung und er baut es bestimmt ein.
Aber ich gehe davon aus, dass er keine schnellere Variante sein wird (gerade in gut gecachten Rechnern).

Grüße // Martin
Martin Schaefer
Phaeno
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 10. Dez 2007, 18:37
Zitat von Dezipaitor:
Also warum sollte so ein Kunststück fehlen sollen?
Ich schrieb doch bereits, das das der Bayer-Baum nicht hier herein passt, da es sich nicht um eine generische Struktur bzw. Algorithmus zum schnellen Speichern von Assoziationen in-Memory handelt. Der Bayer-Baum wurde doch vor allen Dingen für Page-I/O entwickelt, daher die Seiten konstanter Größe.

Im Übrigen benötigt man doch kein Video, um einen Algorithmus zu verstehen. Ein gutes Buch reicht.

Wie wäre es, wenn Du, Dezipaitor, eine B*-Baum-Klasse implementierst und in den Testcode einpflegst? Ich behaupte immer noch, das der Overhead der Seitenverwaltung zu viel Performance klaut. Und gegen eine Hashmap, Skiplist oder einen Trie (DAWG) kommt der BB-Monolith eh nicht an. Natürlich lasse ich mich gerne eines Besseren belehren. Du kannst den Code von Julian Bucknall als Grundlage verwenden, er schwirrt in den Tiefen des WWW irgendwo herum.

Bei der Gelegenheit könnte man auch einen DAWG mit aufnehmen, nur frisst so eine Datenstruktur dermaßen viel Speicher, das sie den Test nicht besteht. Dafür wäre ein DAWG schneller als ne Hashmap.

Wie gesagt, es ging mir nicht um eine vollständige Liste von Listenstrukturen und deren Performancevergleich. Ich habe einen schnellen in-Memory-Cache für einen Interpreter benötigt, und da ging eben die Analyse los. Letztendlich bin ich bei der Hashmap hängengeblieben, aber nur deshalb, weil ich das Verfahren verstanden habe. Die Skiplist habe ich im Zusammenhang mit dem Sourcecode des MS SQL-Servers kennengelernt und wollte nur mal wissen, was ist. die AVL Bäume kenne ich noch aus meiner Studienzeit und -na ja- binary search lernt man in der Schule.

@mkinzler: Ich hab hier irgendwo eine B-Tree-Klasse rumliegen, aber wozu soll ich die einbauen (s.o.)? Wer will, kann das gerne selbst machen. Ich hab doch nicht das Monopol auf die Testumgebung.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
abrosda

Registriert seit: 10. Dez 2007
6 Beiträge
 
Delphi 7 Architect
 
#15

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 11. Dez 2007, 08:06
Ich werd' mal sehen, ob ich vor Weihnachten ein bischen Zeit an meinem Rechner zu Hause habe und dann noch ein paar Algorhithmen hinzufügen. Interessant ist ein Vergleich zwischen den Stringvergleichen und Integervergleichen...
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 11. Dez 2007, 08:24
Zitat von abrosda:
Interessant ist ein Vergleich zwischen den Stringvergleichen und Integervergleichen...
Yo, gute Idee.

Vermutlich wird die Hashmap ggü. der Skiplist besser abschneiden, da bei der Hashmap (=Dictionary) der String per Hash-Funktion in einen Integer umgewandelt wird. Anschließend finden (fast) nur noch Integer-Vergleiche statt.

In allen anderen Strukturen wird dagegen der zu suchende Text stehts mit einem Schlüssel verglichen.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
mquadrat

Registriert seit: 13. Feb 2004
1.113 Beiträge
 
Delphi XE2 Professional
 
#17

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 16. Jan 2009, 12:57
So, ich hab jetzt auch mal ein bisschen mit den Listen rumgespielt. Für den ein oder anderen vielleicht interessant: Wenn man bei der THashedStringlist die Sortierung weg lässt kann man für kleinere Datenmengen nochmal Geschwindigkeit rauskitzeln. Erst ab 50.000 Einträgen wird das Suchen extrem langsamer. Davor ist zwischen sortierten und unsortierten THashStringlists kaum ein Unterschied beim Suchen.
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 16. Jan 2009, 21:08
Das ist interessant! Hast Du deine Optimierung mal in die Teststruktur eingepflegt, sodaß man unmittelbar einen Vergleich mit den anderen Datenstrukturen ziehen kann?

Immer wieder wichtig ist zu wissen, ob und wie eine Datenstruktur skalierbar ist, ob sie also auch bei exorbitanten Datenmengen noch performant ist. Wenn man es braucht.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von Luckie
Luckie
(Moderator)
Online

Registriert seit: 29. Mai 2002
37.300 Beiträge
 
Delphi 2006 Professional
 
#19

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 16. Jan 2009, 21:29
@alzaimar: Wenn du alles zusammen hast, mach doch daraus ein Tutorial und poste es in der Tutorialsparte.
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
Oreaden

Registriert seit: 10. Nov 2008
60 Beiträge
 
#20

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 17. Jan 2009, 07:25
@Luckie: Feine Idee ein Tutorial zum Thema, wie erstelle ich eine Testumgebung

Hab da noch nichts gefunden und meine Kristallkugel läßt mich zu diesem Thema auch in Stich

Schöne Grüße
OREADEN
  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 10:55 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf