Optimized string-replace function

Hello,

I am using a home-made string-replace function over large strings.

This is not efficient and my program runs "forever".

Where can I find an efficient one for Lispworks?

Does Lispworks includes one of it own?

This is the function I use:

;This function was taken from

;http://www.tek-tips.com/viewthread.cfm?qid=1184743&page=1

(defun string-replace (str1 sub1 sub2)

(let ((str1 (string str1))

(str2 "")

(sub1 (string sub1))

(sub2 (string sub2))

(index1 0))

(loop

(if (string-equal str1 sub1

:start1 index1

:end1 (min (length str1)

(+ index1 (length sub1))))

(progn

(setq str2 (concatenate 'string str2 sub2))

(incf index1 (length sub1)))

(progn

(setq str2 (concatenate 'string

str2

(subseq str1 index1 (1+ index1))))

(incf index1)))

(unless (< index1 (length str1))

(return str2)))))

Thank you,

Mauricio

--
Mauricio TORO BERMUDEZ

Research Postgraduate Student (Ph.D)
Computer Science Research Laboratory of Bordeaux (LABRI)
University of Bordeaux 1: Science and Technology

http://www.labri.fr/perso/mtoro/

351, cours de la Libération
F-33405 Talence Cedex. France.
Phone: (+33) 5 4000 24 85
Fax: (+33) 5 4000 66 69

Please don't print this e-mail unless you really need to.

Re: Optimized string-replace function

Hi,

This looks like a rather naive algorithm. Check out something like this: http://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

Pascal

On 20 Apr 2010, at 18:32, Mauricio Toro wrote:

Hello,

I am using a home-made string-replace function over large strings.
This is not efficient and my program runs "forever".
Where can I find an efficient one for Lispworks?

Does Lispworks includes one of it own?

This is the function I use:
;This function was taken from
;http://www.tek-tips.com/viewthread.cfm?qid=1184743&page=1

(defun string-replace (str1 sub1 sub2)
  (let ((str1 (string str1))
   (str2 "")
   (sub1 (string sub1))
   (sub2 (string sub2))
   (index1 0))

   (loop
   (if (string-equal str1 sub1
   :start1 index1
   :end1 (min (length str1)
   (+ index1 (length sub1))))

   (progn
   (setq str2 (concatenate 'string str2 sub2))
   (incf index1 (length sub1)))
   (progn
   (setq str2 (concatenate 'string

   str2
   (subseq str1 index1 (1+ index1))))
   (incf index1)))
   (unless (< index1 (length str1))

   (return str2)))))

Thank you,

Mauricio

--
Mauricio TORO BERMUDEZ

Research Postgraduate Student (Ph.D)
Computer Science Research Laboratory of Bordeaux (LABRI)
University of Bordeaux 1: Science and Technology

http://www.labri.fr/perso/mtoro/

351, cours de la Libération
F-33405 Talence Cedex. France.
Phone: (+33) 5 4000 24 85
Fax: (+33) 5 4000 66 69

Please don't print this e-mail unless you really need to.

Pascal Costanza, mailto:pc@p-cos.net, http://p-cos.net

Vrije Universiteit Brussel

Software Languages Lab

Pleinlaan 2, B-1050 Brussel, Belgium

Re: Optimized string-replace function

Mauricio Toro wrote:
> Hello,
>
> I am using a home-made string-replace function over large strings.
> This is not efficient and my program runs "forever".
> Where can I find an efficient one for Lispworks?
>   
Is this any better?

(unpolished, and only lightly tested)

(defun string-replace2 (str1 sub1 sub2)
  (let ((str1 (string str1))
        (sub1 (string sub1))
        (sub2 (string sub2))
        pos
        len
        tail)
    (setq len (length sub1))
    (setq pos (search sub1 str1))
    (if (null pos)
        str1
        (with-output-to-string (s)
          (loop while pos
             do
               (format s (subseq str1 pos))
               (format s sub2)
               (setq tail (subseq str1 (+ pos len)))
               (setq pos  (search sub1 tail))
               (if pos
                   (setq str1 tail)
                   (format s tail)))))))

--