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 1 von 5  1 23     Letzte » 
alzaimar
(Moderator)

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

Vergleich von Suchverfahren mit Beispielen

  Alt 21. Okt 2005, 19:55
In Anbetracht der häufig gestellten Fragen nach 'Suchen in einer Liste' und Ähnlichem hab ich mal vier Verfahren verglichen:
- Stringlist
- AVL-Baum
- Skiplist
- Hashlist

Das Testprogramm fügt zunächst Werte in die jeweilige Datenstruktur ein und sucht sie anschließend wieder. Beim Einfügen wird sichergestellt, das der Eintrag nicht schon in der Liste ist.

Ich würde mich freuen, wenn Jemand einen schnelleren Algorithmus/Datenstruktur findet oder die vorhandenen verbessert. Falls jemand andere schnelle Verfahren hat, dann kann er sie hier posten bzw. das Testprogramm erweitern.

[edit] Update: Auf Nachfrage wurde die THashedStringList aus IniFiles von Borland mit aufgenommen. Neu ist auch, das man angeben kann, ab welcher Dauer eine Reihe während des Messlaufes nicht weiter verfolgt werden soll. Das Laufzeitverhalten einiger Listen degeneriert bei grossen N. Wenn also die Messung des Einfügens einen bestimmten Wert, wird das Verfahren nicht weiter berücksichtigt: Damit man sich keinen Wolf wartet [/edit]

[edit] Update: THashedStringlist wurde mit 'Sorted := True' instantiiert und dadurch unnötig langsam[/edit]
Angehängte Dateien
Dateityp: zip testlists_126.zip (318,6 KB, 470x aufgerufen)
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.509 Beiträge
 
#2

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 21. Okt 2005, 21:58
Nett .. wenn du jetzt nochmal die Verfahren kurz erklären würdest (Dictionary = Stringlist ???)

Was mir aufgefallen ist: Warum hat die blaue Kurve so Zacken, als wäre sie z.B. mit 500.000 langsamer als mit 1.000.000 ?
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 21. Okt 2005, 22:55
Stringlist= Delphi TStringlist mit Sorted := True und Duplicates := dupIgnore, Suchen per binary search
AVL - Tree: AVL-Baum (Binärer ausgeglichener Baum)
Skiplisten: Verkettete Listen mit zusätzlichen Pointern auf weiter entfernte Elemente (Skip list)
Directories : Hash tabellen (Nein. Nicht zum Rauchen)

Zitat von jfheins:
Was mir aufgefallen ist: Warum hat die blaue Kurve so Zacken, als wäre sie z.B. mit 500.000 langsamer als mit 1.000.000 ?
Wenn Hashtabellen voll sind, werden sie erweitert. Due Größe der vergrößerten Tabelle eine Primzahl, die ungefähr doppelt so gross ist, wie die ursprüngliche Tabelle. Es scheinen 'gute' und 'schlechte' Größen zu geben. Einige sind 'mies'. Warum das so ist, weiss ich nicht.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Der_Unwissende

Registriert seit: 13. Dez 2003
Ort: Berlin
1.756 Beiträge
 
#4

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 22. Okt 2005, 17:44
Hey,
was ich ein wenig vermisse ist die gute THashedStringlist. Gab es da einen guten Grund sie nicht mit zu berücksichtigen? Also sonst würde mich die auch noch in deinem Test interessieren, zumal die echt gut schneller ist als die TStringlist und ich würde mal denken, dass da Borland für sorgt, dass immer gute Werte für's Hashen benutzt werden.
Ansonsten nettes Programm!

Gruß Der Unwissende
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 22. Okt 2005, 18:33
Hi,
Danke für den Tip. Ich hab sie mal eingebaut Im 1.Posting kann man die neue Version laden. Sie misst nun auch nur das Suchen.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von stoxx
stoxx

Registriert seit: 13. Aug 2003
1.111 Beiträge
 
#6

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 9. Dez 2005, 18:05
zu den Skiplisten ... hier eine richtig geile Seite mit Vorlesungs Videos !
wow .. da tut sich was an den Unis

http://electures.informatik.uni-frei...2004&chapter=7
Phantasie ist etwas, was sich manche Leute gar nicht vorstellen können.
  Mit Zitat antworten Zitat
Benutzerbild von mschaefer
mschaefer

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

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 6. Aug 2007, 10:03
Moin, moin,

Das ist eine schöne Gegenüberstellung, die einem
viel Arbeit in die falsche Richtung ersparen kann.

Grüße nach Berlin
Martin Schaefer
Phaeno
  Mit Zitat antworten Zitat
hathor
(Gast)

n/a Beiträge
 
#8

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 24. Okt 2007, 21:17
Hi,

Dictionary ist deutlich am Besten!

Kennt jemand die Media Library von WINAMP?
Da gibt es MAIN.IDX und MAIN.DAT (und einige andere) - gibt es einen DELPHI-Sourcecode, mit dem man auf die Datenbank zugreifen kann?
Mit welchem Datenbankmodell ist sie vergleichbar?

Danke für jede Hilfe!
  Mit Zitat antworten Zitat
abrosda

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

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 10. Dez 2007, 14:02
Der AVL Tree wird erheblich schneller, wenn nicht jedesmal vor dem einfügen geprüft wird, ob der Key schon im Baum vorhanden ist.
Das setzt natürlich eindeutige Werte voraus.
  Mit Zitat antworten Zitat
Dezipaitor

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

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 10. Dez 2007, 14:20
wo ist der B(*/+)-Baum ?
Christian
Windows, Tokens, Access Control List, Dateisicherheit, Desktop, Vista Elevation?
Goto: JEDI API LIB & Windows Security Code Library (JWSCL)
  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 09:58 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