Hi,
For wisp I created an efficient implementation of substring replacement and
thought it might be useful for guile in general.
I optimized it a bit to get rid of (likely) quadratic behaviour:
; ,time (string-replace-substring (xsubstring "abcdefghijkl" 0 99999) "def"
"abc")
; 1.140127s real time, 1.139714s run time. 0.958733s spent in GC.
; 0.885618s real time, 0.885350s run time. 0.742805s spent in GC.
; second number after multiple runs
(define (string-replace-substring s substring replacement)
"Replace every instance of substring in s by replacement."
(let ((sublen (string-length substring)))
(let replacer
((newstring s)
(index (string-contains s substring)))
(if (not (equal? index #f))
(let ((replaced (string-replace newstring replacement index
(+ index sublen))))
(replacer replaced (string-contains replaced substring
index)))
newstring))))
This fast and elegant approach is thanks to ijp.
I tested a two alternative approaches. The following uses explicit readonly
substrings and is fast, the one afterwards always searches from the beginning
and shows drastic slowdown on long strings.
; efficient version from rev 12266d455bb0 of the wisp hg repo
; ,time (string-replace-substring-fast-but-long (xsubstring "abcdefghijkl" 0
99999) "def" "abc")
; 1.316090s real time, 1.315626s run time. 1.129857s spent in GC.
; 0.668212s real time, 0.667948s run time. 0.482193s spent in GC.
; 0.868419s real time, 0.868131s run time. 0.685472s spent in GC
; Second and third are after multiple runs
(define (string-replace-substring-fast-but-long s substring replacement)
"Replace every instance of substring in s by replacement."
(let ((sublen (string-length substring)))
(let replacer
((newstring s)
(startindex 0)
(addindex (string-contains s substring)))
(if (not (equal? addindex #f))
(let*
((index (+ startindex addindex))
(replaced (string-replace newstring replacement index
(+ index sublen)))
(newaddindex (string-contains (substring/read-only
replaced index) substring)))
(replacer replaced index newaddindex))
newstring))))
; less efficient version from rev a887aeb0dfe2
; ,time (string-replace-substring-slow (xsubstring "abcdefghijkl" 0 99999)
"def" "abc")
; 5.242456s real time, 5.240834s run time. 0.358750s spent in GC.
; 5.727069s real time, 5.724973s run time. 0.835445s spent in GC.
; switches between fast and slow version
(define (string-replace-substring-slow s substring replacement)
"Replace every instance of substring in s by replacement."
(let ((sublen (string-length substring)))
(let replacer
((newstring s)
(index (string-contains s substring)))
(if (not (equal? index #f))
(let ((replaced (string-replace newstring replacement index
(+ index sublen))))
(replacer replaced (string-contains replaced substring)))
newstring))))
ijp suggested renaming to (string-replace-all, but I do not know enough about
conventions in guile to judge that).
Best wishes,
Arne
