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 1 von 3  1 23   
romber

Registriert seit: 15. Apr 2004
Ort: Köln
1.163 Beiträge
 
Delphi 10 Seattle Professional
 
#1

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

  Alt 17. Okt 2005, 17:22
Hallo!

Gibt es eine ressourcenschönende schnelle Methode, sehr große Strings (wie in meinem Fall eine TStringList mit über 250.000 ziemlich langen Einträgen) auf Existenz einer bestimmten Zeichenkette zu prüfen? Mit pos geht das zwar auch, so richtig schnell ist das aber nicht.

Danke!
  Mit Zitat antworten Zitat
Benutzerbild von SirThornberry
SirThornberry
(Moderator)

Registriert seit: 23. Sep 2003
Ort: Bockwen
12.235 Beiträge
 
Delphi 2006 Professional
 
#2

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

  Alt 17. Okt 2005, 17:48
also pos ist bereits in assembler programmiert und is somit wohl nur sehr schwer noch zu optimieren (wenn überhaupt möglich). Wie genau verwendest du es in Zusammenhang mit einer Stringlist? Suchst du in der Stringlist nach kompletten Einträgen? Wenn du suchst welcher Index in der Stringlist mit einer bestimmten zeischenkette los geht hilft es schon die Stringlist zu sortieren und dann den algorythmus darauf anzupassen, ansonsten wenn es darum geht einen teilstring an beliebiger Stelle zu finden dann bleibt nur übrig das du alle items der Stringliste durchgehst und das dauert nunmal lange..
Jens
Mit Source ist es wie mit Kunst - Hauptsache der Künstler versteht's
  Mit Zitat antworten Zitat
romber

Registriert seit: 15. Apr 2004
Ort: Köln
1.163 Beiträge
 
Delphi 10 Seattle Professional
 
#3

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

  Alt 17. Okt 2005, 18:09
Danke für schnelle Antwort!

Ich habe Einträge, die aus Zahlen bestehen. Hier ein kleiner Abschnitt des Inhaltes:

...
33670903
33670905
33670899
33670911
33670915
33670904
33670919
33670920
33670912
33670916
33670921
33670918
...

Mann kann da erkennen, dass die Zahlen immer höher werden, aber nicht immer in der richtigen Reihenfolge sind. Ich möchte eigentlich nur sehr schnell prüfen, ob der eintrag bereits in der Liste ist, bevor ich diesen hinzufüge. Kann man da was optimieren?
  Mit Zitat antworten Zitat
Benutzerbild von Ultimator
Ultimator

Registriert seit: 17. Feb 2004
Ort: Coburg
1.860 Beiträge
 
FreePascal / Lazarus
 
#4

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

  Alt 17. Okt 2005, 18:12
Und wenn du mit Delphi-Referenz durchsuchenIndexOf hergehst, und den zurückgegebenen Index auf -1 überprüfst?
Julian J. Pracht
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

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

  Alt 17. Okt 2005, 18:34
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 FastStrings.Pas von hier
http://www.droopyeyes.com/default.as...owProduct&ID=4

Alternativ empfehle ich mein TStringDictionary, eine dynamische Hashliste. Es fügt 100.000 Strings inkl. überprüfung in 600ms ein. TStringList ist 2-100x langsamer (je mehr Strings, desto schlimmer). Dafür verzichtest Du auf eine Sortierung. Wenn Dir das schnurz ist, verwende mein Wörterbuch.
Angehängte Dateien
Dateityp: pas csdictionary_200.pas (11,1 KB, 80x 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 SirThornberry
SirThornberry
(Moderator)

Registriert seit: 23. Sep 2003
Ort: Bockwen
12.235 Beiträge
 
Delphi 2006 Professional
 
#6

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

  Alt 17. Okt 2005, 18:34
wenn es nur zahlen sind würde ich nicht die Stringlist nehmen sondern direkt TList und anstelle von Pointern deine Integer da rein hängen (casten). Dann das ganze noch sortieren und dann solltest du mit dem Quicksortalgorythmus recht schnell herausfinden ob der Eintrag schon vorhanden ist. Falls du bei der Stringlist bleibst so ist dort Sorted schon implementiert und auch IndexOf.
Wenn sorted auf True ist und "duplicates" auf "dubExcept" so bekommst du einen Fehler wenn du einen vorhandenen Eintrag adden willst (das ganze in Try-Except) und du solltest recht schnell fertig sein.
Jens
Mit Source ist es wie mit Kunst - Hauptsache der Künstler versteht's
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

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

  Alt 17. Okt 2005, 19:06
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 Festplattenzugriffe nötig sind (bei einem B-Baum wären das ca. 3 Zugriffe a 8kb). Bei bis zu 10.000.000 Datensätzen, die ich ohne Probleme im Speicher halten kann, ist eine Hashliste optimal
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
romber

Registriert seit: 15. Apr 2004
Ort: Köln
1.163 Beiträge
 
Delphi 10 Seattle Professional
 
#8

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

  Alt 20. Okt 2005, 22:56
Ich wollte die vom Alzaimar entwickelte TIntegerDictionary probieren und habe ihn um einen Beispiel gebeten. Er hat mir die Beispielcode und die bereits erstellte EXE-Datei geshickt. Wenn man die Datei ausführt, wird in einem Memo-Feld angezeigt, wie lange den Suchprocess gedauert hat. Und das geht wirklich verdammt schnell. Ich habe jetzt aber ein anderes Problem: sobald ich die Code ins Delphi lade und ohne etwas zu ändern von dort ausführe, wird das Programm um fast deppelt langsammer! Woran liegt das?
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

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

  Alt 21. Okt 2005, 10:15
Führe dein Programm mal ohne Debugger aus ... also nicht direkt vom Delphi aus.
Der Debugger bremst ein wenig.

Ich hatte z.B. mal den Fall, daß ein reiner ASM-Code im Debugger mindestens 20-mal Langsamer ablief, als ohne.





Du könntest eventuell auch mal nach meinem SearchSameFiles (unter Open Source) suchen, dort werden zwar Dateien verglichen, aber man kann den Code auch leicht dahingehend verändern, daß da Strings verglichen werden.

Es wäre zumindestens ein "nettes" Beispiel für dich.

Dort wird mit 'ner Hashliste gearbeitet und bei gleichem Hash sicherheitshalber nochmals die Dateien(oder Strings) verglichen und da die Hashs nicht sortiert sind gibt es noch 'ne abgeänderte Pos-Funktion zum suchen eines Hashs.

PS: wunder dich aber nicht, wenn sich das Programm so nicht compilieren läßt ... dir fehlen da bestimmt noch ein paar Dateien eines anderen Projekts, aber wenn nötig kann ich dir ja die entsprechenden Funktionen/Proceduren noch zukommen lassen (und einige davon sind auch schon in der DP veröffentlicht)
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
Benutzerbild von sniper_w
sniper_w

Registriert seit: 11. Dez 2004
Ort: Wien, Österriech
893 Beiträge
 
Delphi 6 Enterprise
 
#10

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

  Alt 21. Okt 2005, 11:33
Bei einer Sortierte Liste ist Binary Search seeeehr schnel....
Man braucht maximal 32 mal abzufragen in einer List von 2^32 Beiträgen um eine richtige Antwort zu bekommen. Da sollte es Geschwindigkeitsvorteile schon geben...

google.com
Katura Haris
Es (ein gutes Wort) ist wie ein guter Baum, dessen Wurzel fest ist und dessen Zweige in den Himmel reichen.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23   

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:32 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