Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
19. Apr 2006
Ahoj,
zurück aus dem Osterurlaub!
Eine Dictionary ist ein Wörterbuch. In einem Wörterbuch ist zu einem bestimmten Wort etwas hinterlegt, z.b. eine Erklärung, eine Übersetzung oder ein Bild.
Ich kann Wörterbücher also dazu verwenden, um zu einem Schlüssel irgendwelche Informationen zu speichern. Ich kann ein Wörterbuch aber auch dazu verwenden, um doppelte Vorkommen eines Schlüssels...
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
22. Okt 2005
Meine Hashtabelle vergrößert sich doch dynamisch.
Ich hatte ursprünglich auch den CRC16 drin, bis ich meine StringDictionary für mehr als 655536 Elemente brauchte. Also den CRC32.
Und die Berechnung von CRC32 ist auch nicht langsamer, als CRC16. Dann habe ich noch recherchiert und, siehe da, es geht noch schneller: Ich habe den 'ELF'-Hash verwendet, daneben gibt es noch den 'Pjw', der in...
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
22. Okt 2005
Ich habe sie getestet, bringt in diesem Fall nur bis <20.000 etwas, dann ist sie beim Suchen besser als eine normale Stringlist.
Ich verweise mal auf meinen Thread, indem diverse Listen verglichen werden. Ich baue die mal da ein.
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
22. Okt 2005
CRC16 geht doch nur bis max. 65536 Elemente. Was ist bei 10.000.000 Elementen?
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
21. Okt 2005
himitsu: Nee :zwinker:
KeyToHash ('Müller') ---> 12345. Unsere Liste hat genau 1000 Elemente, also 12345 mod 1000 = 345.
Also ist der Record zu 'Müller' in Hash. Da is nix mit Suchen! Wie gesagt, wenn KeyToHash('Meier')=22345 ergibt (mod 1000 = 2345!), dann haben wir hier ein Problem = Kollision, da muss man sich dann was ausdenken. Warte einfach ne Stunde, dann poste ich meinen Vergleich....
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
21. Okt 2005
Man muss unterscheiden zwischen einer Hashliste, was eine Datenstruktur ist, und einer Liste von Hashes, was einfach eine Liste von Abkürzungen für irgendwelche Dingsels ist. Z.B. kannst du eine Liste von Hashwerten aller Dateien nehmen.
Hier ist aber eine Hashliste, Assoziativ-Array, Dictionary gemeint.
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
21. Okt 2005
Alles ist relativ.
Bei einer Hashliste dauert das Suchen in 100.000.000 Elementen genauso lang, wie das Suchen in einer Liste mit 1.000 Elementen. Mit Binary seach ist das Verhältnis 3:1 na, nun.
Das EINFÜGEN (denn die Elemente müssen ja erstmal rein) dauert bei Hashlisten von 100.000.000 Elementen für das letzte Element genau so lang, wie für das erste. Bei einer sortierten Liste ist das...
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
17. Okt 2005
Auch da sind Hashlisten einfach schneller. Ein TIntegerDictionary ist im geposteten Sourcecode enthalten. Er ist gegenüber einer TList, Sortieren und Binarysearch auch um den schon erwähnten Faktor schneller.
Das 'Suchen' von Daten sollte und muss keine Zeit kosten. Natürlich immer relativ. Bei 100.000.000.000 Datensätzen darf das Suchen ruhig mal mal 100ms dauern, da doch einige...
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
17. Okt 2005
Wenn Du statt einer Stringlist einfach einen String nimmst (und nicht einfach sl.Text verwenden, weil lahm), dann sollte Boyer-Moore deinen Anforderungen genügen. Wenn der String nur am Anfang einer Zeile stehen kann, wäre eventuell eine individueller Algorithmus schneller. Allerdings berücksichtigt Boyer-Moore auch diesen Sonderfall (man sucht dann einfach nach "#10#13FooBar").
Besorge Dir...