[DBP] String replication function

Author

Message

calcyman

17

Years of Service

User Offline

Joined: 31st Aug 2007

Location: The Uncertainty Principle

Posted: 12th Oct 2008 22:35

Link

The following code is much faster than replicating a string using conventional methods. It works similar to the string$() function in QBasic. The program below demonstrates the difference in speed. Try experimenting with the number of times for the string to be replicated.

+ Code Snippet

oldtime = timer()
For x = 1 to 1000
c$ = linearstr("Hello ",100)
Next x
print timer()-oldtime;" microseconds"

oldtime = timer()
For x = 1 to 1000
c$ = MultiplyString("Hello ",100)
Next x
print timer()-oldtime;" microseconds"

wait key

end

function linearstr(char as string, num as integer)

`This is the conventional method, which repeatedly appends the character to the end of the string.

For x = 1 to num
a$ = a$ + char
Next x

endfunction a$

function MultiplyString(char as string, num as integer)

`This method uses bitwise operations to achieve a faster speed.

filter = 67108864
For x = 0 to 26
a$ = a$ + a$
If (num && filter)>0 then a$ = a$ + char
filter = filter >> 1
Next x

endfunction a$

The bitwise method is faster when there are more than 30 repetitions.

The optomist's right, The pessimist's right.

Back to top

Profile PM Email

Sasuke

18

Years of Service

User Offline

Joined: 2nd Dec 2005

Location: Milton Keynes UK

Posted: 22nd Nov 2008 17:38

Link

Great work, this could come very handy with some of my parser functions

Though I have a no way near as fast as the bitwise method but twice a fast as the conventional method:

+ Code Snippet

function addString( char as string , num as integer )
   while n <= (num-1)
      inc n : a$ = a$ + char
   endwhile 
endfunction a$

I tried setting the num to 1000 to see what I get (around):

linearstr: 4800
addString: 2400
MultiplyString: 34 *WOW*

A dream is a fantasy, if you achieve that fantasy it was never a dream to begin with.

Back to top

Profile PM Email

IanM

Retired Moderator

22

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 22nd Nov 2008 18:54 Edited at: 22nd Nov 2008 18:55

Link

@Calcyman,
Once I understood how your function worked, I saw a method of making it a little faster by calculating the optimal value of 'filter' and looping until filter was empty.

+ Code Snippet

function NewMultiplyString(char as string, num as integer)

   `This method uses bitwise operations to achieve a faster speed.

   filter = num || (num >> 1)
   filter = filter || (filter >> 2)
   filter = filter || (filter >> 4)
   filter = filter || (filter >> 8)
   filter = (filter || (filter >> 16)) + 1

   while filter
      a$ = a$ + a$
      If (num && filter) then a$ = a$ + char
      filter = filter >> 1
   endwhile

endfunction a$

The stuff I added is a method of calculating the next higher power of 2 of 'num', then using that value for the filter.

I also wrote my own using my plug-in commands - on my system it's fastest until the number of duplications is approx 600, then the improved version of yours overtakes it again.

+ Code Snippet

function ReplaceString(char as string, num as integer)
   a$ = replace all$(padright$("", num), " ", char)
endfunction a$

Complete test code used:

Loops = 1000
Dups = 1000

sync on
sync rate 0

oldtime = timer()
For x = 1 to Loops
   c$ = linearstr("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - linearstr"
print len(c$)
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = AddString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - addstring"
print len(c$)
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = MultiplyString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - multiplystring"
print len(c$)
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = NewMultiplyString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - newmultiplystring"
print len(c$)
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = ReplaceString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - replacestring"
print len(c$)
print ""

sync off
wait key

end

function linearstr(char as string, num as integer)

`This is the conventional method, which repeatedly appends the character to the end of the string.

For x = 1 to num
      a$ = a$ + char
   Next x

endfunction a$

function addString( char as string , num as integer )
   while n <= (num-1)
      inc n : a$ = a$ + char
   endwhile
endfunction a$

function MultiplyString(char as string, num as integer)

`This method uses bitwise operations to achieve a faster speed.

filter = 67108864
   For x = 0 to 26
      a$ = a$ + a$
      If (num && filter)>0 then a$ = a$ + char
      filter = filter >> 1
   Next x

endfunction a$

function NewMultiplyString(char as string, num as integer)

`This method uses bitwise operations to achieve a faster speed.

filter = num || (num >> 1)
   filter = filter || (filter >> 2)
   filter = filter || (filter >> 4)
   filter = filter || (filter >> 8)
   filter = (filter || (filter >> 16)) + 1

while filter
      a$ = a$ + a$
      If (num && filter) then a$ = a$ + char
      filter = filter >> 1
   endwhile

endfunction a$

function ReplaceString(char as string, num as integer)
   a$ = replace all$(space$(num), " ", char)
endfunction a$

+ Code Snippet

Loops = 1000
Dups = 1000

sync on
sync rate 0

oldtime = timer()
For x = 1 to Loops
   c$ = linearstr("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - linearstr"
print len(c$)
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = AddString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - addstring"
print len(c$)
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = MultiplyString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - multiplystring"
print len(c$)
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = NewMultiplyString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - newmultiplystring"
print len(c$)
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = ReplaceString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - replacestring"
print len(c$)
print ""

sync off
wait key

end

function linearstr(char as string, num as integer)

   `This is the conventional method, which repeatedly appends the character to the end of the string.

   For x = 1 to num
      a$ = a$ + char
   Next x

endfunction a$

function addString( char as string , num as integer )
   while n <= (num-1)
      inc n : a$ = a$ + char
   endwhile
endfunction a$

function MultiplyString(char as string, num as integer)

   `This method uses bitwise operations to achieve a faster speed.

   filter = 67108864
   For x = 0 to 26
      a$ = a$ + a$
      If (num && filter)>0 then a$ = a$ + char
      filter = filter >> 1
   Next x

endfunction a$

function NewMultiplyString(char as string, num as integer)

   `This method uses bitwise operations to achieve a faster speed.

   filter = num || (num >> 1)
   filter = filter || (filter >> 2)
   filter = filter || (filter >> 4)
   filter = filter || (filter >> 8)
   filter = (filter || (filter >> 16)) + 1

   while filter
      a$ = a$ + a$
      If (num && filter) then a$ = a$ + char
      filter = filter >> 1
   endwhile

endfunction a$

function ReplaceString(char as string, num as integer)
   a$ = replace all$(space$(num), " ", char)
endfunction a$

[b]Utility plug-ins collection (updated 27/09/08) and
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

RedFlames

17

Years of Service

User Offline

Joined: 25th Aug 2007

Location: Germania

Posted: 24th Nov 2008 16:48 Edited at: 24th Nov 2008 16:49

Link

I want to enter too

Here is the testcode with 2 more functions:
PokeString & PokeString2 which use "poke String" (uh no really?!

) from matrix1utils. ( But i dont know how safe it is...)
The second one is slightly faster, and nearly as fast as ReplaceString, but calcyman's is still fastest as far as i have tested

And I added local-declarations to the functions, might improve it (1-2 microseconds maybe

).

Testcode:

Loops = 1000
Dups = 1000

sync on
sync rate 0

oldtime = timer()
For x = 1 to Loops
   c$ = linearstr("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - linearstr"
print len(c$)
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = AddString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - addstring"
print len(c$);c$
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = MultiplyString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - multiplystring"
print len(c$);c$
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = NewMultiplyString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - newmultiplystring"
print len(c$);c$
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = ReplaceString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - replacestring"
print len(c$);c$
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = PokeString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - pokestring"
print len(c$);c$
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = PokeString2("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - pokestring2"
print len(c$);c$
print ""

sync off
wait key

end

function linearstr(char as string, num as integer)

`This is the conventional method, which repeatedly appends the character to the end of the string.

For x = 1 to num
      a$ = a$ + char
   Next x

endfunction a$

function addString( char as string , num as integer )
   local a$ as String
   local n as integer
   while n <= (num-1)
      inc n : a$ = a$ + char
   endwhile
endfunction a$

function MultiplyString(char as string, num as integer)
   local filter as integer
   local a$ as string
   local x as integer
   `This method uses bitwise operations to achieve a faster speed.

filter = 67108864
   For x = 0 to 26
      a$ = a$ + a$
      If (num && filter)>0 then a$ = a$ + char
      filter = filter >> 1
   Next x

endfunction a$

function NewMultiplyString(char as string, num as integer)
   local filter as integer
   local a$ as string
   `This method uses bitwise operations to achieve a faster speed.

filter = num || (num >> 1)
   filter = filter || (filter >> 2)
   filter = filter || (filter >> 4)
   filter = filter || (filter >> 8)
   filter = (filter || (filter >> 16)) + 1

while filter
      a$ = a$ + a$
      If (num && filter) then a$ = a$ + char
      filter = filter >> 1
   endwhile

endfunction a$

function ReplaceString(char as string, num as integer)
   local a$ as String
   a$ = replace all$(space$(num), " ", char)
endfunction a$

Function PokeString(char as string ,num as integer )
	local a$ as String
	local ptr as dword
	local x,l as integer
	l=len(char)
	a$ = space$(num*l)
	ptr = Get String Ptr(a$)
	for x=0 to (num-1)*l step l
		Poke String ptr+x,char
	next
Endfunction a$

Function PokeString2(char as string ,num as integer )
	local a$ as String
	local ptr as dword
	local x,l as integer
	l=len(char)
	a$ = space$(num*l)
	ptr = Get String Ptr(a$)
	for x=0 to (num-1)
		Poke String ptr+x*l,char
	next
Endfunction a$

+ Code Snippet

Loops = 1000
Dups = 1000

sync on
sync rate 0

oldtime = timer()
For x = 1 to Loops
   c$ = linearstr("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - linearstr"
print len(c$)
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = AddString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - addstring"
print len(c$);c$
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = MultiplyString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - multiplystring"
print len(c$);c$
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = NewMultiplyString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - newmultiplystring"
print len(c$);c$
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = ReplaceString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - replacestring"
print len(c$);c$
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = PokeString("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - pokestring"
print len(c$);c$
print ""

oldtime = timer()
For x = 1 to Loops
   c$ = PokeString2("Hello ",Dups)
Next x
print timer()-oldtime;" microseconds - pokestring2"
print len(c$);c$
print ""

sync off
wait key

end

function linearstr(char as string, num as integer)

   `This is the conventional method, which repeatedly appends the character to the end of the string.

   For x = 1 to num
      a$ = a$ + char
   Next x

endfunction a$


function addString( char as string , num as integer )
   local a$ as String
   local n as integer
   while n <= (num-1)
      inc n : a$ = a$ + char
   endwhile
endfunction a$

function MultiplyString(char as string, num as integer)
   local filter as integer
   local a$ as string
   local x as integer
   `This method uses bitwise operations to achieve a faster speed.

   filter = 67108864
   For x = 0 to 26
      a$ = a$ + a$
      If (num && filter)>0 then a$ = a$ + char
      filter = filter >> 1
   Next x

endfunction a$

function NewMultiplyString(char as string, num as integer)
   local filter as integer
   local a$ as string
   `This method uses bitwise operations to achieve a faster speed.

   filter = num || (num >> 1)
   filter = filter || (filter >> 2)
   filter = filter || (filter >> 4)
   filter = filter || (filter >> 8)
   filter = (filter || (filter >> 16)) + 1

   while filter
      a$ = a$ + a$
      If (num && filter) then a$ = a$ + char
      filter = filter >> 1
   endwhile

endfunction a$

function ReplaceString(char as string, num as integer)
   local a$ as String
   a$ = replace all$(space$(num), " ", char)
endfunction a$

Function PokeString(char as string ,num as integer )
	local a$ as String
	local ptr as dword
	local x,l as integer
	l=len(char)
	a$ = space$(num*l)
	ptr = Get String Ptr(a$)
	for x=0 to (num-1)*l step l
		Poke String ptr+x,char
	next
Endfunction a$

Function PokeString2(char as string ,num as integer )
	local a$ as String
	local ptr as dword
	local x,l as integer
	l=len(char)
	a$ = space$(num*l)
	ptr = Get String Ptr(a$)
	for x=0 to (num-1)
		Poke String ptr+x*l,char
	next
Endfunction a$

Back to top

Profile PM Email Website

IanM

Retired Moderator

22

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 24th Nov 2008 21:45

Link

Well, if you really want to get competitive about it

, try this one:

+ Code Snippet

function CopyMem(char as string, num as integer)
   local filter as integer
   local a$ as string
   local SourceLen as integer
   local CurrentLen as integer
   local Ptr as dword
   local CharPtr as dword

   filter = num || (num >> 1)
   filter = filter || (filter >> 2)
   filter = filter || (filter >> 4)
   filter = filter || (filter >> 8)
   filter = (filter || (filter >> 16)) + 1

   SourceLen = len(char)
   CurrentLen = 0

   a$ = space$(num * SourceLen)

   Ptr = get string ptr(a$)
   CharPtr = get string ptr(Char)

   while filter
      copy memory Ptr + CurrentLen, Ptr, CurrentLen
      inc CurrentLen, CurrentLen
      If (num && filter)
         copy memory Ptr + CurrentLen, CharPtr, SourceLen
         inc CurrentLen, SourceLen
      endif
      filter = filter >> 1
   endwhile
endfunction a$

At 1000x1000, it runs almost 4 times faster than the 'NewMultiplyString' function on my system (11 ms compared to 42ms).

Utility plug-ins collection (updated 27/09/08) and
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

Sorry your browser is not supported!

Code Snippets / [DBP] String replication function