Reversing a string
 

News:

29 December 2022 - PtokaX 0.5.3.0 (20th anniversary edition) released...
11 April 2017 - PtokaX 0.5.2.2 released...
8 April 2015 Anti child and anti pedo pr0n scripts are not allowed anymore on this board!
28 September 2015 - PtokaX 0.5.2.1 for Windows 10 IoT released...
3 September 2015 - PtokaX 0.5.2.1 released...
16 August 2015 - PtokaX 0.5.2.0 released...
1 August 2015 - Crowdfunding for ADC protocol support in PtokaX ended. Clearly nobody want ADC support...
30 June 2015 - PtokaX 0.5.1.0 released...
30 April 2015 Crowdfunding for ADC protocol support in PtokaX
26 April 2015 New support hub!
20 February 2015 - PtokaX 0.5.0.3 released...
13 April 2014 - PtokaX 0.5.0.2 released...
23 March 2014 - PtokaX testing version 0.5.0.1 build 454 is available.
04 March 2014 - PtokaX.org sites were temporary down because of DDOS attacks and issues with hosting service provider.

Main Menu

Reversing a string

Started by bastya_elvtars, 02 January, 2005, 01:22:10

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

bastya_elvtars

Made for fun but decided to share.

function revrse(string)
	local msg=""
	for a=strlen(string),1,-1 do
		msg=msg..(strsub(string,a,a))
	end return msg
end

SendToAll(revrse("I do not speak polish."))
Everything could have been anything else and it would have just as much meaning.

plop

here's 1 made by rabbitwombat.
function strrev(str)
	if(strlen(str) < 2) then
		return str;
	else
		str = gsub(str, "^(.)(.*)(.)$", function(a, b, c) return c..strrev(b)..a; end, 1);
		return str;
	end
end

plop
http://www.plop.nl lua scripts/howto\'s.
http://www.thegoldenangel.net
http://www.vikingshub.com
http://www.lua.org

>>----> he who fights hatred with hatred, drives the spreading of hatred <----<<

chill

#2
seems not to be as trivial as I thaught ;)

well did some tests, the thing with rabbits function
is that to call a function and get a return value
the program writes on the stack, and here is the problem, stack overflow with large strings,
so that is not the optimal function,

now I thaught up some other functions and did some tests,
the best one is number3, basta_elvars you func is not bad
it survives the long string at least, but in the end it
is almost 10 seconds slower, but truly who needs such longs strings reversed, but just in case....

here my testing code (LUA 5)
function revrse(sstring)
	local msg=""
	for a=string.len(sstring),1,-1 do
		msg=msg..(string.sub(sstring,a,a))
	end
	return msg
end


function strrev(str)
	if(string.len(str) < 2) then
		return str;
	else
		str = string.gsub(str, "^(.)(.*)(.)$", function(a, b, c)
			return c..strrev(b)..a
		end)
		return str;
	end
end

function strrev2( str )

	if(string.len(str) < 2) then
		return str;
	else
		strlen = string.len(str)
		str = string.sub(str,strlen,strlen)..strrev2(string.sub(str,2,strlen-1))..string.sub(str,1,1)
		return str;
	end
end

function strrev3( str )

	if(string.len(str) < 2) then
		return str;
	else
		local revstr = ""
		strlen = string.len(str)

		-- check for for odd elements
		if ( math.mod( strlen, 2 ) == 1 ) then
			-- middle of the string
			local pos = strlen/2 + 0.5
			revstr = string.sub( str, pos, pos )

			for i = 1, pos-1 do
				revstr = string.sub( str, pos+i, pos+i)..revstr..string.sub( str, pos-i, pos-i )
			end
		-- is even
		else
			local pos = strlen/2
			for i = 1, pos do
				revstr = string.sub( str, pos+i, pos+i)..revstr..string.sub( str, pos-i, pos-i )
			end
		end
		return revstr;
	end
end
	



function Main()

	-- create a loooooooong string

	test = ""

	for i = 1,100000 do

		test = test.."ab"
	end

	t0 = os.clock()

	revrse(test)

	t1 = os.clock()

	--print( strrev( test ) )
	--strrev( test )

	t2 = os.clock()

	--print( strrev2( test ) )
	--strrev2( test )

	t3 = os.clock()

	--print( strrev3( test ) )
	strrev3( test )

	t4 = os.clock()

	print("0. clockdiff: "..(t1-t0))

	print("1. clockdiff: "..(t2-t1))

	print("2. clockdiff: "..(t3-t2))

	print("3. clockdiff: "..(t4-t3))



end

Main()

some results

> dofile( "strrev.lua" )
0. clockdiff: 38.234
1. clockdiff: 0
2. clockdiff: 0
3. clockdiff: 27.516
> dofile( "strrev.lua" )
0. clockdiff: 39.812
1. clockdiff: 0
2. clockdiff: 0
3. clockdiff: 28.641

bastya_elvtars

thx chill for your research and your positive critics ;)

maybe this whole hing has no point in ptokax scripts, where we use chatlimit, but hey this is LUA board, not ptokax board!

(On DC++ forum they said we are stuck with ptokax here. Seems they are unable to understand that the ptokax LUA api does not drop the generic lua libraries. :D)
Everything could have been anything else and it would have just as much meaning.

chill

#4
well I think thiss is the biggest LUA forum anyway,
although it is actually about Ptokax..  but not sure

well I had a few more ideas
I thaugh of if maybe something like

for x = 1,y do
  string = string.."abcd"
  or
  string = "abcd"..string
end

could make some time difference and it doesn't,
now the only thing that makes strrev3 faster than yours is basically, that is handles more chars at a time,

so the final thing is to just try and reverse as many chars as possible at a time, well I am a bit lazy so I stoped at 10 here, dunno, if there is a so called 'asymptote' where
adding more chars to handle @ once wouldn't make any difference anymore well dunno, maybe someone wants to try it out...

function revrse(sstring)
	local msg=""
	for a=string.len(sstring),1,-1 do
		msg=msg..(string.sub(sstring,a,a))
	end
	return msg
end

function strrev3( str )

	if(string.len(str) < 2) then
		return str;
	else
		local revstr = ""
		strlen = string.len(str)

		-- check for for odd elements
		if ( math.mod( strlen, 2 ) == 1 ) then
			-- middle of the string
			local pos = strlen/2 + 0.5
			revstr = string.sub( str, pos, pos )

			for i = 1, pos-1 do
				revstr = string.sub( str, pos+i, pos+i)..revstr..string.sub( str, pos-i, pos-i )
			end
		-- is even
		else
			local pos = strlen/2
			for i = 1, pos do
				revstr = string.sub( str, pos+i, pos+i)..revstr..string.sub( str, pos-i, pos-i )
			end
		end
		return revstr;
	end
end

function strrev10( str )

	-- create needed variables
	local revstr=""
	local strlen = string.len( str )

	-- reverse 10 chars of the string
	for i = strlen, 1, -10 do
		revstr = revstr..
			string.sub( str, i, i)..string.sub( str, i-1, i-1)..
			string.sub( str, i-2, i-2)..string.sub( str, i-3, i-3)..
			string.sub( str, i-4, i-4)..string.sub( str, i-5, i-5)..
			string.sub( str, i-6, i-6)..string.sub( str, i-7, i-7)..
			string.sub( str, i-8, i-8)..string.sub( str, i-9, i-9)

	end

	-- cut end of string if strrev is longer than original string
	local strlenrev = string.len( revstr )
	if strlenrev > strlen then
		revstr = string.sub( revstr, 1, strlen )
	end

	return revstr
end

function Main()

	local t0,t1,t2,t3

	-- create a loooooooong string
	t0 = os.clock()
	--if not test then
		test = ""
		for i = 1,30000 do

			test = test.."abcdefghij"

		end
	--end
	print( "String Lenght = "..string.len( test ) )
	print( "Time to create string: "..( os.clock() - t0 ) )


	-- do tests

	t0 = os.clock()

	--print( revrse(test) )
	revrse(test)

	t1 = os.clock()

	--print( strrev( test ) )
	strrev3( test )

	t2 = os.clock()

	--print( strrev10( test ) )
	strrev10( test )

	t3 = os.clock()

	print("0. clockdiff: "..(t1-t0))

	print("1. clockdiff: "..(t2-t1))

	print("2. clockdiff: "..(t3-t2))

end

Main()

> dofile( "strrev.lua" )
String Lenght = 10000
Time to create string: 0.014999999999986
0. clockdiff: 0.063000000000045
1. clockdiff: 0.061999999999955
2. clockdiff: 0.01600000000002
> dofile( "strrev.lua" )
String Lenght = 100000
Time to create string: 1.031
0. clockdiff: 11.266
1. clockdiff: 6.4059999999999
2. clockdiff: 1.109
> dofile( "strrev.lua" )
String Lenght = 200000
Time to create string: 4.391
0. clockdiff: 41.828
1. clockdiff: 27.656
2. clockdiff: 4.266
> dofile( "strrev.lua" )
String Lenght = 300000
Time to create string: 12.61
0. clockdiff: 125
1. clockdiff: 69.937
2. clockdiff: 12.719

Sedulus

[0:wza:bin]$ ./lua rev.lua
rev_merge: zyxwvutsrqponmlkjihgfedcba
strrev10 : zyxwvutsrqponmlkjihgfedcba
String Lenght = 163840
Time to create string: 0
strrev10 : 18.03
rev_merge: 0.75

sounds like...
merge sort
...sort of
function rev_merge( str )
        local h = string.len( str ) / 2
        h = h + math.mod( h, 2 ) / 2
        if h < 40 then
                return rev_substr( str )
        end
        return rev_merge( string.sub( str, h + 1 ) ) ..
                rev_merge( string.sub( str, 1, h ) )
end

-- this is the revrse(sstring) from chill's code
function rev_substr( str )
        local out = ""
        for a = string.len( str), 1, -1 do
                out = out .. string.sub( str, a, a )
        end
        return out
end
the 40 in the above example sounds about right (trial and error), using 10 there takes about the same time as using 100
       local t0,t1,t2,t3
        print( "rev_merge: "..rev_merge("abcdefghijklmnopqrstuvwxyz") )
        print( "strrev10 : "..strrev10("abcdefghijklmnopqrstuvwxyz") )
        t0 = os.clock()
        local test = "abcdefghij"
        for i = 1,14 do
                test = test..test
        end

        print( "String Lenght = "..string.len( test ) )
        print( "Time to create string: "..( os.clock() - t0 ) )

        t2 = os.clock()
        strrev10( test )
        t3 = os.clock()
        rev_merge( test )
        t4 = os.clock()

        print("strrev10 : "..(t3-t2))
        print("rev_merge: "..(t4-t3))

chill

thx for sharing this :)
that is the ultimate string reverse then...

maybe you wanna explain why it is soo fats, and why I don't get any stack overflow,
I don't get it,
This is when you realise you know nothing

well great code

but
-- this is the revrse(sstring) from chill's code
its not even mine :(, its bastya_elvtars

chill

I think I have the conclusion.. but dunno
seems as this is like a binary reverse

such as 2^x  =  stringlenght   where x
would be the number of stack pushes

so if we state  we would have a possibility to
push the stack around 100 times
the string would need to be 1.26e+30 chars long  lol,
till stack overflow, so I guess never.

but why should then a normal reverse be faster than the binary reverse when beeing lower than 40, guess its the calculation or?

Sedulus

okay, this should explain some:
** Why the stack doesn't overflow **

For a moment, forget about the jump to the linear rev_substr,
and use only rev_merge:

    function rev_merge( str )
        local h = string.len( str )
        if h <= 1 then
            return str
        end
        h = h / 2 + math.mod( h, 2 ) / 2
        return rev_merge( string.sub( str, h + 1 ) ) ..
                rev_merge( string.sub( str, 1, h ) )
    end

("local h = string.len( str ) / 2 ; h = h + math.mod( h, 2 ) / 2"
 wasn't fully correct, but the whole math.mod can be abandoned completely
 as string.sub seems to accept floats as well and converts them properly,
 so it didn't matter that is was broken ;) )


Assume a string length of 200,
now we have a maximum stack depth of 8 (log(200)/log(2)=8).

Why?

Every time rev_merge is called, the following happens:
1- the second half of the string is copied
2- rev_merge is called
3- first when we've hit the final node where string.len( str ) is 1 or 0,
   we return to the second deepest node
4- there, we copy the first half of the string
5- GOTO 1

So, we have a tree, that gets traversed like this:

Let input be "abcd", the calling order is between brackets.
        abcd(0)
   cd(1)       ab(4)
d(2)  c(3)  b(5)  a(6)

Here, there are at most log(4)/log(2) = 2 functions on the stack.


When the string size is 163840, the stack size is at most
log(163840)/log(2) = 18. And 18, well yes, that's peanuts.


** Why it's fast **

I'm not entirely sure, but I guess lua has a problem juggling long strings.

This could be seen from your own example:
	String Lenght = 300000 
	Time to create string: 12.61
30.000 iterations took 12.61 seconds.
No wonder then that 300.000 reverse operation takes:
	0. clockdiff: 125
10 times as much time.


So, what we do, is cut the string in half. And work on that, namely, cut it in
half again ;)

At one point this gets inefficient though. Where the time to do a function call
and string splitting takes more time than a simple string traversal, we switch
to the simpler reverse method, which turns out to be faster.

chill

that explains it all, thx
well now that I understand it how it works,
i ask myself, is there any practical use for
this method of reversing strings?

SMF spam blocked by CleanTalk