Strip/replace double or multiple spaces with single

[Keya]

I needed to replace all multiple spaces to single, but the nature of ReplaceString() only gets half the work done when you're replacing a string with half of the exact same string, like two spaces with one:

Code: Select all

mystr.s = "one        two"
mystr = ReplaceString(mystr, "  ", " ")
Debug(mystr)

This replaces the 8 space chars with 4, so there are still multiple spaces left over.

To solve this it seems a loop is required?? first to check if there are any double-spaces left, and then replacing if required:

Code: Select all

Procedure.s StripDualSpaces_ReplaceString(sStr.s)    ;Win+Linux+Mac, 32+64, Unicode+Ascii
  Repeat
    If FindString(sStr, "  ") = 0: Break: EndIf    ;ReplaceString("  " with " ") doesnt work with multiple spaces,
    sStr.s = ReplaceString(sStr, "  ", " ")        ;so we need to repeatedly call it until there are no more.
  ForEver
  ProcedureReturn sStr
EndProcedure

But i need to do this lottttts and there should be a more efficient way than looping like that, so i wrote what i guess is a typical(?) "copy backwards valid chars from ptrB to ptrA", incrementing both pointers as necessary (and for speed reasons this modifies the string you give it - it doesn't return a separate string):

Code: Select all

DisableDebugger
Procedure StripDualSpacesPBptr(*pstr)    ;Win+Linux+Mac, 32+64, Unicode+Ascii
  Protected *pbyteA.Character, *pbyteB.Character, SpaceFlag.i, Increment.i
  *pbyteA = *pstr
  *pbyteB = *pbyteA
  CompilerIf #PB_Compiler_Unicode = 1
    Increment = 2
  CompilerElse
    Increment = 1
  CompilerEndIf
  Repeat
    If *pbyteB\c = 0       ;Char=Null
      Break
    ElseIf *pbyteB\c = 32  ;Char=Space
      If SpaceFlag = 0 
        SpaceFlag = 1       ;(1st space)
        *pbyteA\c = *pbyteB\c
        *pbyteA+Increment:  *pbyteB+Increment
      Else                 ;(2nd+ space)
        *pbyteB+Increment
      EndIf
    Else                    ;Char=Other (not space or null)
      SpaceFlag = 0
      *pbyteA\c = *pbyteB\c  
      *pbyteA+Increment:  *pbyteB+Increment
    EndIf
  ForEver
  *pbyteA\c = 0
EndProcedure
EnableDebugger

I get really good performance out of that! but being in an assembly mood this week i thought i'd try my luck with making an asm version, which was fun as im enjoying learning

Code: Select all

CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
  Macro rax : eax : EndMacro   ;thanks again wilbert for these helpers!
  Macro rbx : ebx : EndMacro   
  Macro rcx : ecx : EndMacro   
CompilerEndIf
 
DisableDebugger           ;Win+Linux+Mac, 32+64, Unicode+Ascii
CompilerIf #PB_Compiler_Unicode
  Procedure StripDualSpacesAsm(*pstr)
    EnableASM
    mov rax, *pstr
    push rbx
    mov rbx, rax
    
    !nextbyte:
    mov dx, [rbx]
    
    ! cmp dx, 0       ;Null?
    ! je  endproc
    ! cmp dx, 32      ;Space?
    ! jne normalchar  ;Other
    
    !spacechar:
    cmp rcx, 0
    ! jne dualspace
    !firstspace:
    mov rcx, 1
    mov [rax], dx
    add rax, 2
    add rbx, 2
    ! jmp nextbyte
    !dualspace:
    add rbx, 2
    ! jmp nextbyte
    
    !normalchar:
    XOr rcx, rcx
    mov [rax], dx
    add rax, 2
    add rbx, 2
    ! jmp nextbyte
    
    !endproc:
    mov [rax], word 0
    pop rbx
    DisableASM
  EndProcedure
CompilerElse
  Procedure StripDualSpacesAsm(*pstr)
    EnableASM
    mov rax, *pstr
    push rbx
    mov rbx, rax
    
    !nextbyte:
    mov dl, [rbx]
    
    ! cmp dl, 0       ;Null?
    ! je  endproc
    ! cmp dl, 32      ;Space?
    ! jne normalchar  ;Other
    
    !spacechar:
    cmp rcx, 0
    ! jne dualspace
    !firstspace:
    mov rcx, 1
    mov [rax], dl
    inc rax
    inc rbx
    ! jmp nextbyte
    !dualspace:
    inc rbx
    ! jmp nextbyte
    
    !normalchar:
    XOr rcx, rcx
    mov [rax], dl
    inc rax
    inc rbx
    ! jmp nextbyte
    
    !endproc:
    mov [rax], byte 0
    pop rbx
    DisableASM
  EndProcedure
CompilerEndIf
EnableDebugger

Timing tests, including ones posted later in this thread ...
My short string is "one two three four five six seven eight nine end" (53% space chars), which is 84 bytes.
My long string is 2000 copies of that (for a total string len of 168kb).
Then there are the Unicode versions also!
I try 5 million calls to the short buffer, and 10 thousand calls to the long one.

Code: Select all

TimePB=Native PB, FindString+ReplaceString loop
TimeK1=Keya's PB, BytePtr-based
TimeK2=Keya's asm, BytePtr-based w/ 8bit ops
TimeW1=wilbert's asm, BytePtr-based w/ 32bit ops
TimeR1=Rashad's PB, StringField-based
TimeR2=Rashad's PB, Peek-based
TimeI1=IdeasVacuum's PB, StringField-based

OS=Linux-64  Char=Ascii  String len=84, trying 5000000 calls...
TimeR1=38568
TimeR2=33397
TimeI1=20884
TimePB=6655
TimeK1=1145
TimeK2=643
TimeW1=422

OS=Linux-64  Char=Unicode  String len=84, trying 5000000 calls...
TimeR1=99061
TimeR2=50534
TimeI1=22502
TimePB=8557
TimeK1=1259
TimeK2=791
TimeW1=582

OS=Linux-64  Char=Ascii  String len=168000, trying 10000 calls...
TimeR1=184175000
TimeR2=53705000
TimeI1=51403000
TimePB=21622
TimeK1=3954
TimeK2=2138
TimeW1=1235

OS=Linux-64  Char=Unicode  String len=168000, trying 10000 calls...
TimeR1=531260000
TimeR2=175150000
TimeI1=60638000
TimePB=24686
TimeK1=4657
TimeK2=2709
TimeW1=1841

---

OS=Linux-32  Char=Ascii  String len=84, trying 5000000 calls...
TimeR2=39688
TimeR1=35749
TimeI1=26846
TimePB=9655
TimeK1=1121
TimeK2=564
TimeW1=402

OS=Linux-32  Char=Unicode  String len=84, trying 5000000 calls...
TimeR1=99186
TimeR2=62115
TimeI1=26096
TimePB=9200
TimeK1=1342
TimeK2=728
TimeW1=651

OS=Linux-32  Char=Ascii  String len=168000, trying 10000 calls...
TimeR1=148315000
TimeI1=65492000
TimeR2=58475000
TimePB=22914
TimeK1=3881
TimeK2=1725
TimeW1=1144

OS=Linux-32  Char=Unicode  String len=168000, trying 10000 calls...
TimeR1=511220000
TimeR2=175540000
TimeI1=57704000
TimePB=25697
TimeK1=4630
TimeK2=2207
TimeW1=1883

---

OS=OSX-64  Char=Ascii  String len=84, trying 5000000 calls...
TimeR2=60728
TimeR1=47592
TimeI1=35529
TimePB=8584
TimeK1=1459
TimeK2=833
TimeW1=749

OS=OSX-64  Char=Unicode  String len=84, trying 5000000 calls...
TimeR1=129911
TimeR2=96344
TimeI1=42651
TimePB=11463
TimeK1=2040
TimeK2=1503
TimeW1=1359

OS=OSX-64  Char=Ascii  String len=168000, trying 10000 calls...
TimeR1=185485000
TimeR2=151470000
TimeI1=70608000
TimePB=23684
TimeK1=5089
TimeK2=2802
TimeW1=2286

OS=OSX-64  Char=Unicode  String len=168000, trying 10000 calls...
TimeR1=582020000
TimeR2=353820000
TimeI1=80147000
TimePB=32381
TimeK1=6991
TimeK2=4804
TimeW1=4315

---

OS=Win-32  Char=Ascii  String len=84, trying 5000000 calls...
TimeR2=67536
TimeR1=59299
TimeI1=30923
TimePB=22804
TimeK1=1552
TimeK2=1024
TimeW1=765

OS=Win-32  Char=Unicode  String len=84, trying 5000000 calls...
TimeR1=117095
TimeR2=93698
TimeI1=32484
TimePB=11562
TimeK1=2054
TimeK2=1555
TimeW1=1457

OS=Win-32  Char=Ascii  String len=168000, trying 10000 calls...
TimeR1=264375000
TimeR2=231745000
TimeI1=58647000
TimePB=84465   ;anomaly
TimeK1=5261
TimeK2=3610
TimeW1=2508

OS=Win-32  Char=Unicode  String len=168000, trying 10000 calls...
TimeR1=570505000
TimeR2=375740000
TimeI1=75652000
TimePB=34182
TimeK1=7585
TimeK2=5629
TimeW1=4787

---

OS=Win-64  Char=Ascii  String len=84, trying 5000000 calls...
TimeR2=71279
TimeR1=62363
TimeI1=34368
TimePB=9304
TimeK1=1475
TimeK2=991
TimeW1=699

OS=Win-64  Char=Unicode  String len=84, trying 5000000 calls...
TimeR1=136522
TimeR2=96323
TimeI1=38987
TimePB=11055
TimeK1=1927
TimeK2=1628
TimeW1=1382

OS=Win-64  Char=Ascii  String len=168000, trying 10000 calls...
TimeR1=278125000
TimeR2=225950000
TimeI1=77789000
TimePB=25608
TimeK1=5100
TimeK2=3363
TimeW1=2333

OS=Win-64  Char=Unicode  String len=168000, trying 10000 calls...
TimeR1=626865000
TimeR2=345905000
TimeI1=87042000
TimePB=28811
TimeK1=6845
TimeK2=5005
TimeW1=4062

[wilbert]

Here's my attempt

Code: Select all

CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
  Macro rcx : ecx : EndMacro   
  Macro rdx : edx : EndMacro   
CompilerEndIf

Procedure StripDualSpacesAsm(*pstr)
  EnableASM
  mov rcx, *pstr
  mov rdx, rcx
  !sds_l0:
  CompilerIf #PB_Compiler_Unicode
    movzx eax, word [rcx]
    add rcx, 2
    !sds_l1:
    mov [rdx], ax
    add rdx, 2
  CompilerElse
    movzx eax, byte [rcx]
    add rcx, 1
    !sds_l1:
    mov [rdx], al
    add rdx, 1
  CompilerEndIf
  !test eax, -33
  !jnz sds_l0
  !cmp eax, 0
  !jz sds_l3
  !sds_l2:
  CompilerIf #PB_Compiler_Unicode
    movzx eax, word [rcx]
    add rcx, 2
  CompilerElse
    movzx eax, byte [rcx]
    add rcx, 1
  CompilerEndIf
  !cmp eax, 32
  !je sds_l2
  !jmp sds_l1
  !sds_l3:
  DisableASM
EndProcedure

[RASHAD]

Code: Select all

  For k = 1 To StringByteLength("  Hello   I am   a   splitted string  ")
    Text$ =  StringField("  Hello   I am   a   splitted string  ",k," ")
    If Text$ <> ""
       Text2$ = Text2$ + Text$ +" "
    EndIf       
  Next
  Debug RTrim(Text2$)

[Little John]

(and for speed reasons this modifies the string you give it - it doesn't return a separate string):

Code: Select all

[...]
  *pbyteA\c = 0
[...]

Is it actually safe to truncate a string like that, or will it confuse PB's string management?

[Keya]

Is it actually safe to truncate a string like that, or will it confuse PB's string management?

John i think PB uses a Knuth boundary tags technique ♥ or similar for every memory allocation, which im not touching, so i thought it should be safe to truncate the string inside (and re-grow up to original size but never more), as PB will still know via its tags exactly how much memory is being used. Thats my theory anyway! lol. Perhaps there's a simple allocating & freeing test to prove its ok

wilbert, nice!! I havent used movzx before, so i will make that my Instruction Of The Week... next week heehee your code looks nice and elegant, cant wait to time it

Rashad, great example! I'll do some timing tests for both soon

{update} John here's, well, one test anyway lol:

Code: Select all

;1. Full string
Test.s = "0123456789"
Follow.s = "x" ;to ensure the next adjacent segment is also allocated
Debug ("Str=" + Test + " @ 0x" + Hex(@Test))

;2. Truncate to "01234" by manual nullchar insertion
*bptr.Ascii = @Test + 5
*bptr\a = 0
Debug ("Str=" + Test + " @ 0x" + Hex(@Test))

;3. Increase string length using native PB code
Test.s = "ABCDEFGH"
Debug ("Str=" + Test + " @ 0x" + Hex(@Test))

;4. Increase string length to greater than original size
Test.s = "ABCDEFGHIJKLMNOP"
Debug ("Str=" + Test + " @ 0x" + Hex(@Test))

1. create a string of 10 chars
2. manually truncate the string by inserting a nullchar
3. use normal PB string command to overwrite the string with a new string longer than truncated, but shorter than or equal to original
The address has remained the same throughout, proving(?) PB knew it was able to increase the size of my null-truncated string back to its original size (otherwise it wouldve reallocated). It couldve only been the tags at work there, not the nullchar.
4. Now use the PB string command to overwrite the string, but with a string longer than the original
Now the address has changed due to reallocation

i could be wrong but it seems the boundary tags are doing their job there, allowing for a "floating" null-terminator because the boundary tags arent affected/dont care about it - they dont seem to care its a null-terminated string, its just binary data to them. Just my theory though lol

Tags on either side of each allocation. I havent had a look at exactly what they are but some are either size or ptr tags, and it looks like six of the 01 bytes = In Use tag (one on either side of each segment), you can see the switch back to 0 after FreeMemory marks them free if not coalesced with an adjacent segment:

Code: Select all

Str1.s = "1111"
Str2.s = "2222"
Str3.s = "3333"
ShowMemoryViewer(@Str1-8,128)
;00391EA0  03 00 03 00 7A 01 0F 00 31 31 31 31 00 01 39 00  ....z...1111..9.
;00391EB0  00 00 00 00 00 00 00 00 03 00 03 00 79 01 0F 00  ............y...
;00391EC0  32 32 32 32 00 01 39 00 00 00 00 00 00 00 00 00  2222..9.........
;00391ED0  03 00 03 00 74 01 0F 00 33 33 33 33 00 01 39 00  ....t...3333..9.
;00391EE0  00 00 00 00 00 00 00 00 23 02 03 00 00 10 00 00  ........#.......

i find it a bit clearer to see when you FreeMemory a segment inside two AllocateMemory'd segments ... this follows ShowMemoryViewer( *mem1 - 8 ):

Code: Select all

*mem1 = AllocateMemory(4):  PokeL(*mem1,$A1A1A1A1)
003B1E88  02 00 01 03 7D 01 0C 00 A1 A1 A1 A1 78 01 3B 00  ....}...¡¡¡¡x.;.
003B1E98  2D 02 02 00 00 10 00 00 78 01 3B 00 78 01 3B 00  -.......x.;.x.;.
003B1EA8  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
003B1EB8  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

*mem2 = AllocateMemory(4):  PokeL(*mem2,$A2A2A2A2)
003B1E88  02 00 01 03 C7 01 0C 00 A1 A1 A1 A1 78 01 3B 00  ....Ç...¡¡¡¡x.;.
003B1E98  02 00 02 00 C5 01 0C 00 A2 A2 A2 A2 78 01 3B 00  ....Å...¢¢¢¢x.;.
003B1EA8  2B 02 02 00 00 10 00 00 78 01 3B 00 78 01 3B 00  +.......x.;.x.;.
003B1EB8  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

*mem3 = AllocateMemory(4):  PokeL(*mem3,$A3A3A3A3)
003B1E88  02 00 01 03 B9 01 0C 00 A1 A1 A1 A1 78 01 3B 00  ....¹...¡¡¡¡x.;.
003B1E98  02 00 02 00 BB 01 0C 00 A2 A2 A2 A2 78 01 3B 00  ....»...¢¢¢¢x.;.
003B1EA8  02 00 02 00 BD 01 0C 00 A3 A3 A3 A3 78 01 3B 00  ....½...££££x.;.
003B1EB8  29 02 02 00 00 10 00 00 78 01 3B 00 78 01 3B 00  ).......x.;.x.;.

FreeMemory(*mem2)   
003B1E88  02 00 01 03 DF 01 0C 00 A1 A1 A1 A1 78 01 3B 00  ....ß...¡¡¡¡x.;.
003B1E98  02 00 02 00 DD 00 0C 00 88 01 3B 00 88 01 3B 00  ....Ý...?.;.?.;.
003B1EA8  02 00 02 00 DB 01 0C 00 A3 A3 A3 A3 78 01 3B 00  ....Û...££££x.;.
003B1EB8  29 02 02 00 00 10 00 00 78 01 3B 00 78 01 3B 00  ).......x.;.x.;.

FreeMemory(*mem1)    ;should coalesce with *mem2 ?
003B1E88  04 00 01 03 4C 00 0C 00 98 01 3B 00 98 01 3B 00  ....L...?.;.?.;.
003B1E98  02 00 02 00 4E 00 0C 00 88 01 3B 00 88 01 3B 00  ....N...?.;.?.;.
003B1EA8  02 00 04 00 48 01 0C 00 A3 A3 A3 A3 78 01 3B 00  ....H...££££x.;.
003B1EB8  29 02 02 00 00 10 00 00 78 01 3B 00 78 01 3B 00  ).......x.;.x.;.

[IdeasVacuum]

For general purpose use I think Rashad's solution wins out. It is simple, easy to understand and cross platform.

[Keya]

For general purpose use I think Rashad's solution wins out. It is simple, easy to understand and cross platform.

Every solution above is fully cross-platform, and they're all just as easy to call ... DoConvert(@Str) or Str = DoConvert(Str) ...? but yes at least Rashad's has the advantage of being able to remember it unfortunately it seems to have the slowest performance, im time testing now - it seems StringField() doesn't perform well on long strings

[wilbert]

it seems StringField() doesn't perform well on long strings

Yes, you are right. It's very inefficient. The same goes for building strings by continuously adding substrings.

If it's about simplicity, for me your initial idea of using ReplaceString until there's nothing more to replace is the most logical approach.
It could be simplified a bit to

Code: Select all

Procedure.s StripDualSpaces_ReplaceString(sStr.s)
  While FindString(sStr, "  ") : sStr.s = ReplaceString(sStr, "  ", " ") : Wend 
  ProcedureReturn sStr
EndProcedure

If it's about speed, asm

[Keya]

it seems StringField() doesn't perform well on long strings

Yes, you are right. It's very inefficient. The same goes for building strings by continuously adding substrings.

Exponentially worse too the longer the string ...

Code: Select all

Time=149    Len=8400   x1 data, 5.63 bytes/ms
Time=5874   Len=16800  x2 data, 2.86 bytes/ms
Time=13170  Len=25200  x3 data, 1.91 bytes/ms
Time=23209  Len=33600  x4 data, 1.44 bytes/ms
Time=36290  Len=42000  x5 data, 1.15 bytes/ms <- only 1150 bytes per second and the string is only 42kb :(

It's comparatively slow-but-bearable on the short (84-byte) string, though ive only tested on Win32 so far:

Code: Select all

OS=Win-32  Char=Unicode  String len=84, trying 5000000 calls...
TimeR=117095	0.0234190002ms/call

OS=Win-32  Char=Ascii  String len=84, trying 5000000 calls...
TimeR=59299	0.0118597997ms/call

But on the 168,000-byte string being processed 10,000 times, it's currently been running for 60 minutes so far with no end in sight! all the other solutions had finished that in ~30 seconds. So i've now terminated it and changed its loop from 10,000 to 2, multiplying the result by 5000 for the approximated result, lol... it's just that slow! Looks can be deceiving, IdeasVacuum
I should have updated time tests including yours wilberts in the next quarter of an hour or so

[RASHAD]

No StringField()
If it is inefficient you have to report Fred
Still simple and crossplatform

Code: Select all

  text$ = Trim("  Hello        I     am   a   splitted string    Hello      I   am   a   splitted string    Hello      I   am   a   splitted string  ")
  For k = 0 To StringByteLength(text$)
     text2$ = text2$ + PeekS(@text$+k,1,#PB_UTF8)   
     If PeekS(@text$+k,1,#PB_UTF8) = " "
        text2$ = RTrim(text2$) + " "       
     EndIf     
  Next
  
  Debug text2$

Edit : Modified for ascii & Unicode

[wilbert]

No StringField()
If it is inefficient you have to report Fred
Still simple and crossplatform

Sorry, but did you even take the time to test it ?
It's not unicode compatible and still very inefficient.

[RASHAD]

Hi Wilbert
You misunderstood me
I have a lot of trouble with StringField() and StringByteLength() and maybe more specially with memory types
But what can I do
Usually I have my own way around
I belief MS Windows has it is own bugs and so PureBasic but I do not stop there

[Keya]

Ive updated the timings in the first post. Rashad thankyou for your contributions, and I was able to make a unicode-compatible version of your second algorithm by making the For loop Step 2. perhaps not fully unicode compatible, but ascii range with unicode compile at least - enough for timing anyway!
Your algorithms are elegant but really falls down on long strings because of so many concatenation and reallocations

wilbert congratulations, your algorithm sweeps the board on every platform! impressive i look forward to learning about movzx next week heehee

[wilbert]

@Rashad,
Sorry, I shouldn't have concluded things so fast.
As for your code, some times it helps to know a few basic things. For example when you use a for loop, the expression for the 'to' part is evaluated each time so if it doesn't change it's better to use a variable for it.
Your initial code with the StringField in it, could already made faster quite a bit by changing it to this

Code: Select all

fieldCount = CountString("  Hello   I am   a   splitted string  ", " ") + 1
For k = 1 To fieldCount
  Text$ =  StringField("  Hello   I am   a   splitted string  ",k," ")
  If Text$ <> ""
    Text2$ = Text2$ + Text$ +" "
  EndIf       
Next
Debug RTrim(Text2$)

although it's still not fast.

@Keya,
Thanks for the updated timings
The movzx combined with using the full 32 bit eax register for comparison instead of only the 8 or 16 least significant bits really makes a speed difference.

[Gadget]

Hi,

Not ASM and uses PureBasic strings. So, not fast but what I normally use is:

Code: Select all

Procedure.s ReplaceMultipleSpaces(OldText.s)
  ; Returns the string passed to this function but with all multiple spaces reduced to a single space
  
  Protected NewText.s = OldText
  
  If NewText <> ""
    ; Keep looking for double spaces and replace them until none are left
    While CountString(NewText,"  ") > 0
      NewText = ReplaceString(NewText,"  "," ")
    Wend 
  EndIf
  
  ProcedureReturn NewText
EndProcedure

Hope this is of help to someone,

Gadget