AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Object-Pascal / Delphi-Language Delphi Große Strings schnell auf Inhalt einer Zeichenkette prüfen?

Große Strings schnell auf Inhalt einer Zeichenkette prüfen?

Ein Thema von romber · begonnen am 17. Okt 2005 · letzter Beitrag vom 19. Apr 2006
Antwort Antwort
Seite 3 von 3     123
Benutzerbild von himitsu
himitsu
Online

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
38.962 Beiträge
 
Delphi 10.4 Sydney
 
#21

Re: Große Strings schnell auf Inhalt einer Zeichenkette prüf

  Alt 22. Okt 2005, 19:18
Zitat von alzaimar:
CRC16 geht doch nur bis max. 65536 Elemente. Was ist bei 10.000.000 Elementen?
Ist mir wohl bekannt.

Nur hast du in deinem "Beispielchen" doch einen größeren Hash mittels "mod 1000" in einen Kleineren gesplittet.

Wozu also erst einen Größeren Wert (was meist auch noch rechenaufwendiger ist) erstelen, wenn dieser dann eh in 'nen Kleineren umgewandelt wird?

Und in diesem Vergleich ist CRC16 also schneller und hat immernich einen Größeren Werteumfang, als die mit "mod 1000" erstellten 1000 verschiedenen Werte.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

Re: Große Strings schnell auf Inhalt einer Zeichenkette prüf

  Alt 22. Okt 2005, 19:53
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.
[edit] Und die Berechnung von CRC32 ist auch nicht langsamer, als CRC16. [/edit] 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 Compilern Verwendung findet. Ich hatte mal ELF und PJW verglichen, bin dann bei ELF hängengeblieben.

Also nochmal (auf die Gefahr hin, das Dich das nervt):
Ich berechne einen 32bit-Hash zu dem einzufügenden Schlüssel. Damit bin ich, was die maximale Größe der Liste anbelangt, auf der Sicheren Seite. Bevor ich die aber gleich so gross mache, fange ich ganz klein an, nämlich bei 1000 (genauergesagt 997, weil Primzahl) an. Wenn die Liste langsam voll wird, muss ich sie vergrößern. Ich verdopple also die Größe, such mir die nächstbeste Primzahl und dass ist dann die neue Listengröße. Natürlich muss ich einmalig alle bereits in der Liste gespeicherten Elemente nochmals in die neue, größere Liste einfügen, da sich ja die Hashfunktion (ELF mod ListSize) verändert hat. Ich dachte zuerst, dass damit die Performance flöten geht, aber nee. Ausserdem kommt das 'Rehashing' sehr selten vor, bei 2^32 einzufügenden Elementen passiert das ja nur 20 mal, oder so.

Ich verwende Stringlisten derzeit nur noch ihrem Zweck (LISTEN) entsprechend. Wenn ich aber nach Strings suchen muss, geht nix über eine Hash-Tabelle (oder gleich eine DB). Na gut, die Skiplist ist für kleinere (<40.000) Elemente noch etwas besser, aber ich mag die Stringdictionaries nun mal. Vielleicht, weil ich sie mir selbst gebastelt habe.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
shadowman

Registriert seit: 1. Nov 2005
48 Beiträge
 
#23

Re: Große Strings schnell auf Inhalt einer Zeichenkette prüf

  Alt 14. Apr 2006, 16:47
Hallo zusammen,
wie benutzt man diese Hash-Tabellen (TStringDictionary) denn? Ist von der Handhabung her anders als TStringList, oder? Ich komme damit irgendwie nicht zurecht. Z.B. weiß ich nicht, wie ich auf einzelne Zeilen zugreifen kann und deren Inhalt.
Mit TStringListe konnte man das mit Liste.Strings[Index] zugreifen. Mit TStringDictionary geht das z.B. nicht usw.

Hier stand irgendwo, dass ein kleines Beispiel-Projekt per Mail geschickt wurde. Könnte jemand (alzaimar ?) vielleicht ein Beispiel hier posten, damit alle was davon haben? Wie man das Ganze nutzt:
- Einträge "richtig" einfügt (falls da was zu beachten gibt)
- durchläuft
- auf bestimmte Einträge/Zeilen zugreift usw.
- ...

Wäre sehr nett.

Gruß und frohe Ostern Euch!
shadow
  Mit Zitat antworten Zitat
Elvis

Registriert seit: 25. Nov 2005
Ort: München
1.902 Beiträge
 
Delphi 2010 Professional
 
#24

Re: Große Strings schnell auf Inhalt einer Zeichenkette prüf

  Alt 14. Apr 2006, 17:07
Schaue mal hier vorbei. (Beitrag 6)
Funktioniert für Strings fast genau wie für Integers.
Robert Giesecke
I’m a great believer in “Occam’s Razor,” the principle which says:
“If you say something complicated, I’ll slit your throat.”
  Mit Zitat antworten Zitat
shadowman

Registriert seit: 1. Nov 2005
48 Beiträge
 
#25

Re: Große Strings schnell auf Inhalt einer Zeichenkette prüf

  Alt 15. Apr 2006, 10:58
Hallo Elvis,
danke sehr für die Antwort und den HInweis, allerdings bin ich dadurch nicht so richtig schlauer geworden

Delphi-Quellcode:
Var
   Liste: TStringDictionary;
   i: integer;
begin
   Liste := TStringDictionary.Create;

   for i := 0 to 99 do begin
      Liste.Add('Mustertext' + IntToStr(i), nil); // mit nil geht es schon los.. wieso, weshalb, warum?
   end;

   // wie gehe ich nun z.b. zu der Zeile 77 und zeige mir diese an oder mache damit irgendwas?
   // bei einer StringList wäre es: ShowMessage(Liste.Strings[77]);
   // wie ist das bei der HashListe?
   
end;

Gruß,
shadow
  Mit Zitat antworten Zitat
Elvis

Registriert seit: 25. Nov 2005
Ort: München
1.902 Beiträge
 
Delphi 2010 Professional
 
#26

Re: Große Strings schnell auf Inhalt einer Zeichenkette prüf

  Alt 15. Apr 2006, 11:10
Du hast anscheinend nicht gelesen wie alzaimar versucht hat, himitsu Dictionaries zu erklären...

Man benutzt ein Dictionary NICHT als normalen Datencontainer. Wie der Name schon sagt ist es zum Nachschlagen da...
Robert Giesecke
I’m a great believer in “Occam’s Razor,” the principle which says:
“If you say something complicated, I’ll slit your throat.”
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

Re: Große Strings schnell auf Inhalt einer Zeichenkette prüf

  Alt 19. Apr 2006, 10:01
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 auszuschließen. Dann speichere ich einfach Nichts (oder Nil) zu dem Wort. Wenn ich wissen will, ob ich ein 'Wort' schon einmal gespeichert habe, kann ich nun einfach im Wörterbuch nachschauen, ob das Wort drinsteht. Nur wenn es nicht drinsteht, füge ich es ein (denn dann hab ich es ja wohl vorher noch nicht gesehen). Man verwendet Hashtabellen z.B. beim Parsen. Im 'Procedure'-Wörterbuch kann ich sicherstellen dass erstens eine Prozedur nicht 2x implementiert und zweitens eine Prozedur definiert wird, bevor sie aufgerufen wird.

Der fundamentale Unterschied zwischen einer Liste und einem Wörterbuch ist die beim Wörterbuch fehlende Möglichkeit, die enthaltenen Daten aufzulisten, womöglich auch noch sortiert. Man kann natürlich alle Daten durchiterieren, das hat die von mir entwickelte Klasse, aber das ist eine -im Vergleich zur Liste- relativ lahme Krücke. Dafür ist sie beim Einfügen und Suchen verdammt schnell.

In einer Hashtabelle ist es egal, ob 100 oder 100.000.000 Wörter gespeichert sind: Die Suche geht immer gleich schnell. Bei einer Liste warte ich mir bei 100.000.000 Elementen einen Wolf
"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 13:45 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf