Prüfen, ob ein String einen Interger darstellt.

Für Fragen zur Programmiersprache auf welcher Lazarus aufbaut
Warf
Beiträge: 1480
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Prüfen, ob ein String einen Interger darstellt.

Beitrag von Warf »

Ich hab einfach mal ein bisschen gebenchmarkt:

Eine eigene Implementation:

Code: Alles auswählen

function isIntLoop(s: String): Boolean; inline;
var
  i: Integer;
begin
  Result := Length(s) > 0;
  for i:=1 to Length(s) do
    if not (s[i] in ['0'..'9']) then
      exit(False);
end;   

Braucht auf O3 etwa nur die hälfte (und 60% auf O1) der Zeit von Val:

Code: Alles auswählen

function isIntVal(s: String): Boolean; inline;
var dummy: Integer;
  code: Word;
begin
  val(s, dummy, code);
  Result := code = 0;
end;     


Also deutlich effizienter. Der Grund dafür ist das val effektiv mehr macht. Val konvertiert strings zu Integers und gibt nur zurück ob es gefailed hat. Die konvertierung ist natürlich deutlich komplizierter, da sie schlicht weg mehr macht:

Code: Alles auswählen

function strToIntExample(s: String): Integer;
var
  i: Integer;
begin
  if Length(s) = 0 then error;
  Result := 0;
  for i:=1 to Length(s) do
  begin
    Result *= 10;
    if (s[i] in ['0'..'9']) then
      Result += ord(s[i]) - ord('0')
    else
      error
  end;
end;


Dementsprechend sind Funktionen wie TryStrToInt oder auch StrToIntDef langsamer als eine hand geschriebene funktion, denn sie führen code aus den man schlicht weg nicht braucht.
Würde man LLVM als backend benutzen könnte der Optimizer wahrscheinlich bei Whole-Program optimization feststellen das das ergebnis von val nicht verwendet wird und dieses wegoptimieren (sodass man dann bei der selben funktionaltiät wie die handgeschriebene funktion endet), allerdings ist der FPC Optimizer nicht so gut wie LLVM, weshalb dieser unterschied zu stande kommt.

Was mir dabei auch aufgefallen ist, ein For-in loop ist deutlich langsamer als ein For-i loop. also mein beispiel von oben

Code: Alles auswählen

function IsInteger(s: string): boolean; inline;
var
  c: char;
begin
  Result := s.length > 0;
  for c in s do
    if not (c in ['0'..'9']) then
      exit(False); // oder Result := False; und break;
end;


braucht etwa 40% länger als die selbe funktion mit nem For-I loop. Das ist äußerst interresant, weil in C++ ein For-Each mit Iterator nach dem Optimieren (mit LLVM oder auch mit GCC) tatsächlich den selben assembly erzeugt wie ein For-I loop nach dem optimieren. Daran erkennt man auch mal wieder das der FPC nicht so gut im optimieren ist wie vergleichbare C++ compiler.
Da die meisten Pascal programme allerdings nicht auf optimale performance aus sind, ist das meist kein Problem, sollte man nur im Hinterkopf behalten, das sich der FPC nicht so sehr für performance kritische anwendungen eignet

Programm:

Code: Alles auswählen

program Project1;
 
{$mode objfpc}{$H+}
 
uses
  LCLIntf;
 
 
type TStringArray = array of String;
type TBooleanArray = array of Boolean;
 
function GenRandomString: String;
var
  len, i: integer;
begin
  len := Random(4) + 2;
  SetLength(Result, len);
  for i:=1 to len do
    Result[i] := chr(Random(15) + ord('0'));
end;
 
function GenRandomStrings(n: Integer): TStringArray;
var
  i: Integer;
begin
  SetLength(Result, n);
  for i:=0 to n-1 do
    Result[i] := GenRandomString;
end;
 
function isIntVal(s: String): Boolean; inline;
var dummy: Integer;
  code: Word;
begin
  val(s, dummy, code);
  Result := code = 0;
end;
 
function isIntLoop(s: String): Boolean; inline;
var
  i: Integer;
begin
  Result := Length(s) > 0;
  for i:=1 to Length(s) do
    if not (s[i] in ['0'..'9']) then
      exit(False);
end;
 
var
  arr: TStringArray;
  valResults: TBooleanArray;
  loopResults: TBooleanArray;
  start: Cardinal;
  valTime, loopTime: Cardinal;
  i: Integer;
begin
  Randomize;
  arr := GenRandomStrings(10000000);
  SetLength(valResults, Length(Arr));
  SetLength(loopResults, Length(Arr));
 
  start := GetTickCount;
  for i:=0 to Length(arr) -1 do
    loopResults[i] := isIntLoop(arr[i]);
  loopTime := GetTickCount-start;
 
  start := GetTickCount;
  for i:=0 to Length(arr) -1 do
    valResults[i] := isIntVal(arr[i]);
  valTime := GetTickCount-start;
  WriteLn('Val: ',  valTime);
  WriteLn('loop: ',  loopTime);
end.
 

Socke
Lazarusforum e. V.
Beiträge: 2780
Registriert: Di 22. Jul 2008, 19:27
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 10/Linux/Raspbian/openSUSE
CPU-Target: 32bit x86 armhf
Wohnort: Köln
Kontaktdaten:

Re: Prüfen, ob ein String einen Interger darstellt.

Beitrag von Socke »

Warf hat geschrieben:Der Grund dafür ist das val effektiv mehr macht. Val konvertiert strings zu Integers und gibt nur zurück ob es gefailed hat. Die konvertierung ist natürlich deutlich komplizierter, da sie schlicht weg mehr macht:

val kann insbesondere auch Hexadezimal ($) und Binärzahlen (%) verarbeiten.
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein

Mathias
Beiträge: 5039
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunc)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Prüfen, ob ein String einen Interger darstellt.

Beitrag von Mathias »

Fliesskommazahlen kann es auch sehr effizient.
Mit Lazarus sehe ich gün
Mit Java und C/C++ sehe ich rot

Warf
Beiträge: 1480
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Prüfen, ob ein String einen Interger darstellt.

Beitrag von Warf »

Mathias hat geschrieben:Fliesskommazahlen kann es auch sehr effizient.

Ja wobei das ne ganz andere funktion ist. Ich hab mal in den Assembly geschaut, und beim Compilen erkennt der FPC den typen in den du schreiben willst und setzt dann entsprechend die funktion fpc_val_integer oder fpc_val_double o.ä. ein. Ist also keine entscheidung zur laufzeit.

Socke hat geschrieben:val kann insbesondere auch Hexadezimal ($) und Binärzahlen (%) verarbeiten.

Tatsächlich hat das keine so große auswirkung auf die laufzeit, da du praktisch nur am anfang einmal eine lookuptable und die basis laden musst. Das tatsächliche durchlaufen über die zahlen ist nicht ineffizienter, es kommen am anfang nur 2-3 load instructions hinzu.

Die Val funktion(en) sind vor definiert und vor kompiliert, man kann also davon ausgehen das bis auf sonderfälle, für das was sie tuen sollen, sie die effizientest mögliche implementierung sind. Das erkennen ob ein string eine Zahl ist, ist aber natürlich deutlich einfacher als das konvertieren, daher lohnt es sich mMn. schon eine entsprechende funktion selbst zu definieren.

Ich hab persönlich in fast jedem projekt eine Utility.pas in der ich für das Projekt wichtige funktionen drin hab, isNumeric und isFloat gehören eigentlich immer dazu, sowie ein paar weitere datentypen und funktionen, sodass ich bei nem neuen projekt meist die utility.pas von nem alten projekt rüber kopiere und die sachen raus lösche die ich nicht gebrauchen kann bzw neue sachen hinzufüge.

Zahlen Erkennung gehört definitiv zu den Sachen die man sehr oft braucht und ne eigne funktion dafür lohnt sich auf jeden fall

Benutzeravatar
m.fuchs
Lazarusforum e. V.
Beiträge: 2284
Registriert: Fr 22. Sep 2006, 19:32
OS, Lazarus, FPC: Winux (Lazarus 2.0.8, FPC 3.0.4)
CPU-Target: x86, x64, arm
Wohnort: Berlin
Kontaktdaten:

Re: Prüfen, ob ein String einen Interger darstellt.

Beitrag von m.fuchs »

six1 hat geschrieben:Wenn es im jeweiligen Programm nicht passt strtointdef zu verwenden, würde ich es einfach nicht verwenden; schon mal drüber nachgedacht?
Diese Schlaumeierei ist manchmal echt schwer zu ertragen. Ein Hinweis auf mögliche Komplikationen hätte auch ausgereicht und das Problem verständlich gemacht.

Entspann dich mal, gibt keinen Grund sich aufzuregen.
Gesucht war Quellcode, der prüft ob ein String eine Zahl darstellt. Dein Code macht das nicht und gibt ein fehlerhaftes Ergebnis aus. Da sind doch ein paar Hinweise erlaubt, was das Problem und warum es so schwerwiegend ist.
Software, Bibliotheken, Vorträge und mehr: https://www.ypa-software.de

Warf
Beiträge: 1480
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Prüfen, ob ein String einen Interger darstellt.

Beitrag von Warf »

six1 hat geschrieben:Wenn es im jeweiligen Programm nicht passt strtointdef zu verwenden, würde ich es einfach nicht verwenden; schon mal drüber nachgedacht?


Böse Zungen würden jetzt behaupten das StrToIntDef nicht dafür geeignet ist um zu überprüfen ob ein String eine Zahl ist, sondern um einen string in eine Zahl umzuwandeln mit einem Default wert falls es fehlschlägt.
Ich mein klar kann ich verstehen das man eventuell einen einzeiler sucht bei dem man keine dummy Variable definieren muss, wie bei TryStrToInt, aber es ist nunmal keine allgemein korrekte Lösung, da die Domain der Integers keinen Bottom-Value zulässt.
Tatsächlich sieht das bei Double anders aus, da gibts NaN, aber für Integers muss man nunmal die Domain um einen zusätzlichen Boolean erweitern damit man eine korrekte funktion hat

Benutzeravatar
six1
Beiträge: 207
Registriert: Do 1. Jul 2010, 19:01

Re: Prüfen, ob ein String einen Interger darstellt.

Beitrag von six1 »

@warf
das hast du zutreffend erklärt; bin ich absolut deiner Meinung!
Es gibt da kleine, feine Unterschiede und man muss eben wissen, was hinten rauskommen soll :D
Notfalls kann man sogar in die Hilfe schauen.
Gruß, Michael

Antworten