QuestionWhat 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:
• Cecil and Osborne

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.

• Cecil

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

• Cecil

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

• Cringer and Cecil

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

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 .

Stefan

Well-Known Member
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.

• Osborne and Stefan

Cecil

19+ years progress programming and still learning.
I'm from Norfolk, UK... We don't speak proper. • Stefan

Rob Fitzpatrick

I'm from Norfolk, UK... We don't speak proper. "Two great peoples, divided by a common tongue."

D
Replies
0
Views
279
Dominique
D
J
Replies
0
Views
183
J
J
Replies
0
Views
50
Jessica Kent
J
J
Replies
0
Views
131
Jessica Kent
J
J
Replies
0
Views
196
J.D. Little
J