Question What is the most efficient algorithm for reversing a character string

Cecil

19+ years progress programming and still learning.
Hi Guys,

This might sound odd question but what is the most efficient algorithm for reversing a character string in the ABL of any string length?

Backstory:
I was working function and I need to reverse the order of the string value (example: a2c-4e6-g8H to become H8g-6e4-c2a) and this is not something normally do. But, it got me thinking as to what is the most efficient way of doing this in the ABL.

I know that .NET has a method of reversing string arrays, but I was thinking of a more pure ABL approach.
 

Cringer

ProgressTalk.com Moderator
Staff member
I've no idea if it's the most efficient, in fact it almost certainly isn't, but it definitely plays to my geeky side...


Can't beat a bit of recursion on a Monday morning.
 
Last edited:

Osborne

Active Member
Cringer's solution is a nice one.

The best I could come up with is this:
Code:
DEFINE VARIABLE vCount AS INTEGER NO-UNDO.
DEFINE VARIABLE vResult AS CHARACTER NO-UNDO.
DEFINE VARIABLE vText AS CHARACTER INITIAL "a2c-4e6-g8H" NO-UNDO.

DO vCount = LENGTH(vText) TO 1 BY -1:
   vResult = vResult + SUBSTRING(vText,vCount,1).
END.

MESSAGE vResult VIEW-AS ALERT-BOX.
 

TomBascom

Curmudgeon
I am not in any way proud of this ;)

Code:
function rev3 returns character ( input s as character ).

  define variable r as character no-undo.
  define variable c as character no-undo.
  define variable i as integer no-undo.

  do while true:
    assign
      i = i + 1
      c = substring( s, i, 1 )
    .
    if c = chr(0) then
      leave.
     else
      r = c + r.
  end.

  return r.

end.

message rev3( "Forwards" ).
 

TomBascom

Curmudgeon
Combining them all with some tweaks to rev3():

Code:
FUNCTION Reverse RETURNS CHARACTER  (pInput AS CHARACTER):

    DEFINE VARIABLE cLastChar AS CHARACTER NO-UNDO.
    DEFINE VARIABLE cRest     AS CHARACTER NO-UNDO.
    
    IF LENGTH(pInput, "CHARACTER") = 1 THEN
        RETURN pInput.
        
    ASSIGN
        cLastChar = SUBSTRING (pInput, LENGTH (pInput, "CHARACTER") , 1)
        cRest     = SUBSTRING (pInput, 1, LENGTH (pInput, "CHARACTER") - 1)
        .
         
    RETURN cLastChar + Reverse (cRest).
    
END FUNCTION.


function rev2 returns character ( input vText as character ).

  DEFINE VARIABLE vCount AS INTEGER NO-UNDO.
  DEFINE VARIABLE vResult AS CHARACTER NO-UNDO.
  
  DO vCount = LENGTH(vText) TO 1 BY -1:
     vResult = vResult + SUBSTRING(vText,vCount,1).
  END.
  
  return vResult.
  
end.


function rev3 returns character ( input s as character ).

  define variable r as character no-undo.
  define variable c as character no-undo initial "!".
  define variable j as integer no-undo.
  
  do while c > "":
    assign
      j = j + 1
      c = substring( s, j, 1 )
      r = c + r
    .
  end.
  
  return r.
  
end.


define variable i   as integer no-undo.
define variable n   as integer no-undo initial 1000.

define variable t1  as integer no-undo.
define variable t2  as integer no-undo.
define variable t3  as integer no-undo.

define variable str as character no-undo.

str = "abcdefghijklmnopqrstuvwxyz123ABCDEFGHIJKLMNOPQRSTUVWXYZ".

display
  reverse( str ) format "x(80)" skip
     rev2( str ) format "x(80)" skip
     rev3( str ) format "x(80)" skip
.

etime( yes ). 
do i = 1 to n:
  str = reverse( str ).
end.
t1 = etime.

etime( yes ). 
do i = 1 to n:
  str = rev2( str ).
end.
t2 = etime.

etime( yes ). 
do i = 1 to n:
  str = rev3( str ).
end.
t3 = etime.

display t1 t2 t3.

Results in:

Code:
        t1         t2         t3                        
───────────────────────────────────────────────────────
ZYXWVUTSRQPONMLKJIHGFEDCBA321zyxwvutsrqponmlkjihgfedcba
ZYXWVUTSRQPONMLKJIHGFEDCBA321zyxwvutsrqponmlkjihgfedcba
ZYXWVUTSRQPONMLKJIHGFEDCBA321zyxwvutsrqponmlkjihgfedcba

       515         83        127
 

Stefan

Well-Known Member
With some low level unrolled loop inspiration, I present rev5, more than two times faster than rev2! You're bound to have certain types of strings that need to be reversed, so you can handle those sweet spot lengths with an unrolled loop:

Code:
function rev5 returns character (
    i_c as char
):

    def var cc as char no-undo.
    def var ilen as int no-undo.

    ilen = length( i_c ).
    case ilen:
           when 55 then
            assign
                cc    =    substring( i_c, 55, 1 )
                    +    substring( i_c, 54, 1 )
                    +    substring( i_c, 53, 1 )
                    +    substring( i_c, 52, 1 )
                    +    substring( i_c, 51, 1 )
                    +    substring( i_c, 50, 1 )
                    +    substring( i_c, 49, 1 )
                    +    substring( i_c, 48, 1 )
                    +    substring( i_c, 47, 1 )
                    +    substring( i_c, 46, 1 )
                    +    substring( i_c, 45, 1 )
                    +    substring( i_c, 44, 1 )
                    +    substring( i_c, 43, 1 )
                    +    substring( i_c, 42, 1 )
                    +    substring( i_c, 41, 1 )
                    +    substring( i_c, 40, 1 )
                    +    substring( i_c, 39, 1 )
                    +    substring( i_c, 38, 1 )
                    +    substring( i_c, 37, 1 )
                    +    substring( i_c, 36, 1 )
                    +    substring( i_c, 35, 1 )
                    +    substring( i_c, 34, 1 )
                    +    substring( i_c, 33, 1 )
                    +    substring( i_c, 32, 1 )
                    +    substring( i_c, 31, 1 )
                    +    substring( i_c, 30, 1 )
                    +    substring( i_c, 29, 1 )
                    +    substring( i_c, 28, 1 )
                    +    substring( i_c, 27, 1 )
                    +    substring( i_c, 26, 1 )
                    +    substring( i_c, 25, 1 )
                    +    substring( i_c, 24, 1 )
                    +    substring( i_c, 23, 1 )
                    +    substring( i_c, 22, 1 )
                    +    substring( i_c, 21, 1 )
                    +    substring( i_c, 20, 1 )
                    +    substring( i_c, 19, 1 )
                    +    substring( i_c, 18, 1 )
                    +    substring( i_c, 17, 1 )
                    +    substring( i_c, 16, 1 )
                    +    substring( i_c, 15, 1 )
                    +    substring( i_c, 14, 1 )
                    +    substring( i_c, 13, 1 )
                    +    substring( i_c, 12, 1 )
                    +    substring( i_c, 11, 1 )
                    +    substring( i_c, 10, 1 )
                    +    substring( i_c,  9, 1 )
                    +    substring( i_c,  8, 1 )
                    +    substring( i_c,  7, 1 )
                    +    substring( i_c,  6, 1 )
                    +    substring( i_c,  5, 1 )
                    +    substring( i_c,  4, 1 )
                    +    substring( i_c,  3, 1 )
                    +    substring( i_c,  2, 1 )
                    +    substring( i_c,  1, 1 )
                    .
        otherwise 
            cc = rev2( i_c ).
    end case.

    return cc.    

end function.

Watch it fly at ProgressAblDojo

My results:
Code:
        t1         t2         t3         t4         t5
---------- ---------- ---------- ---------- ----------
       164         29         42         40         12

Where you can also watch the not so fast fiddling with memptr bytes attempt (rev4)
 

Cecil

19+ years progress programming and still learning.
Combining them all with some tweaks to rev3():

Code:
FUNCTION Reverse RETURNS CHARACTER  (pInput AS CHARACTER):

    DEFINE VARIABLE cLastChar AS CHARACTER NO-UNDO.
    DEFINE VARIABLE cRest     AS CHARACTER NO-UNDO.
   
    IF LENGTH(pInput, "CHARACTER") = 1 THEN
        RETURN pInput.
       
    ASSIGN
        cLastChar = SUBSTRING (pInput, LENGTH (pInput, "CHARACTER") , 1)
        cRest     = SUBSTRING (pInput, 1, LENGTH (pInput, "CHARACTER") - 1)
        .
        
    RETURN cLastChar + Reverse (cRest).
   
END FUNCTION.


function rev2 returns character ( input vText as character ).

  DEFINE VARIABLE vCount AS INTEGER NO-UNDO.
  DEFINE VARIABLE vResult AS CHARACTER NO-UNDO.
 
  DO vCount = LENGTH(vText) TO 1 BY -1:
     vResult = vResult + SUBSTRING(vText,vCount,1).
  END.
 
  return vResult.
 
end.


function rev3 returns character ( input s as character ).

  define variable r as character no-undo.
  define variable c as character no-undo initial "!".
  define variable j as integer no-undo.
 
  do while c > "":
    assign
      j = j + 1
      c = substring( s, j, 1 )
      r = c + r
    .
  end.
 
  return r.
 
end.


define variable i   as integer no-undo.
define variable n   as integer no-undo initial 1000.

define variable t1  as integer no-undo.
define variable t2  as integer no-undo.
define variable t3  as integer no-undo.

define variable str as character no-undo.

str = "abcdefghijklmnopqrstuvwxyz123ABCDEFGHIJKLMNOPQRSTUVWXYZ".

display
  reverse( str ) format "x(80)" skip
     rev2( str ) format "x(80)" skip
     rev3( str ) format "x(80)" skip
.

etime( yes ).
do i = 1 to n:
  str = reverse( str ).
end.
t1 = etime.

etime( yes ).
do i = 1 to n:
  str = rev2( str ).
end.
t2 = etime.

etime( yes ).
do i = 1 to n:
  str = rev3( str ).
end.
t3 = etime.

display t1 t2 t3.

Results in:

Code:
        t1         t2         t3                       
───────────────────────────────────────────────────────
ZYXWVUTSRQPONMLKJIHGFEDCBA321zyxwvutsrqponmlkjihgfedcba
ZYXWVUTSRQPONMLKJIHGFEDCBA321zyxwvutsrqponmlkjihgfedcba
ZYXWVUTSRQPONMLKJIHGFEDCBA321zyxwvutsrqponmlkjihgfedcba

       515         83        127
Awesome Work Tom .

I must of sparked hamster in your mind .
 

TomBascom

Curmudgeon
Inspired by Stefan!

The use of SUBSTITUTE() avoids re-allocating the string with every character and instead only does that every 8 characters.

This seems to be about 50% faster than Osborne's rev2()!

Code:
function rev7 returns character ( input s as character ).

  define variable r as character no-undo.
  define variable j as integer no-undo.

  do while substring( s, j + 1 ) > "":
    assign
      r = substitute( "&1&2&3&4&5&6&7&8&9",
        substring( s, j + 8, 1 ),
        substring( s, j + 7, 1 ),
        substring( s, j + 6, 1 ),
        substring( s, j + 5, 1 ),
        substring( s, j + 4, 1 ),
        substring( s, j + 3, 1 ),
        substring( s, j + 2, 1 ),
        substring( s, j + 1, 1 ),
        r
      )
      j = j + 8
    .
  end.

  return r.

end.
 
Top