ReverseString()

[AND51]

Hello!

Here's my code to reverse a string (ABC => CBA), have fun!

Code: Select all

Procedure.s reverseString(text.s)
	If text
		ProcedureReturn reverseString(PeekS(@text+SizeOf(Character)))+PeekS(@text, 1)
	EndIf
EndProcedure

Debug reverseString("I love PureBasic!")

What about a nice competition? Do you think you can beat this?

[Trond]

> 10 times faster:

Code: Select all

Procedure.s ReverseString3(String.s)
  Protected *Start.Character = @String
  Protected *Nd.Character = *Start + Len(String)-1
  While *Start < *Nd
    Swap *Start\c, *Nd\c
    *Start + SizeOf(Character)
    *Nd - SizeOf(Character)
  Wend
  ProcedureReturn String
EndProcedure

[AND51]

Very impressive!
You're so fast, because your exchanging data in which there is a great distance, similar to the QuickSort algorithm.


//Edit: Your code does not work with unicode! Can you correct this?

[netmaestro]

It's fast because arithmetic operations guided by pointers are far faster than stringhandling functions. Little tweak and it's good to go for Ascii or Unicode:

Code: Select all

Procedure.s ReverseString3(String.s) 
  Protected *Start.Character = @String 
  Protected *Nd.Character 
  *Nd.Character = *Start + Len(String)*SizeOf(character)-SizeOf(character)
  While *Start < *Nd 
    Swap *Start\c, *Nd\c 
    *Start + SizeOf(Character) 
    *Nd - SizeOf(Character) 
  Wend 
  ProcedureReturn String 
EndProcedure

[AND51]

Very nice! Both of you did your job well!

[Shardik]

It's still possible to tweak Trond's solution a little bit further by implementing it in native Assembler:

Code: Select all

Procedure.S ReverseString(String.S)
  Protected StringLength.L

  StringLength = StringByteLength(String)

  !   MOV EAX,DWORD[p.v_String]
  !   MOV ESI,EAX
  !   MOV EDI,EAX
  !   ADD EDI,DWORD[p.v_StringLength]
  !   DEC EDI
  !CheckIfReady:
  !   CMP ESI,EDI
  !   JNB Ready
  !   MOV BL,[ESI]
  !   MOV BH,[EDI]
  !   MOV [EDI],BL
  !   MOV [ESI],BH
  !   INC ESI
  !   DEC EDI
  !   JMP CheckIfReady
  !Ready:

  ProcedureReturn String
EndProcedure


Count.L
StartTime.L

StartTime = ElapsedMilliseconds()

Repeat 
  ReverseString("I love PureBASIC!")
  Count + 1 
Until ElapsedMilliseconds() - StartTime >= 1000 

MessageRequester("Cycle count", Str(Count), #MB_ICONINFORMATION)

Measured cycles on my PC:
AND51: ~ 0.16 million
Trond + netmaestro: ~ 2.1 million
Shardik: ~ 2.4 million

It's always quite interesting to compare different algorithms and in most cases my predictions have been proven wrong...
I've also tried to copy 4 bytes at once which should be faster but with the above short example string the payoff for aligning the string on a word boundary and fill it up with spaces to a size divideable by 8 takes too much time.

Even my first approach of using two strings

Code: Select all

Procedure.S ReverseString(String1.S)
  Protected String2.S
  Protected StringLength.L

  StringLength = Len(String1)
  String2 = Space(StringLength)

!   MOV ESI,DWORD[p.v_String1]
!   MOV EDI,DWORD[p.v_String2]
!   MOV ECX,DWORD[p.v_StringLength]
!   ADD EDI,ECX
!   DEC EDI
!CopyLoop:
!   MOV AL,[ESI]
!   MOV [EDI],AL
!   INC ESI
!   DEC EDI
!   LOOP CopyLoop
!   MOV EAX,EDI

  ProcedureReturn String2
EndProcedure

is quite slow with about 1.4 million cycles. Unfortuately it's not possible to make use of the powerful move string instruction MOVS with REP prefix because one index register has to be incremented and the other has to be decremented...