[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
efficient implementation of string-replace-substring / string-replace-al
From: |
Arne Babenhauserheide |
Subject: |
efficient implementation of string-replace-substring / string-replace-all |
Date: |
Fri, 13 Sep 2013 16:32:13 +0200 |
User-agent: |
Wanderlust/2.15.9 (Almost Unreal) SEMI/1.14.6 (Maruoka) FLIM/1.14.9 (Gojō) APEL/10.8 Emacs/24.3 (x86_64-pc-linux-gnu) MULE/6.0 (HANACHIRUSATO) |
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
- efficient implementation of string-replace-substring / string-replace-all,
Arne Babenhauserheide <=