Erstellung einer Funktion

[Mo53]

Ist dann mit 'A' die Zahl gemeint ?
Und wenn ich dann die zweite Variante nehme muss ich dann unten bei longestNumber := NumberString eintragen ? das funktioniert ja nicht da longestNumber vom Datentyp byte ist und NumberString ein string.

Sorry für die dummen Fragen, ich komme da einfach nicht weiter.

[Delphi.Narium]

Nein, 'A ist als Beispiel für das Anhängen eines einzelnen Zeichens an einen String gedacht.

StringVariabel := StringVariabel + 'String';
oder
StringVariabel := StringVariabel + AndereStringVariabel;

Wenn der Rückgabewert von LongestNumber ein String sein soll, dann muss halt LongestNumber vom Typ String sein. Man ersetze byte durch string.

[Michael II]

Da der zu durchsuchende String beim Aufruf der Funktion vollständig bekannt ist: Verzichte möglichst auf "teure" Additionen von Strings: Es macht zum Beispiel genau 0 Sinn, wenn du jede auftretende Ziffernfolge aufaddierst, diese abspeicherst, nur um sie später wieder zu verwerfen, wenn du eine längere Folge gefunden hast. - Stringoperationen kosten viel, Integerops wenig.

Merke dir also nur Start und Länge der jeweils "maximalen" Folge und nicht den Zeichensalat.

Beispiel:
A0022DJIOE390220DJIWOEDJ390J3

An Position i=1 liest du A und tust nix.
An i=2 liest du 0. Du merkst dir start=2, dann liest du 0, 2, 2.
Bei i=6 liest du "D"; also keine Ziffer mehr. Du hast die erste Ziffernfolge gefunden: Laenge = i-start = 6-2 = 4. Du merkst dir die momentan längste Folge, indem du maxstart=start=2 und maxlaenge=laenge=4 speicherst.

Es folgen keine Ziffern bis und mit i=10. Du tust nix.
Bei i=11 liest du eine 3. Du merkst dir start=11. Bei i=17 "D" ist die Ziffernfolge zu Ende. Die Laenge = i-start beträgt Laenge=17-11 = 6. Laenge=6 ist grösser als die bisherige maxlaenge=4 => Du merkst dir maxstart=11 maxlaenge=6 usw.

Am Ende weisst du, dass eine längste Folge bei maxstart beginnt und maxlaenge lang ist.

Auf dem zehnjährigen 2,2GHz Prozessor i7-3620QM können so 1000 1Mio Zeichen lange Strings in 4,4 Sekunden durchsucht werden.

Delphi-Quellcode:

function LaengsteZiffernFolgeDerWelt( s : string ) : string;
var
  len_s,
  maxlaenge, maxstart, laenge, start, i: Integer;

begin
  start := 0;
  maxlaenge := 0;
  maxstart := 0;
  i := 1;
  len_s := length(s);
  while i <= len_s do
  begin
    if ( s[i] in ['0'..'9'] ) then
    begin
      if start = 0 then start := i
    end
    else
    begin
      if start > 0 then
      begin
        laenge := i-start;
        if laenge > maxlaenge then
        begin
          maxlaenge := laenge;
          maxstart := start;
        end;
        start := 0;
      end;
    end;
    inc(i);
  end;

  if start > 0 then // *
  begin
    laenge := i-start;
    if laenge > maxlaenge then
    begin
      maxlaenge := laenge;
      maxstart := start;
    end;
  end;

  if maxlaenge > 0 then Result := Copy( s, maxstart, maxlaenge )
  else Result := '';
end;

* Wenn s[length(s)] eine Ziffer ist, dann müssen wir noch prüfen, ob diese letzte Ziffernfolge in s die längste ist. Du könntest auch gleich nach dem "begin" der Funktion an s ein "Nichtzifferzeichen" anhängen. Also s := s+'A'; Dann kannst du auf diesen Check (if start > 0 then begin... end) verzichten. In den allermeisten Fällen wäre das sicher auch ok...

[Amateurprofi]

Oder so:

Delphi-Quellcode:

FUNCTION LongestCipherSequence(const S:String):Integer;
var N:Integer; P:PChar;
begin
   Result:=0;
   P:=PChar(S);
   if P<>Nil then
      repeat
         case P^ of
            #0       :  Break;
            '0'..'9' :  begin
                           N:=1;
                           Inc(P);
                           while P^ in ['0'..'9'] do begin
                              Inc(N);
                              Inc(P);
                           end;
                           if N>Result then Result:=N;
                        end;
            else        Inc(P);
         end;
      until False;
end;

Oder um Michaels Hinweis aufzugreifen:

Delphi-Quellcode:

FUNCTION LongestCipherSequence2(const S:String):Integer;
var P,PS:PChar;
begin
   Result:=0;
   P:=PChar(S);
   if P<>Nil then
      repeat
         case P^ of
            #0       :  Break;
            '0'..'9' :  begin
                           PS:=P;
                           Inc(P);
                           while P^ in ['0'..'9'] do Inc(P);
                           if P-PS>Result then Result:=P-PS;
                        end;
            else        Inc(P);
         end;
      until False;
end;

Delphi-Quellcode:

PROCEDURE TMain.Test;
const S='1A22B333C4444D55555E';
begin
   ShowMessage(IntToStr(LongestCipherSequence(S)));
   ShowMessage(IntToStr(LongestCipherSequence2(S)));
end;

[Michael II]

Zitat von Amateurprofi:

Oder so:

Nicht "oder so", sondern nur so wie Profi .
Es gibt allerdings einen Unterschied: #37 liefert wie in #26 verlangt den String, #38 die Position.
Zeitlich bewegen wir uns im gleichen Rahmen. Profi nutzt aus, dass Strings Null-terminiert sind, muss aber die =#0 Abfrage bei jedem Zeichen ausführen, #37 "einmal" am Schluss *.

[Mo53]

Wirklich sehr Interessant, Vielen Dank für eure Mühe

[Mo53]

Kann man das denn so regeln das die längste Ziffernfolge auf Basis des Strings bestimmt wird aber ein word-Wert zurückgegeben wird also z.B. wenn die längste Ziffernfolge 012 ist wird eine 12 zurückgegeben ?

[Amateurprofi]

Zitat von Michael II:

Zitat von Amateurprofi:

Oder so:

Nicht "oder so", sondern nur so wie Profi .
Es gibt allerdings einen Unterschied: #37 liefert wie in #26 verlangt den String, #38 die Position.
Zeitlich bewegen wir uns im gleichen Rahmen. Profi nutzt aus, dass Strings Null-terminiert sind, muss aber die =#0 Abfrage bei jedem Zeichen ausführen, #37 "einmal" am Schluss *.

Hallo Michael,
Zu "#37 liefert wie in #26 verlangt den String, #38 die Position"
Nee, #28 liefert die Länge der Ziffernfolge
Um die Ziffernfolge selbst zu liefern, bedarf es einiger kleiner Änderungen.
Hier die Funktion, die die Ziffernfolge liefert

Delphi-Quellcode:

FUNCTION LongestCipherSequence(const S:String):String;
var MaxLen:Integer; P,PS,PSMax,PStart:PChar;
begin
   MaxLen:=0;
   PStart:=PChar(S);
   P:=PStart;
   if P<>Nil then
      repeat
         case P^ of
            #0       :  Break;
            '0'..'9' :  begin
                           PS:=P;
                           Inc(P);
                           while P^ in ['0'..'9'] do Inc(P);
                           if P-PS>MaxLen then begin
                              MaxLen:=P-PS;
                              PSMax:=PS;
                           end;
                        end;
            else        Inc(P);
         end;
      until False;
   if MaxLen=0 then Result:=''
      else Result:=Copy(S,PSMax-PStart+1,MaxLen);
end;

Zu "muss aber die =#0 Abfrage bei jedem Zeichen ausführen, #37 "einmal" am Schluss"
Nee, stimmt nicht.
Beim While wird ebenfalls bei jedem Zeichen geprüft, ob I >= len_s ist.
Vom Zeitaufwand her macht das keinen Unterschied.

Ich habe mal kurz das Zeitverhalten getestet. Gleiche Größenordung bei beiden Funktionen.
Ergebnis siehe Anhang:

Man könnte das Zeitverhalten noch optimieren:
Wenn bereits eine Ziffernfolge gefunden wurde, kann man beim Finden der nächsten Ziffer prüfen, ob das Zeichen an P+Maxlen eine Ziffer ist.
Wenn nicht, kann die Ziffernfolge nicht länger sein, als die bisher längste.
Dann kann man P = P+MaxLen setzen, muss also nicht jedes Zeichen separat prüfen.
Das lohnt sich aber nur, wenn wirklich lange Strings mit vielen Ziffern geprüft werden sollen, ansonsten wird das eher zu einem höheren Zeitbedarf führen.

Delphi-Quellcode:

PROCEDURE TMain.Test;
const Lines=10000; MaxLen=200; Rnd=12; Count=1000;
var I,J,Len:Integer; T0,T1,T2:Cardinal; S:String; List:TStrings;
begin
   List:=TStringList.Create;
   for I:=1 to Lines do begin
      Len:=Random(MaxLen);
      SetLength(S,Len);
      for J:=1 to Len do
         S[J]:=Char(Random(Rnd)+Ord('0'));
      List.Add(S)
   end;
   T0:=GetTickCount;
   for I:=1 to Count do
      for J:=0 to List.Count-1 do
         LongestCipherSequence(List[J]);
   T1:=GetTickCount;
   for I:=1 to Count do
      for J:=0 to List.Count-1 do
      LaengsteZiffernFolgeDerWelt(List[J]);
   T2:=GetTickCount;
   ShowMessage(IntToStr(T1-T0)+' LongestCipherSequence'#13+
               IntToStr(T2-T1)+' LaengsteZiffernFolgeDerWelt');
   List.Free;
end;

[Michael II]

Zitat von Amateurprofi:

Um die Ziffernfolge selbst zu liefern, bedarf es einiger kleiner Änderungen.
Hier die Funktion, die die Ziffernfolge liefert
FUNCTION LongestCipherSequence(const S:String):String; Ich habe mal kurz das Zeitverhalten getestet. Gleiche Größenordung bei beiden Funktionen.

Apfel Birnen Vergleich wegen deinem const Aufruf:
Mit const, also so
function LaengsteZiffernFolgeDerWelt( const s : string ) : string; ist's natürlich auch schneller.

Bei etwa 80% pseudozufällig verteilten Ziffern sind beide gleich schnell. Bei mehr als 80% Ziffernanteil deine, bei weniger meine.

Die Idee mit vorausschauender Prüfung ist schön.

[Michael II]

Sehr schnelle Lösung zur Suche gelöscht.
Da dies nie gebraucht werden wird (siehe #55).
Ich will ja keinen DP Platz verschwenden.