AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Gibt es einen schnelleren Stringvergleich als if S1 = S2
Thema durchsuchen
Ansicht
Themen-Optionen

Gibt es einen schnelleren Stringvergleich als if S1 = S2

Ein Thema von Bjoerk · begonnen am 15. Sep 2012 · letzter Beitrag vom 17. Sep 2012
Antwort Antwort
Seite 1 von 3  1 23      
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#1

Gibt es einen schnelleren Stringvergleich als if S1 = S2

  Alt 15. Sep 2012, 18:09
Sitz‘ grad mal wieder über einem meiner 88000 Parser. Dabei ist mal wieder bei mir die Frage aufgetaucht, ob es einen schnelleren Stringvergleich als if S1 = S2 gibt? Vermutlich nein, sonst wäre er in Delphi implementiert. Richtig?
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#2

AW: Gibt es einen schnelleren Stringvergleich als if S1 = S2

  Alt 15. Sep 2012, 18:32
Mittlerweile vielleicht. Es gibt ja die FastCode Challenge Site, wo sich Delphi z.T. bedient hat.

Der Vergleich zweier Strings kann eventuell durch folgende Heuristik schneller werden.
Vergleiche die Längen, dann das jeweils erste Zeichen und dann das jeweils letzte Zeichen. Nur wenn alle drei Vergleiche TRUE ergeben, vergleiche den Rest des Strings.

Ich denke aber, die Compare-Routinen sind schon optimiert
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#3

AW: Gibt es einen schnelleren Stringvergleich als if S1 = S2

  Alt 15. Sep 2012, 19:17
Genau so macht es Delphi, Zeichen für Zeichen.
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.624 Beiträge
 
Delphi 12 Athens
 
#4

AW: Gibt es einen schnelleren Stringvergleich als if S1 = S2

  Alt 15. Sep 2012, 19:29
Und bei AnsiCompareStr? AFAIK wird dort die API-Funktion CompareString mit den Spracheinstellungen des aktuellen Users aufgerufen, welche mit PChars arbeitet. Das dürfte schneller sein, kommt zumindest auf einen Versuch an.
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#5

AW: Gibt es einen schnelleren Stringvergleich als if S1 = S2

  Alt 15. Sep 2012, 19:34
Das dürfte schneller sein,
Warum
Intellekt ist das Verstehen von Wissen. Verstehen ist der wahre Pfad zu Einsicht. Einsicht ist der Schlüssel zu allem.
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#6

AW: Gibt es einen schnelleren Stringvergleich als if S1 = S2

  Alt 15. Sep 2012, 19:49
Und bei AnsiCompareStr? AFAIK wird dort die API-Funktion CompareString mit den Spracheinstellungen des aktuellen Users aufgerufen, welche mit PChars arbeitet. Das dürfte schneller sein, kommt zumindest auf einen Versuch an.
Leider nein.

Das ist (bis jetzt) am schnellsten:

Delphi-Quellcode:
function StrCompare(const S1, S2: string): boolean;
begin
  if Length(S1) <> Length(S2) then
    Result:= false
  else
    Result:= S1 = S2;
end;
  Mit Zitat antworten Zitat
Benutzerbild von sx2008
sx2008

Registriert seit: 16. Feb 2008
Ort: Baden-Württemberg
2.332 Beiträge
 
Delphi 2007 Professional
 
#7

AW: Gibt es einen schnelleren Stringvergleich als if S1 = S2

  Alt 15. Sep 2012, 19:53
Es ist ein Unterschied ob man nur wissen muss ob 2 Strings gleich sind oder wie z.B. bei AnsiCompareStr ob ein String kleiner, grösser oder gleich ist.
Daher ist if AnsiCompareStr(s1,s2)=0 then langsamer als if s1 = s2 then .

Hier sollte man sprachlich besonders präzise sein; will man vergleichen oder auf Gleichheit prüfen?
Delphi-Quellcode:
function StrEquals(const s1,s2:string):Boolean; // prüft ob zwei strings gleich sind
function StrCompare(const s1,s2:string):Integer; // 0=beide gleich, 1=s1 ist grösser, -1=s1 ist kleiner
Wenn man sich anschaut, wie ein AnsiString im Speicher liegt
http://www.codexterity.com/images/ansistring_layout.gif
dann muss man Folgendes tun:
1.) sind die beiden Zeiger s1 und s2 gleich? Falls ja: return(true)
2.) ist einer der beiden Zeiger = nil Falls ja: return(false)
3.) Längen der strings holen
4.) sind die Längen ungleich? Falls ja: return(false)
5.) Zeichen für Zeichen auf Gleichheit prüfen. Bei Abweichung return(false)
6.) return(true)

Wenn man die Punkte 1. bis 6. in Assembler ausprogrammiert erhält man die max. mögliche Geschwindigkeit.
Besonders bei 5. kann man z.B. durch schnellere CPU-Befehle SIMD, SSE,... noch einiges an Zeit rausholen.
  Mit Zitat antworten Zitat
Popov
(Gast)

n/a Beiträge
 
#8

AW: Gibt es einen schnelleren Stringvergleich als if S1 = S2

  Alt 15. Sep 2012, 20:10
Weil es mich auch interessiert hat, habe ich Furtbichlers Vorschlag getestet. Letztendlich dauert der Vergleich dann sogar länger, aber nur paar Millisekunden.

Hier das Beispiel zum überprüfen:

Delphi-Quellcode:
uses
  DateUtils;

procedure TForm1.Button1Click(Sender: TObject);
var
  i, k, m, c, x: Integer;
  t1, t2: TTime;
  s, s1, s2: String;
begin
  Screen.Cursor := crHourGlass;

  c := 0;
  Caption := '';

  t1 := Now;
  x := 10000000; // 10 Mio. Durchläufe
  for i := 1 to x do
  begin
    k := Random(MaxInt);
    m := Random(MaxInt);

    s1 := IntToStr(k); //die Hälfte der Strings sind gleich
    if Odd(i) then s2 := IntToStr(k) else s2 := IntToStr(m);

    //Direkt - Beispiel 1
    //if s1 = s2 then Inc(c);

    //Indirekt - Beispiel 2
    if Length(s1) = Length(s2) then
      if s1[1] = s2[1] then
        if s1[Length(s1)] = s2[Length(s2)] then
          if s1 = s2 then Inc(c);
  end;
  t2 := Now;

  Caption := Format('Gleich: %d von %d; Millisek.: %d', [c, x, MilliSecondsBetween(t1, t2)]);

  Screen.Cursor := crDefault;
end;

Geändert von Popov (15. Sep 2012 um 20:12 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

Registriert seit: 31. Mai 2009
1.198 Beiträge
 
Turbo Delphi für Win32
 
#9

AW: Gibt es einen schnelleren Stringvergleich als if S1 = S2

  Alt 15. Sep 2012, 23:03
Ne Frage nebenbei (jz nicht nur dies hier betreffend, sondern auch etwas allgemeiner):
Delphi-Quellcode:
    if Length(s1) = Length(s2) then
      if s1[1] = s2[1] then
        if s1[Length(s1)] = s2[Length(s2)] then
          if s1 = s2 then Inc(c);
Ist folgende Variante nicht schneller? Oder optimiert das Delphi allgemein genauso?
Delphi-Quellcode:
    len := Length(s1);
    if len = Length(s2) then
      if s1[1] = s2[1] then
        if s1[len] = s2[len] then // hier!
          if s1 = s2 then Inc(c);
Sry hab kB Delphi zu starten und zu disassemblieren. Vlt weiß es ja einer auf Anhieb.
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG
  Mit Zitat antworten Zitat
Popov
(Gast)

n/a Beiträge
 
#10

AW: Gibt es einen schnelleren Stringvergleich als if S1 = S2

  Alt 15. Sep 2012, 23:31
Nur etwas Statistik. Man sollte bedenken, dass auch der sonstige Code um die eigentlich Abfrage Zeit verbraucht. So werden 50 Mio. FOR Schleifen, abzüglich der IF Zeile oder Zeilen (je nach Beispiel) in meinem Rechner in 4820 Millisekunden abgewickelt.

Also

50. Mio Schleifen ohne IF Zeilen durchschnittlich in 4820 Millisekunden

50. Mio Schleifen mit einer IF Zeile (Bsp. 1) durchschnittlich in 5035 Millisekunden

50. Mio Schleifen mit vier IF Zeilen (Bsp. 2) durchschnittlich in 5060 Millisekunden

50. Mio Schleifen mit zwei IF Zeilen (Bsp. 3) durchschnittlich in 5020 Millisekunden
Delphi-Quellcode:
    //Bsp. 3
    if Length(s1) = Length(s2) then
      if s1 = s2 then Inc(c);
50. Mio Schleifen mit vier IF Zeilen (Aphtons Beispiel) durchschnittlich in 5035 Millisekunden


Wie man sieht werden etwas 50. Mio Vergleiche in ca. 200 Millisek. durchgeführt. Das macht 4 Nanosekunden pro Vergleich. Ich würde sagen, das die Funktion optimiert ist. Die Unterschiede zwischen den Beispielen sind eher marginal.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23      


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 12:26 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz