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

JamesBowen · Nov 21, 2021

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.

jdpjamesp · Nov 22, 2021

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

ProgressAblDojo

abldojo.services.progress.com

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

Osborne · Nov 22, 2021

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 · Nov 22, 2021

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 · Nov 23, 2021

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 · Nov 23, 2021

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)

JamesBowen · Nov 23, 2021

TomBascom said:

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 .

Stefan · Nov 24, 2021

Cecil said:
I must of sparked hamster in your mind .

Grammar Tips: Must Have or Must Of? | Proofed's Writing Tips

When people use the phrase "must of," they usually mean "must have." Find out how to avoid this error with Proofed's Writing Tips blog.

getproofed.com

TomBascom · Nov 24, 2021

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.

JamesBowen · Nov 24, 2021

Stefan said:
Grammar Tips: Must Have or Must Of? | Proofed's Writing Tips

When people use the phrase "must of," they usually mean "must have." Find out how to avoid this error with Proofed's Writing Tips blog.

getproofed.com

I'm from Norfolk, UK... We don't speak proper.

Rob Fitzpatrick · Nov 25, 2021

Cecil said:
I'm from Norfolk, UK... We don't speak proper.

"Two great peoples, divided by a common tongue."

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

JamesBowen

19+ years progress programming and still learning.

jdpjamesp

ProgressTalk.com Moderator

ProgressAblDojo

Osborne

Active Member

TomBascom

Curmudgeon

TomBascom

Curmudgeon

Stefan

Well-Known Member

JamesBowen

19+ years progress programming and still learning.

Stefan

Well-Known Member

Grammar Tips: Must Have or Must Of? | Proofed's Writing Tips

TomBascom

Curmudgeon

JamesBowen

19+ years progress programming and still learning.

Grammar Tips: Must Have or Must Of? | Proofed's Writing Tips

Rob Fitzpatrick

ProgressTalk.com Sponsor