Reverse a string

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
Tourist Trap
Posts: 2933
Joined: Jun 02, 2015 16:24

Reverse a string

Postby Tourist Trap » Jan 11, 2017 15:22

The only trick here is that the macro used take a string variable as argument or as well a raw string. Maybe it can be extended to reverse a number also?

Code: Select all

#macro _REVERSESTRING( s , t )
    t = ""
    #if typeOf(s)=typeOf(string)
        for i as integer = len(s) - 1 to 0 step -1
            t &= chr((s)[i])
        next i
    #else
        for i as integer = len(*(cast(zstring ptr, @(s)))) - 1 to 0 step -1
            t &= chr((s)[i])
        next i
    #endIf
#endMacro

dim as string outstr

_REVERSESTRING( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" , outstr)
? outstr

dim as string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
_REVERSESTRING(s , outstr)
? outstr

'(eof)

'(eof)
I3I2UI/I0
Posts: 90
Joined: Jun 03, 2005 10:39
Location: Germany

Re: Reverse a string

Postby I3I2UI/I0 » Jan 11, 2017 19:26

Hi, as asm

Code: Select all

Function Revers (ByVal txt As String) As string
 Dim lt As Long
 Dim As String Text = txt
 lt = Len(Text)
 If lt > 1 Then
  asm
   mov eax, [Text]   'Anfang des String im RAM
   mov ebx, [lt]   'Laenge des String
   mov esi, eax
   add eax, ebx
   dec eax
   mov edi, eax    'letzes Zeichen des String
   mov ecx,ebx
   shr ecx         'ecx =lt \ 2 ;Laufvariable
   lnext:
    mov al, [esi]  'al = Anfang
    mov ah, [edi]  'ah = Ende
    mov [edi], al  'Ende = al
    mov [esi], ah  'Anfang = ah
    inc esi        'Anfang + 1
    dec edi        'Ende - 1
   loop lnext      'wie for .. next
  End asm
 End If
 Function = Text
End Function

Dim t As String
t = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

Print Revers(" !dlroW olleH ")
Print t
Print Revers (t)
Sleep

https://forum.qbasic.at/viewtopic.php?p=12224#12224
https://www.freebasic-portal.de/code-beispiele/string-funktionen/asm-text-revers-srever-txet-28.html
Tourist Trap
Posts: 2933
Joined: Jun 02, 2015 16:24

Re: Reverse a string

Postby Tourist Trap » Jan 11, 2017 22:10


Very nice, probably necessary for intensive reversing (asm performance).

From my side I propose this extension to numerical values of the original macro above, with the same level of generality of the input, but something is limitating the use of STR(), so it requires STR2() to be fixed (question of return byref...).

Code: Select all

 '_macro that can revert a string input, or something numeric
'_output as string

function str2(byref s as const string) byref as const string
    return s
end function

#macro _REVERSESTRING( in_ , out_ )
    out_ = ""
    #if typeOf(in_)=typeOf(string)
        for i as integer = len(in_) - 1 to 0 step -1
            out_ &= chr((in_)[i])
        next i
    #elseIf typeOf(in_)=typeOf(integer)
        for i as integer = len(str(in_)) - 1 to 0 step -1
            out_ &= chr((str2(str(in_)))[i])
        next i
    #elseIf typeOf(in_)=typeOf(double)
        for i as integer = len(str(in_)) - 1 to 0 step -1
            out_ &= chr((str2(str(in_)))[i])
        next i
    #else
        for i as integer = len(*(cast(zstring ptr, @(in_)))) - 1 to 0 step -1
            out_ &= chr((in_)[i])
        next i
    #endIf
#endMacro

'------------------------------------------------------------
'--------------------------------------------------------TEST

dim as string outstr

'strings
_REVERSESTRING( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" , outstr)
? outstr

dim as string in_str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
_REVERSESTRING(in_str , outstr)
? outstr

'integers
_REVERSESTRING(1234567890 , outstr)
? outstr

dim as integer in_int = 1234567890
_REVERSESTRING(in_int , outstr)
? outstr

'doubles
'terminal zeros are unfortunately lost for decimal numbers
_REVERSESTRING(1234.567890 , outstr)
? outstr

dim as double in_dbl = 1234.567890
_REVERSESTRING(in_dbl , outstr)
? outstr


'(eof)
dodicat
Posts: 6687
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Reverse a string

Postby dodicat » Jan 11, 2017 23:28

Hi TT.
Literal string reverse:

Code: Select all

screen 14

sub gnirtSwarD(s as string,x as long=0,y as long=0)
#define map(a,b,x,c,d) ((d)-(c))*((x)-(a))/((b)-(a))+(c)
var e=8*len(s)
dim as any ptr im(1)={imagecreate(e,16),imagecreate(e,16)}
draw string im(0),(1,0),s
for x as long=0 to e
    for y as long=0 to 16
        if point(x,y,im(0))=15 then
        var x1=map(0,e,x,e,0)
        pset im(1),(x1,y)
        end if
    next
next
put(x,y),im(1)
imagedestroy Im(0)
imagedestroy Im(1)
end sub

gnirtSwarD("ABCDEFGHIJKLMNOPQRSTUVWXYZ",50,50)
sleep
 
ganache
Posts: 45
Joined: Aug 04, 2016 9:25

Re: Reverse a string

Postby ganache » Jan 12, 2017 9:05

My method:

Dim As String s
Dim As Integer i
input "Enter a string:";s
for i=len(s) to 0 step -1
print chr(s[i]);"";
next i
Sleep
End

Output
Enter a string:? Terminator 2:Judgment Day
yaD tnemgduJ:2 rotanimreT
BasicCoder2
Posts: 3586
Joined: Jan 01, 2009 7:03
Location: Australia

Re: Reverse a string

Postby BasicCoder2 » Jan 12, 2017 9:33

Or as an added function (command).

Code: Select all

function reverseString(forward as string) as string
    dim as string reverse
    for i as integer = len(forward) to 0 step -1
        reverse = reverse & chr(forward[i])
    next i
    return reverse
end function

Dim As String s
input "Enter a string:";s
print reverseString(s)

Sleep
fxm
Posts: 9947
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Reverse a string

Postby fxm » Jan 12, 2017 10:20

Code: Select all

Function reverseString2 (Byval s As String) As String
  Dim As Integer l = Len(s)
  For i As Integer = 0 To l\2-1
    Swap s[i], s[l-1-i]
  Next i
  Return s
End Function
BasicCoder2
Posts: 3586
Joined: Jan 01, 2009 7:03
Location: Australia

Re: Reverse a string

Postby BasicCoder2 » Jan 12, 2017 21:35

@fxm,
Yes clearly the best solution. I notice the ASM version does it the same way.
.
dodicat
Posts: 6687
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Reverse a string

Postby dodicat » Jan 12, 2017 22:42

Basiccoder2.
Your own method is efficient if you fully utilise string indexing.
(even although you do loop the whole string).

Code: Select all

Function reverseString2 (Byval s As String) As String 'fxm
  Dim As Integer l = Len(s)
  For i As Integer = 0 To l\2-1
    Swap s[i], s[l-1-i]
  Next i
  Return s
End Function

Function reverseString3 (byref s As String) As String'basiccoder2 -- tweaked
dim as long L=len(s)-1
dim as string t=string(L+1,0)
for n as long=L to 0 step -1
    t[L-n]=s[n]
next
return t
end function

dim as string s="ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"
for n as long=1 to 22
    s+=s
next
print "Length of string ";len(s)
do
sleep 50
dim as string ans
dim as double t
t=timer
ans= reversestring2(s)
print timer-t,left(ans,72),"fxm"
sleep 50
t=timer
ans= reversestring3(s)
print timer-t,left(ans,72),"other"
print
loop until inkey=chr(27)
sleep
 
dodicat
Posts: 6687
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Reverse a string

Postby dodicat » Jan 12, 2017 23:32

I notice that in the method by fxm, instead of passing a string byval, it is much faster to pass the string byref and make a copy inside the function.
VIZ:

Code: Select all

Function reverseString2 (Byref s1 As String) As String 'fxm
  dim as string s=s1
  Dim As Integer l = Len(s)
  For i As Integer = 0 To l\2-1
    Swap s[i], s[l-1-i]
  Next i
  Return s
End Function

Function reverseString3 (byref s As String) As String'basiccoder2 -- tweaked
dim as long L=len(s)-1
dim as string t=string(L+1,0)
for n as long=L to 0 step -1
    t[L-n]=s[n]
next
return t
end function

dim as string s="ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"
for n as long=1 to 22
    s+=s
next
print "Length of string ";len(s)
do
sleep 50
dim as string ans
dim as double t
t=timer
ans= reversestring2(s)
print timer-t,left(ans,72),"fxm"
sleep 50
t=timer
ans= reversestring3(s)
print timer-t,left(ans,72),"other"
print
loop until inkey=chr(27)

 
fxm
Posts: 9947
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Reverse a string

Postby fxm » Jan 13, 2017 7:08

No, that must be equivalent because a string is a pseudo "complex" object.
When one passes to a procedure a complex object (ie: of a Type with destructor or copy-constructor) for a parameter declared byval, in fact the caller does a copy of this object and this copy is passed byref to the procedure (complex objects are always passed by reference).

In fact complex objects are always passed by reference, either directly or through a copy.
Tourist Trap
Posts: 2933
Joined: Jun 02, 2015 16:24

Re: Reverse a string

Postby Tourist Trap » Jan 13, 2017 13:20

dodicat wrote:I notice that in the method by fxm, instead of passing a string byval, it is much faster to pass the string byref and make a copy inside the function.

Only for the long strings, when you build little strings we see nothing really clear.

Same here, even for long string, that's unclear, somehow random? Should theorically byref as const string be fastest, slowest? Maybe it's a totally dumb question, but it had to be asked at least once in a life :-)

Code: Select all

Function reverseString2 (Byref s1 As const String) As const String 'fxm
  dim as string s=s1
  Dim As Integer l = Len(s)
  For i As Integer = 0 To l\2-1
    Swap s[i], s[l-1-i]
  Next i
  Return s
End Function

Function reverseString3 (Byref s1 As String) As String 'fxm
  dim as string s=s1
  Dim As Integer l = Len(s)
  For i As Integer = 0 To l\2-1
    Swap s[i], s[l-1-i]
  Next i
  Return s
End Function


dim as string s="ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"
for n as long=1 to 22
    s+=s
next

print "Length of string ";len(s)

do
        sleep 50
        dim as string ans
        dim as double t
        t=timer
        ans= reversestring3(s)
        print timer-t,left(ans,72),"fxm "
        sleep 50
        t=timer
        ans= reversestring2(s)
        print timer-t,left(ans,72),"fxm byref const"
        print
loop until inkey=chr(27)
dodicat
Posts: 6687
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Reverse a string

Postby dodicat » Jan 13, 2017 14:09

Here are my results for a straight comparison of byval and byref (no const).

Code: Select all

Length of string  150994944
 0.8946248914876378         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byref
 0.8182067048352479         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byval

 0.7169296806865049         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byref
 0.8183353687887518         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byval

 0.7150281230147328         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byref
 0.8181683793949333         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byval

 0.7146794299570445         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byref
 0.8178699884865779         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byval

 0.714382065600077          0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byref
 0.8175089765236834         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byval

 0.7144836964636596         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byref
 0.8168889256795779         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byval

 0.7152765539680104         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byref
 0.8218955282830791         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byval

 0.7146058587973698         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byref
 0.8206848550554184         0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA            byval

Press any key to continue . . .


32 bit -gen gas
Tourist Trap
Posts: 2933
Joined: Jun 02, 2015 16:24

Re: Reverse a string

Postby Tourist Trap » Jan 13, 2017 14:28

Not sure there is any pattern?
Image
dodicat
Posts: 6687
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Reverse a string

Postby dodicat » Jan 13, 2017 14:36

here is the testing code for my results:

Code: Select all

Function reverseString2 (Byref s1 As String) As const String 'fxm
  dim as string s=s1
  Dim As Integer l = Len(s)
  For i As Integer = 0 To l\2-1
    Swap s[i], s[l-1-i]
  Next i
  Return s
End Function

Function reverseString3 (Byval s As String) As String 'fxm
  Dim As Integer l = Len(s)
  For i As Integer = 0 To l\2-1
    Swap s[i], s[l-1-i]
  Next i
  Return s
End Function


dim as string s="ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"
for n as long=1 to 22
    s+=s
next

print "Length of string ";len(s)

do
        sleep 50
        dim as string ans
        dim as double t
        t=timer
        ans= reversestring2(s)
        print timer-t,left(ans,72),"byref "
        sleep 50
        t=timer
        ans= reversestring3(s)
        print timer-t,left(ans,72),"byval"
        print
loop until inkey=chr(27)

I am not just nitpicking with this, I have abandoned using byval strings in my bigint functions, they are noticeably slower.

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 2 guests