Solved

# Split a string: needed efficient algoritme

Posted on 1998-06-07
133 Views
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
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

LVL 5

Accepted Solution

inter earned 350 total points
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
end;

Regards,
Igor
0

LVL 5

Expert Comment

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

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

With regards,
Donker
0

LVL 6

Expert Comment

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...

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

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

### Suggested Solutions

A lot of questions regard threads in Delphi.   One of the more specific questions is how to show progress of the thread.   Updating a progressbar from inside a thread is a mistake. A solution to this would be to send a synchronized message to the…
Hello everybody This Article will show you how to validate number with TEdit control, What's the TEdit control? TEdit is a standard Windows edit control on a form, it allows to user to write, read and copy/paste single line of text. Usua…
Illustrator's Shape Builder tool will let you combine shapes visually and interactively. This video shows the Mac version, but the tool works the same way in Windows. To follow along with this video, you can draw your own shapes or download the file…
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …