Re: efficient implementation of string-replace-substring / string-replace-all

[Andy Wingo]

On Fri 13 Sep 2013 21:41, Mark H Weaver <address@hidden> writes:

> Here's an implementation that does this benchmark about 80 times faster
> on my machine: (20 milliseconds vs 1.69 seconds)
>
> (define* (string-replace-substring s substr replacement
>                                    #:optional
>                                    (start 0)
>                                    (end (string-length s)))
>   (let ((substr-length (string-length substr)))
>     (if (zero? substr-length)
>         (error "string-replace-substring: empty substr")
>         (let loop ((start start)
>                    (pieces (list (substring s 0 start))))
>           (let ((idx (string-contains s substr start end)))
>             (if idx
>                 (loop (+ idx substr-length)
>                       (cons* replacement
>                              (substring s start idx)
>                              pieces))
>                 (string-concatenate-reverse (cons (substring s start)
>                                                   pieces))))))))

Inspired to code-golf a bit, here's one that's even faster :)

(define (string-replace-substring s substring replacement)
  "Replace every instance of substring in s by replacement."
  (let ((sublen (string-length substring)))
    (with-output-to-string
      (lambda ()
        (let lp ((start 0))
          (cond
           ((string-contains s substring start)
            => (lambda (end)
                 (display (substring/shared s start end))
                 (display replacement)
                 (lp (+ end sublen))))
           (else
            (display (substring/shared s start)))))))))

Just marginally so, though.

Andy
-- 
http://wingolog.org/