We help IT Professionals succeed at work.

The result of a function using iteration

ttheimer
ttheimer asked
on
336 Views
Last Modified: 2012-05-08
In the following example I have a function that iterates through a string seeking the substring after the last slash.  While this works I would prefer to build a function that can return this substring after the last slash without relying on the private variable "FinalValStr" that is declared outside of the function.

procedure TForm1.Button1Click(Sender: TObject);
begin
  StrAfterFirstSlash(Edit1.Text);
  Label1.Caption := FinalValStr;
end;

function TForm1.StrAfterFirstSlash(InStr: String): String;
var
  PosWd: Word;
begin
  PosWd := Pos('/', InStr);
  if PosWd > 0 then
    Result := StrAfterFirstSlash(Copy(InStr, PosWd + 1, 1000))
  else
  begin
    FinalValStr := InStr;
    Exit;
  end;
end;
Comment
Watch Question

Oracle dba
CERTIFIED EXPERT
Top Expert 2009
Commented:
This one is on us!
(Get your first solution completely free - no credit card required)
UNLOCK SOLUTION
Emmanuel PASQUIERFreelance Project Manager
CERTIFIED EXPERT
Top Expert 2010
Commented:
This one is on us!
(Get your first solution completely free - no credit card required)
UNLOCK SOLUTION
Geert GOracle dba
CERTIFIED EXPERT
Top Expert 2009

Commented:
ooo___O_O___ooo

efficient?
you use pos ...
and you are running from the beginning of the string
whereas the intended item is at the end

i suggest the faststrings unit for real efficiency
next i'll give a sample with FastStrings unit
function StrAfterLastSlash(InStr:String):String;
begin
  Result := '';
  for i := Length(InStr) downto 1 do
    if not (InStr[i] in ['/','\']) then 
      Result := InStr[I] + Result
    else 
      Break;
end;

Open in new window

Emmanuel PASQUIERFreelance Project Manager
CERTIFIED EXPERT
Top Expert 2010

Commented:
I don't use Pos
and while I start at the begining where I could have started from the end just by reversing the for loop AND adding a break as you do, it's still much better than reversing + pos as you do.

Result:=Char+Result is one realloc + 1 move per cycle, which is not good also.

Ok, as you are willing to get every cycle of CPU wisely used, then let's reverse the for logic, and use a while instead. Next optimisation would be ASM, but that would be ridiculous as this is almost as good.

If you want to compare those algo by executing them 1.000.000 times, be fair to replace the IN test by ='/' as it is not the same load.
function StrAfterLastSlash(InStr:String):String;
Var
 L,P:Integer;
begin
 L:=Length(InStr); 
 P:=L;
 while (P>0) And Not(InStr[P] In ['/','\']) do Dec(P);
 Result:=Copy(InStr,P+1,L-P);
end;

Open in new window

Emmanuel PASQUIERFreelance Project Manager
CERTIFIED EXPERT
Top Expert 2010

Commented:
Ok, let's strike the IN operator as it is  too much just for 2 chars comparisons.
function StrAfterLastSlash(InStr:String):String;
Var
 L,P:Integer;
begin
 L:=Length(InStr); 
 P:=L;
 while (P>0) And (InStr[P]<>'/') And (InStr[P]<>'\') do Dec(P);
 Result:=Copy(InStr,P+1,L-P);
end;

Open in new window

Geert GOracle dba
CERTIFIED EXPERT
Top Expert 2009

Commented:
owkay, but then why not use pointers ?
function StrAfterLastSlash(InStr:String; aSlash: Char = '/'; aBackSlash: char = '\'):String;
var X: PChar;
  L: integer;
begin
  Result := InStr;
  L := Length(InStr);
  if L > 0 then
  begin
    X := @InStr[L];
    while X >= @InStr[1] do
    begin
      if (X[0] = aSlash) or (X[0] = aBackSlash) then
      begin
        Inc(X);
        Result := X;
        Break;
      end;
      Dec(X);
    end;
  end;
end;

Open in new window

Geert GOracle dba
CERTIFIED EXPERT
Top Expert 2009

Commented:
And forget the FastStrings, i doesn't compile any longer under D2009/D2010
Emmanuel PASQUIERFreelance Project Manager
CERTIFIED EXPERT
Top Expert 2010

Commented:
you must be kidding

Result:=X; is a Copy as well, but implicitly done by delphi.
in ASM, comparing InStr[P] with a value is a simple loop, that can use instruction LODSB based on DS:SI to quickly get the value and inc automatically the index (P). delphi does not optimize the loop by using it, but this is the closest algo in high level language. By the way, I've looked at the delphi generated ASM, there is plenty of room for optimizations.

by using the pointer in your loop, your are changing the base of your (segment:offset) pair and therefore prevent the use of such optimizations. As delphi is not well optimized, it should not matter much. but that's complicated.

code in ASM (not complete, just the loop, and sometime I mix with delphi call) : 
   MOV ECX,Length(InStr) 
   OR ECX,ECX
   JZ end // jump if string empty   
   STD // set the direction backward
   MOV ESI,[ebp] // load addr of 1st char of the string
   ADD ESI, ECX-1 // move to last char of string    
loop :
   LODSB
   CMP Al,'/'
   JE End
   CMP Al,'\'
   JE End
   LOOP
end :
   CLD // put direction flag to normal state
// now ECX contains the final value of P, just have to go on with Move

Open in new window

aikimarkSocial distance; Wear a mask; Don't touch your face; Wash your hands for 20 seconds
CERTIFIED EXPERT
Top Expert 2014
Commented:
This one is on us!
(Get your first solution completely free - no credit card required)
UNLOCK SOLUTION

Author

Commented:
The points and rating hardly apply here.

I posted the question to straighten out my thinking about recursion.  Though the responses never addressed that issue I found myself copying pieces from each personal note file... string functions I hadn't used, performance considerations, etc., etc.  Quite a surprise but thanks to all.
Emmanuel PASQUIERFreelance Project Manager
CERTIFIED EXPERT
Top Expert 2010

Commented:
Thanks aikimark for your comment, you are right that we went a little far in theory, and without a benchmark it's not as valuable. here it is

I tested the following algo :

StrAfterLastSlash_0 : my first algo (corrected) on post 25812343
StrAfterLastSlash_1 : my last algo on post 25812512
StrAfterLastSlash_2 : Geert first algo on post 25811631
StrAfterLastSlash_3 : Geert last algo on post 25812591

Note that some algo do not manage the 2 slashes. It's the case of Algo_2

After the first tests, I noticed that IN operator was quicker than even 2 comparison. That's an interesting piece of news ! I then made a modification on my last algo using it :
StrAfterLastSlash_1 : code in this last post

each function run x50.000.000, perf mesured with QueryPerformanceCounter
time in seconds
test machine : Intel i920/Nehalem@2.7Ghz

test line: C:\Program Files (x86)\CodeGear\RAD Studio\5.0\bin\dclIndyProtocols100.bpl
StrAfterLastSlash_0 :    14,54
StrAfterLastSlash_1 :    7,43
StrAfterLastSlash_1_1 : 6,72
StrAfterLastSlash_2 :    10,63 // better than 3, but no '\' and '/' management
StrAfterLastSlash_3 :    12,46

test line: C:\Delphi\Is\Good
StrAfterLastSlash_0 :   4,92
StrAfterLastSlash_1 :   3,89
StrAfterLastSlash_1_1 : 3,80
StrAfterLastSlash_2 :   6,95
StrAfterLastSlash_3 :   6,07

Conclusions :
- no worry to have about IN operator, it's efficient.
- memory copy and pointers
- Going through all the string (algo_0) is killing performance if the remaining string is long, otherwise it's better than too much memory copy
- using pointer does not help

and last, going to ASM should divide the time of algo 1_1 by at least 3 - maybe 5, judging the poor code generated by delphi on this point.
But is there anybody who care about these arduous optimizations given the little time modern computers can do it 50 millions times ?

function StrAfterLastSlash_1_1(InStr:String):String;
Var
 L,P:Integer;
begin
 L:=Length(InStr);
 P:=L;
 while (P>0) And Not (InStr[P] In ['\','/']) do Dec(P);
 Result:=Copy(InStr,P+1,L-P);
end;

Open in new window

Emmanuel PASQUIERFreelance Project Manager
CERTIFIED EXPERT
Top Expert 2010

Commented:
in my conclusion, I didn't finished a line :
- memory copy (like reversing a text) are also killing performance if not absolutely necessary
aikimarkSocial distance; Wear a mask; Don't touch your face; Wash your hands for 20 seconds
CERTIFIED EXPERT
Top Expert 2014

Commented:
@epasquier

Thanks for the benchmarks.

I'm surprised you didn't test the ASM solution (http:#25812839) or the ExtractFilename() function.
Emmanuel PASQUIERFreelance Project Manager
CERTIFIED EXPERT
Top Expert 2010

Commented:
about the ASM solution, it's not complete. It would need some testing and tweaking. I haven't done so in few years and I'm rusty :o) Maybe latter.
I wanted to first test quickly what a Delphi programmer could have at his disposal. You are right I should test ExtractFileName as well.
I'll do it and post its result here

Gain unlimited access to on-demand training courses with an Experts Exchange subscription.

Get Access
Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Empower Your Career
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE

Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions
Unlock the solution to this question.
Join our community and discover your potential

Experts Exchange is the only place where you can interact directly with leading experts in the technology field. Become a member today and access the collective knowledge of thousands of technology experts.

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.