Solved

Split a string: needed efficient algoritme

Posted on 1998-06-07
5
136 Views
Last Modified: 2012-05-07
Having no time to do this myself right now,
I would like to have the following slow code modified so that it becomes
much, much quicker.
Function Reserve can go away, but the procedure SplitFromEnd must give the exact same result as it does know.
The typical length of the string to process in SplitFromEnd is about 20 Kb.
So Reserve is very very inefficient.
Please post your answer ASAP, and in the form of a procedure I can cut and paste
in my program right away and do not give mere hints.

With Regards,
 Donker


Function Reverse(Inputstring: String): String;
var x : integer;
    ToProcess : String;
begin
    ToProcess:='';
    for x:= 1 to length(Inputstring)
    do ToProcess:= copy(Inputstring,x,1) + ToProcess;
    Reverse:=ToProcess;

end;

procedure SplitFromEnd(SplitAt: String; var InputString, PostString: String) ;
var TmpPos: integer;
    Before, AfterIncl, ToProcess: String;
    tmpSplitAt: string;
begin
   ToProcess:=Reverse(Inputstring);
   tmpSplitAt:=Reverse(SplitAt);

   TmpPos := pos(tmpSplitAt, ToProcess);

   if tmppos = 0
   then begin
        MessageDlg('SplitFromEnd: NOT FOUND', mtInformation,[mbOk], 0);
        end;

   AfterIncl:= copy(ToProcess, 1, tmppos + length(SplitAt));
   AfterIncl:=reverse(AfterIncl);
   Before :=  copy(ToProcess, tmppos +length(SplitAt), length(ToProcess));
   Before := reverse(Before);

   InputString:=Before;
   Poststring:= AfterIncl;
end;
0
Comment
Question by:padonker
5 Comments
 
LVL 5

Accepted Solution

by:
inter earned 350 total points
ID: 1334779
Hi friend,
This routine does no reversion and it only do one copy operation. May be it full fill you needs.

procedure SplitFromEnd(SplitAt: string; var InStr, PostStr: string);
var
  P : PChar;
  C : PChar;
  CLen : integer;
  Found : boolean;
begin
  // Append #0 for null terminated processing
  C := @SplitAt[1];
  CLen := Length(SplitAt);
  P := @InStr[Length(InStr) - Length(SplitAt)];
  SplitAt := SplitAt + #0;
  // try to find the SplitAt from right
  Found := false;
  while (P <> @InStr[1]) and not Found do  //while not hit to the begining
  begin
    Dec(P);
    Found := StrLComp(P, C, CLen) = 0;
  end;
  if Found then
  begin
    //copy post
    PostStr := StrPas(P);
    //Truncate the InStr
    SetLength(InStr, Longint(P) - Longint(@InStr[1]));
  end else
    MessageDlg('SplitFromEnd: NOT FOUND', mtInformation, [mbOk], 0);
end;

Awaiting comments
Regards,
Igor
0
 
LVL 5

Expert Comment

by:ronit051397
ID: 1334780
Maybe this Reverse function will work faster:

Function Reverse(Inputstring: String): String;
var P,S: pChar;
begin
  S:=pChar(Inputstring);
  P:=StrEnd(S)-1;
  Dec(S);
  while P<>S do
  begin
    Result:=Result+P[0];
    Dec(P);
  end;
end;
0
 

Author Comment

by:padonker
ID: 1334781
I say: Yes, this is a excellent piece of code.
Thank you Inter.



With regards,
   Donker
0
 
LVL 6

Expert Comment

by:Holger101497
ID: 1334782
I guess inter's function will be the fastest... although it does 20000 string compares if the string is 20000 long... I don't know the internal implementation of POS, so I don't know how fast it is...

some hints about your code:
copy(Inputstring,x,1) is InputString[x] ! I don't know how "smart" the compiler is in optimization, but you definitely don't need a function call here! InputString[x] is (almost) directly translated into an address


ronit: Your code will only be marginally faster - if at all.
The problem is this: for x:= 1 to length(Inputstring) do ToProcess:= copy(Inputstring,x,1) + ToProcess; OR Result:=Result+P[0];

They both append the characters one by one and re-allocate the string 20000 times! The "correct" way of reversing it would be something like this:

L:=Length(InputString); //store it to save 20000 function calls in the loop
SetLength(result,L); //allocate the string;
FOR P:=1 TO L DO result[L]:=InputString[L+1-P];

you can use PChars, but I'm not sure if that's faster...

P.S.: Ooops. While I was writing, the answer was accepted. I wonder if my comment still makes it :-))
0
 
LVL 5

Expert Comment

by:inter
ID: 1334783
Thanks,
If you need a faster routine I can program a FindLast routine which immediatelly finds the right most matching string and we can get rid of the StrLComp, but this may take a while. Regards, Igor
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
IExtractImage Delphi 14 201
IdTelnet1DataAvailable handler freezes the Application 4 63
control image tags in a string ? 12 110
Base1 Encode/Decode 3 67
Introduction The parallel port is a very commonly known port, it was widely used to connect a printer to the PC, if you look at the back of your computer, for those who don't have newer computers, there will be a port with 25 pins and a small print…
Creating an auto free TStringList The TStringList is a basic and frequently used object in Delphi. On many occasions, you may want to create a temporary list, process some items in the list and be done with the list. In such cases, you have to…
This Micro Tutorial will give you a basic overview how to record your screen with Microsoft Expression Encoder. This program is still free and open for the public to download. This will be demonstrated using Microsoft Expression Encoder 4.
Along with being a a promotional video for my three-day Annielytics Dashboard Seminor, this Micro Tutorial is an intro to Google Analytics API data.

911 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

21 Experts available now in Live!

Get 1:1 Help Now