fastest character replacement method
Craig Reynolds
just wondering if anyone could tell which of the follwing methods would be
fastest for replacing multiple occurences of a character within a string.
Method 1: (using '/' as an example)
while (Pos('\',Path) > 0) do
Path[Pos('\',Path)] := '/';
Method 2:
using the StringReplace function
StringReplace(const Str, '\', '/'; rfReplaceAll)
obviously if I wanted to do more than 1 character replacement it would be
easiest to use StringReplace, but for a single character I am wondering,
although I guess that the code behind StringReplace() is similar to the
while loop in method 1.
--
~~~~~~~~~~~~~
§ ©raig ®eynolds §
~~~~~~~~~~~~~
Just because this is never going to work is no reason to be negative!
Dodgy
Bjørge Sæther
news:3bea9385$0$75...@echo-01.iinet.net.au...
> Hi
>
> just wondering if anyone could tell which of the follwing methods would be
> fastest for replacing multiple occurences of a character within a string.
>
> Method 1: (using '/' as an example)
>
> while (Pos('\',Path) > 0) do
> Path[Pos('\',Path)] := '/';
>
> Method 2:
>
> using the StringReplace function
>
> StringReplace(const Str, '\', '/'; rfReplaceAll)
>
> obviously if I wanted to do more than 1 character replacement it would be
> easiest to use StringReplace, but for a single character I am wondering,
> although I guess that the code behind StringReplace() is similar to the
> while loop in method 1.
Hi !
As a result of a long discussion in this NG a few months ago I created this
replace function. It behaves differently depending on whether the replacement
string is longer, shorter or of equal length. If you want the "same size"
version only, use the last if... block only. The function is compatible with
StringReplace, only much faster.
function _StringReplace(const S, OldPattern, NewPattern: string;
Flags: TReplaceFlags = [rfReplaceAll]): string;
var
i : integer;
SearchStr,
Patt : string;
ChStart,
ChPatt : PChar;
OldPattLen : integer;
NewPattLen : integer;
Delta : integer;
begin
result:=S;
OldPattLen:=Length(OldPattern);
NewPattLen:=Length(NewPattern);
if rfIgnoreCase in Flags then begin
SearchStr:=ANSIUppercase(S);
Patt:=ANSIUpperCase(OldPattern);
end
else begin
SearchStr:=S;
Patt:=OldPattern;
end;
if OldPattLen > NewPattLen then begin // We may do only one string
truncation
ChStart:=PChar(SearchStr);
ChPatt:=ChStart;
Delta:=0;
while true do begin
ChPatt:=StrPos(ChPatt, PChar(Patt));
if ChPatt = nil then
break;
if NewPattLen > 0 then
Move(NewPattern[1], result[ChPatt-ChStart+1-Delta], NewPattLen);
Move(result[(ChPatt-ChStart-Delta)+OldPattLen+1],
result[ChPatt-ChStart+NewPattLen+1-Delta],
Length(Result)-(ChPatt-ChStart-Delta)-OldPattLen);
Delta:=Delta+OldPattLen-NewPattLen; // Keep track of difference in
positions between S and result
if not (rfReplaceAll in Flags) then
break;
inc(ChPatt);
end;
SetLength(Result, Length(Result)-Delta);
end
else if OldPattLen < NewPattLen then begin // The slowest, needs to enlarge
string for each match
NewPattLen:=Length(NewPattern);
ChStart:=PChar(SearchStr);
ChPatt:=ChStart;
Delta:=0;
while true do begin
ChPatt:=StrPos(ChPatt, PChar(Patt));
if ChPatt = nil then
break;
SetLength(Result, Length(Result)+NewPattLen-OldPattLen);
Move(result[(ChPatt-ChStart)+Delta+OldPattLen+1],
result[(ChPatt-ChStart)+(NewPattLen)+Delta+1],
Length(Result)-(ChPatt-ChStart)-Delta-NewPattLen);
Move(NewPattern[1], result[ChPatt-ChStart+1+Delta], NewPattLen);
Delta:=Delta+(NewPattLen-OldPattLen); // Keep track of difference in
positions between S and result
if not (rfReplaceAll in Flags) then
break;
inc(ChPatt);
end;
end
else if (OldPattLen = 1) and (NewPattLen = 1) then begin // Just replace
Chars...
for i:=1 to Length(SearchStr) do
if SearchStr[i] = Patt[1] then begin
result[i]:=NewPattern[1];
if not (rfReplaceAll in Flags) then
break;
end;
end
else begin // Equal length, but more than 1 char...keep length, but move
chars
ChStart:=PChar(SearchStr);
ChPatt:=ChStart;
while true do begin
ChPatt:=StrPos(ChPatt, PChar(Patt));
if ChPatt = nil then
break;
Move(NewPattern[1], result[ChPatt-ChStart+1], OldPattLen);
if not (rfReplaceAll in Flags) then
break;
inc(ChPatt);
end;
end;
end;
Have fun !
--
Bjoerge Saether
Consultant / Developer
http://www.itte.no
Asker, Norway
bjorge@takethisaway_itte.no (remve the obvious)
Bruce Roberts
"Craig Reynolds" <reynold...@hotmail.com> wrote in message
news:3bea9385$0$75...@echo-01.iinet.net.au...
> Hi
>
> just wondering if anyone could tell which of the follwing methods would be
> fastest for replacing multiple occurences of a character within a string.
>
> Method 1: (using '/' as an example)
>
> while (Pos('\',Path) > 0) do
> Path[Pos('\',Path)] := '/';
>
> Method 2:
>
> using the StringReplace function
>
> StringReplace(const Str, '\', '/'; rfReplaceAll)
>
> obviously if I wanted to do more than 1 character replacement it would be
> easiest to use StringReplace, but for a single character I am wondering,
> although I guess that the code behind StringReplace() is similar to the
> while loop in method 1.
Repeated use of Pos is relatively expensive. Nor is StringReplace that
efficient, especially for single character patters. A more efficient method
would be
for ix := 1 to Length (Path) do
begin
if Path [ix] = '\'
then Path [ix] := '/';
end;
Craig Reynolds
> efficient, especially for single character patters. A more efficient
method
> would be
>
> for ix := 1 to Length (Path) do
> begin
> if Path [ix] = '\'
> then Path [ix] := '/';
> end;
probably a good idea, and using a for loop is going to be better than a
while, if I recall correctly.
--
~~~~~~~~~~~~~
§ ©raig ®eynolds §
~~~~~~~~~~~~~
Just because this is never going to work is no reason to be negative!
"Bruce Roberts" <b...@bounceitattcanada.xnet> wrote in message
news:JaAG7.2623$qb4....@tor-nn1.netcom.ca...
Craig Reynolds
it in the 'things to use' section :)
--
~~~~~~~~~~~~~
§ ©raig ®eynolds §
~~~~~~~~~~~~~
Just because this is never going to work is no reason to be negative!
"Bjørge Sæther" <REMOVE_bsaether@THIS_online.no> wrote in message
news:mKxG7.12899$Fr3.2...@news1.oke.nextra.no...
Craig Reynolds
running a test using the while method, and then the for loop, and it took 13
seconds both times. Given that in this case I am changing a path for
unix/linux compatability, and doing it to about 650 images, I would have
thought if there was a gain to be had from not using Pos() a lot, it would
have shown. But then again maybe not.
--
~~~~~~~~~~~~~
§ ©raig ®eynolds §
~~~~~~~~~~~~~
Just because this is never going to work is no reason to be negative!
"Bruce Roberts" <b...@bounceitattcanada.xnet> wrote in message
news:JaAG7.2623$qb4....@tor-nn1.netcom.ca...
>
David C. Ullrich
<reynold...@hotmail.com> wrote:
>> Repeated use of Pos is relatively expensive. Nor is StringReplace that
>> efficient, especially for single character patters. A more efficient
>method
>> would be
>>
>> for ix := 1 to Length (Path) do
>> begin
>> if Path [ix] = '\'
>> then Path [ix] := '/';
>> end;
>
>probably a good idea, and using a for loop is going to be better than a
>while, if I recall correctly.
It's not that a for loop is better than a while loop. The reason
what Bruce said is much faster than what you said is that Bruce's
code only loops through the characters in the string _once_.
If you use repeated calls to Pos each call to Pos does a (partial)
scan through the string. So on a random string with N characters
Bruce's algorithm takes time N while repeated calls to Pos take
time N*N.
It's possible that a for loop is sometimes somewhat more efficient
than a while loop as well, for technical reasons. But if so that
will be a difference of a few percent at most, and more important
the relative difference will have nothing to do with the size
of the string. Otoh the difference between N and N*N is a
100000000% percent improvement if the string is large enough.
David C. Ullrich
Bruce Roberts
> Out of curiosity, what would you call repeated use of Pos. I was just
> running a test using the while method, and then the for loop, and it took
13
> seconds both times. Given that in this case I am changing a path for
> unix/linux compatability, and doing it to about 650 images, I would have
> thought if there was a gain to be had from not using Pos() a lot, it would
> have shown. But then again maybe not.
Without seeing the code you used for the test its really not possible to
comment on your observations.
AlanGLLoyd
Ullrich) writes:
>Otoh the difference between N and N*N is a
>100000000% percent improvement if the string is large enough.
I think that that's the improvement for the biggest string you can have, so its
usually a bit less than that <g>
Alan Lloyd
alang...@aol.com
Null A.N.D. Void
<reynold...@hotmail.com> wrote:
>Out of curiosity, what would you call repeated use of Pos.
>while (Pos('\',Path) > 0) do Path[Pos('\',Path)] := '/';
Roughly translates to:
R:=0;
For i:=1 To Length(Path) Do If Path[i]='\' Then
Begin R:=i; Break; End;
While R>0 Do
Path[R]:='\';
R:=0;
For i:=1 To Length(Path) Do If Path[i]='\' Then
Begin R:=i; Break; End;
End;
which makes it clearer where the inefficiency is. If you find the
first '\' at R=10 and replace it, there is no reason to scan from
character 1-10 to look for the next R.
In processing a string 'abc\de\f', your code goes like this:
Abc\de\f
aBc\de\f
abC\de\f
abc/de\f
Abc/de\f
aBc/de\f
abC/de\f
abc/de\f
abc/De\f
...etc
>I was just
>running a test using the while method, and then the for loop, and it took 13
>seconds both times. Given that in this case I am changing a path for
>unix/linux compatability, and doing it to about 650 images, I would have
>thought if there was a gain to be had from not using Pos() a lot, it would
>have shown. But then again maybe not.
Try this (worst case scenario for your code).
procedure TForm1.Button1Click(Sender: TObject);
Var
S : String;
i,j : Integer;
T : TDateTime;
begin
SetLength(S,100000);
For i:=1 To 100000 Do S[i]:=Chr(65+Random(5));
T:=Now;
While (Pos('A',S) > 0) Do S[Pos('A',S)] := 'a';
Caption:=FloatToStr((Now-T)*3600*24); T:=Now;
For j:=1 To 500 Do
Begin
For i:=1 To 100000 Do If S[i]='a' Then S[i]:='A';
For i:=1 To 100000 Do If S[i]='A' Then S[i]:='a';
End;
Caption:=Caption+' '+FloatToStr((Now-T)*3.6*24);
End;
J French
- and there is also the fact that Pos is looking for a string of *any*
length - the OP was talking about replacing a Char
{ #############################################
}
Procedure StrReplaceChr( Var S:String ; OldB:Char ; NewB:Char ) ;
Var
L9 : Integer ;
Begin
For L9 := 1 To Length( S ) Do
Begin
If S[L9] = OldB Then
S[L9] := NewB ;
End;
End; {StrReplaceChr}
On Sat, 10 Nov 2001 12:56:28 GMT, C...@S.com (Null A.N.D. Void) wrote:
>On Fri, 9 Nov 2001 13:48:23 +0800, "Craig Reynolds"
><reynold...@hotmail.com> wrote:
<snipped>
David C. Ullrich
Well yes, it's usually a bit less. But the point is it's a _big_
improvement.
Really - people sometimes don't realize the difference between
N and N^2: if you have an O(N) algorithm that executes in 0.001
seconds for a string of length 1000 then it will execute in
1 second for a string of length 1,000,000, which is acceptable,
you don't expect to process that long a string instantaneously.
Otoh if you have an O(N^2) algorithm that executes in 0.001
seconds on a string of length 1000 then it will take more than
16 minutes for a string of length 1,000,000.
Doesn't matter if we're just tweaking mis-spelled filenames,
but it's happened to me many times that I'm processing the
text in some file. Works fine for small (test) files, then when
I try it on a large (real) file the machine seems to hang.
So I hunt for the N^2 in the algorithm... (well, that used
to happen. These days I'm a little fanatical about reading
each character in the file exactly once, period. Takes a little
foresight but it's always fun when the thing works
"instantaneously" on a large file.)
>Alan Lloyd
>alang...@aol.com
David C. Ullrich
David C. Ullrich
<reynold...@hotmail.com> wrote:
>Out of curiosity, what would you call repeated use of Pos. I was just
>running a test using the while method, and then the for loop, and it took 13
>seconds both times. Given that in this case I am changing a path for
>unix/linux compatability, and doing it to about 650 images, I would have
>thought if there was a gain to be had from not using Pos() a lot, it would
>have shown. But then again maybe not.
If you're just processing filenames it probably doesn't matter much.
The N versus N^2 thing becomes important when you're processing
_long_ strings (_not_ the same thing as processing many short
strings!)
Try a test, not that it matters for this application: Construct a
really long string, like use something like
SetLength(s, 2000000);
for j:=1 to 1000000 do
begin
s[2*j-1]:= '\';
s[2*j]:= '/';
end;
and now compare the running time of your algorithm
and Bruce's on _that_ string. (Hint: try Bruce's
first...)
As long as they're short strings like filenames,
manipulating strings using things like Pos, Delete,
etc in loops can be very convenient. But don't do
it if there's a chance the code will ever be used
on a long string (like scanning the text in a large
file looking for delimiters, etc.)
David C. Ullrich
Dodgy
<reynold...@hotmail.com> waffled on about something:
>Hi
>
>just wondering if anyone could tell which of the follwing methods would be
>fastest for replacing multiple occurences of a character within a string.
>
>Method 1: (using '/' as an example)
>
>while (Pos('\',Path) > 0) do
> Path[Pos('\',Path)] := '/';
>
>Method 2:
>
>using the StringReplace function
>
>StringReplace(const Str, '\', '/'; rfReplaceAll)
>
>obviously if I wanted to do more than 1 character replacement it would be
>easiest to use StringReplace, but for a single character I am wondering,
>although I guess that the code behind StringReplace() is similar to the
>while loop in method 1.
Avoid the use of pos for single char replaces at it does loads of
internal string chopping even if you are looking for a single
character.
It's best just to go straight for them with
for l:=1 to length(yourstring)
begin
if yourstring[l]=oldchar then yourstring[l]=newchar;
end;
Craig Reynolds
replacing ways :)
--
~~~~~~~~~~~~~
§ ©raig ®eynolds §
~~~~~~~~~~~~~
Just because this is never going to work is no reason to be negative!
"Craig Reynolds" <reynold...@hotmail.com> wrote in message
news:3bea9385$0$75...@echo-01.iinet.net.au...
Bruce Roberts
> thanks for the input people, I am now much wiser in my string searching
and
> replacing ways :)
One last note if I may. Knowing now that you are processing paths one can
improve upon the for loop solution based on the fact that // cannot occur in
the string and presuming that there will be no empty strings:
lth := Length (path);
i := 1;
repeat
if path [i] = '/'
then begin
path [i] := '\';
inc (i);
end;
inc (i);
until (i > lth);
(If the presumption of no empty strings is incorrect, one would have to
replace the repeat with a while.)
Craig Reynolds
--
~~~~~~~~~~~~~
§ ©raig ®eynolds §
~~~~~~~~~~~~~
Just because this is never going to work is no reason to be negative!
"Bruce Roberts" <b...@bounceitattcanada.xnet> wrote in message
news:T%mH7.3142$qb4....@tor-nn1.netcom.ca...
David C. Ullrich
<b...@bounceitattcanada.xnet> wrote:
>
>"Craig Reynolds" <reynold...@hotmail.com> wrote in message
>news:3bedd9b4$0$14...@echo-01.iinet.net.au...
>> thanks for the input people, I am now much wiser in my string searching
>and
>> replacing ways :)
>
>One last note if I may. Knowing now that you are processing paths one can
>improve upon the for loop solution based on the fact that // cannot occur in
>the string and presuming that there will be no empty strings:
>
>lth := Length (path);
>i := 1;
>repeat
> if path [i] = '/'
> then begin
> path [i] := '\';
> inc (i);
> end;
> inc (i);
>until (i > lth);
I was a big fan of your earlier comments here, but surely this
one is a "yikes" in terms of wondering why code doesn't work
when you re-use it.
(Surely knowing that we're processing paths if anything means that
ultimate optimizations are not going to make much difference.)
>(If the presumption of no empty strings is incorrect, one would have to
>replace the repeat with a while.)
>
>
>
David C. Ullrich
Bruce Roberts
"David C. Ullrich" <ull...@math.okstate.edu> wrote in message
> I was a big fan of your earlier comments here, but surely this
> one is a "yikes" in terms of wondering why code doesn't work
> when you re-use it.
>
> (Surely knowing that we're processing paths if anything means that
> ultimate optimizations are not going to make much difference.)
>
You are probably quite correct in this. Frankly I'd likely use a for loop
solution myself for the very reasons you cite. However, I thought it would
be instructive show how special knowledge of a problem can lead to a more
efficient solution. While I'm not a big fan of spending time to eke the last
microsecond out of a piece of code, I do think that one should try to
develop good and safe programming habits that produce efficient code. IMO
overall program performance is improved when one habitually uses code that
is efficient.