Hallo,

habe den Hash von http://www.dev-center.de/header/hash mit der TStringList in Delphi 7 verglichen.

Getestet hab ich das ganze mit jeweils 1 Mio. Einträgen.

Erstellzeit der Einträge (Hash/Stringlist) in ms: ~1400 / ~800
Suchzeit nach 10000 Einträgen in ms: ~30 / ~ 60

Aufgerufen hab ich das ganze natürlich mehrere Male, die obigen Ergebnisse sind der ungefähre Mittelwert.

Jedenfalls unterscheiden sich die Ergebnisse in der Suche nicht allzu und bei der Erstellung ist die StringList erheblich schneller.

Woran liegst?

edit: die Werte bei Delphis THashedStringList sind ungefähr gleich der von TStringList.

_________________
offizieller DGL Compliance Beauftragter
Never run a changing system! (oder so)

Natürlich dauert das Befüllen eines Hashes länger als bei einer Stringliste. Wenn du bei einer Stringliste die Kapazität schon direkt auf die richtige Größe setzt, dann geht beim Befüllen einer Stringliste kaum mehr Zeit verlohren, da der Speicher die Liste intern nicht mehr umkopiert werden muss. Das sollte aber auch nicht so riesig ins Gewicht fallen. Bei einem Hash ist es aber so, dass die Einträge beim Hinzufügen nach einer mathematischen Formel verteilt werden. Wenn du dann darauf zugreifen möchtest, dann wird die gleiche Formel wieder angewendet und entsprechend weniger Einträge müssen durchsucht werden. Im Idealfall nur ein Einziger. Wärend bei einer Stringliste im schlimmsten Fall alle Einträge durchsucht werden müssen. Wenn die Liste sortiert ist kann man auch Binär suchen. Wodurch sich die Zeit erheblich verkürzen ließe. Allerdings muss die Stringliste aufwendig sortiert werden. Wenn sich die Daten recht oft ändern ist das nicht mehr sehr praktikabel.

Typischerweise ist es so, wenn du Einträge anhand eines Namens (String) identifizieren musst, dann ist ein Hash sinnvoller. Denn mit einer Liste müsstest du jeden Eintrag anfassen und überprüfen ob der Name der Gesuchte ist und wenn ja, dann dessen Assoziierten Wert zurückliefern. Wenn du aber wie ein Array darauf zugreifen möchtest, dann ist eine Liste wesentlich schneller, denn entweder gibt es den Eintrag 25071 oder eben nicht.

Pauschal lässt sich deine Frage nicht beantworten. Das kommt immer auf das Einsatzgebiet an. Zu mal mir die Bedingungen deines Test nicht ersichtlich sind. Entsprechend kann es sein, dass du ein Test gewählt hast bei dem ein Hash eh weniger gut abschneiden würde oder du etwas nicht berücksichtigt hast. Da wäre es also sinnvoll, wenn du noch ein paar Hintergrundinfos postest.

PS: Bei den Hashklassen gibt es auch eine Initialgröße die an den Konstruktor übergeben wurde. Sollte diese zu klein sein, dann arbeitet ein Hash auch nicht Effizient. Denn diese Größe sind die möglichen Felder auf denen die Einträge verteilt werden können. Hättest du nur 1 übergeben würden die Einträge alle hintereinander gehangen werden. Wodurch das Hash praktisch nutzlos wäre, da immer alle Einträge linear durchsucht werden müssen.

PPS: Ich darf wohl auch behaupten, dass die Hashklassen mit Sicherheit nicht die Effizientesten sind. Das war von mir nur mal ein Test. Für mich haben sie aber den Nutzen erfüllt.

PPPS: Delphi 7 hat einen grottigen Speichermanager. Da die Hashes sehr viele kleinteilige Speicherbereiche erzeugen dürfte der Speichermanager auch noch seinen Teil dazu beitragen, dass das Hash beim Befüllen länger benötigt. Da solltest du dir mal FastMM anschauen. Was sich wohl auch generell lohnen würde. Die Delphis nach Version 7 haben alle schon einen Speichermanager der wesentlich besser arbeitet als der von 7. Ich würde sogar behaupten, dass der ziemlich genau so arbeitet wie der von FastMM. Nur FastMM hat auch diverse Debugging Funktionen eingebaut. Was ein gutes Stichwort ist. Die solltest du beim Testen dann auch nicht aktivieren, da dass Speicherleck suchen auch seine Zeit in Anspruch nimmt.

Das Hashing-Verfahren aus der Unit ist verkettet, das ist ein gutes Verfahren und wesentlich besser als eine StringList, wenn man nach einem Eintrag sucht. Es summieren sich dabei allerdings die Zeiger, das heißt wenn Du wirklich extrem viele Einträge hast, dann wäre Doppeltes Hashing eventuell besser, da es weniger Speicher verbraucht. Nachteil von Doppeltem Hashing (Einfaches Hashing finde ich wegen Klumpenbildung uninteressant und lasse es direkt außen vor) ist, dass die Berechnung wieder aufwendiger wird, habe die Laufzeiten nicht mehr im Kopf, aber langsamer als Verkettetes Hashing ist es definitiv. Generell muss man für große Datenmengen immer noch bedenken, dass die Laufzeit absäuft wenn das Array zu voll wird, daher baut man in der Regel immer, wenn das Array halb voll ist, ein doppelt so großes. Ob man sich so etwas leisten kann hängt vom Einzelfall ab.

Aber was hast Du vor ? Eventuell ist eine Sortierung sinnvoll um dann eine schnelle Suche zu schaffen, eventuell aber nicht. Ohne zu wissen was Du machen willst kann man nur raten. Wenn Du alle Elemente betrachten musst, wirst Du mindestens lineare Laufzeit brauchen, wenn es sortiert werden kann, kannst Du mittels AVL-Baum auf logarithmische Laufzeit kommen, was schon extrem gut ist.

Zu Deinem Test: Je größer die Datenmenge desto mehr fällt das ins Gewicht, eventuell ist Dein Test zu klein. Laut Deinem Test ist die Suche mit Hashing doppelt so schnell wie die der StringList, finde das eigentlich schon deutlich genug.

_________________
Meine Musik: spiker-music.net

Wobei ich da schon fast sagen muss, dass ich das nicht deutlich genug finde. Gesetz den Fall, es handelt sich sich um Strings als Indexwerte. Dann würde ich bei einer normalen (unsortierten) Stringliste mit 1 Million Einträge, bei linearer Suche, wohl eher eine Laufzeit von mehreren 100 Millisekunden erwarten. Bei 10.000 Zugriffen würde ich etwas im Sekundenbereich auch nicht ausschließen wollen. Wobei man da bei dem Tests natürlich auch darauf achten muss, dass man auf die gleichen Einträge zugreift.

Mit Effizient meinte da im Speziellen die Berechnung der Arrayposition. Die ist ja ausschlaggebend dafür wie gut die Einträge verteilt werden. Wobei die Berechnung in der Unit ein SHL benutzt. Das sollte aber eigentlich asm ROL sein, da mit SHL gar nicht mal unschnell einige Werte einfach verlohren gehen. Speziell, wenn die Texte länger werden fließen die Zeichen links nicht mehr in die Berechnung ein.

hatte einen kleinen Fehler mit der Größe des Hashes eingebaut, jetzt lädt es genauso schnell wie die StringList und Suchen dauert 16ms.

Und hier der Code:

_________________
offizieller DGL Compliance Beauftragter
Never run a changing system! (oder so)

Du solltest bei den Stringlisten am Sinnvollsten auch immer IndexOf benutzen. Die Funktion Find funktioniert zwar auch. ABER verhindert erfolgreich, dass Optimierungen wie das Hash bei der THashedStringList eingesetzt werden können. Denn Find ist der letzte Rettungsanker der Listen um die Liste linear zu durchsuchen. Wenn die StringListe sortiert wäre, würde Find auch gar nicht eingesetzt werden. Sondern dann würde eine binäre Suche benutzt werden. Wenn du das auf IndexOf umstellst sollte die HashedStringList auch schon schneller sein. Weil aktuell wird sie nur als StringListe benutzt.

Wobei die THashedStringList im Konstruktor auch eine Größenangabe hat, die ziemlich genau so arbeitet wie bei meinem TStringHash. Wenn die zu klein ist, dann erhöhen sich auch die Kollisionen innerhalb des Hashes und damit die Anzahl der Einträge an der selben Stelle. Die dann letzten Endes wieder Linear durchsucht werden müssen.

Problem bei der HashedStringList ist aber, dass die bei dem ersten Zugriff mittels IndexOf das Hash erzeugt. Was dann höchstwahrscheinlich eine Weile dauert. Wenn die Liste verändert wurde, dann muss das komplette Hash leider neu erzeugt werden. Das hat Delphi wohl für Sinnvoll gehalten(??)

PS: Bei dem TStringHash sollte man als Größe auch eine Möglichst krumme (Primzahl) Größe benutzen. Das Schlimmste wären Potenzen von 2. Das liegt an der Berechnung des Hashes. Dadurch bekommt man eine bessere Verteilung (weniger Kollisionen) was den Suchaufwand minimiert. Hast du praktischer weise schon berücksichtigt. Aber ist auch nur als Hinweis gedacht. Die Geschwindigkeit des Hashes steht und fällt mit einer guten Verteilung. Das ist leider immer so ein Balanceakt zwischen Speicherverbrauch und möglicher verminderter Geschwindigkeit.