Subject: [clisp-list] Re: Lisp question

From: Sam Steingold <[email-masked]>
Date: Fri Oct 3 08:21:05 2003

> * Dan Stanger <[email-masked]> [2003-10-03 10:42:17 -0400]:
>
> What is the best way to convert a list of strings to a single string?
> For example ("abc" "def" "ghi") should convert to "abcdefghi"

1. if your list is not too large (< CALL-ARGUMENTS-LIMIT) then
        (apply #'concatenate 'string list-of-strings)
   if, moreover, CLISP-only, the faster way is
        (apply #'ext:string-concat list-of-strings)

2. in general, the standard way is the same as adding lists of numbers &c:
        (reduce (lambda (s1 s2) (concatenate 'string s1 s2))
                list-of-strings :initial-value "")
   (CLISP-specific ext:string-concat is again faster:
        (reduce #'ext:string-concat list-of-strings)
   moreover, it does not cons up a lambda).

-- 
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/>
<http://www.mideasttruth.com/> <http://www.honestreporting.com>
All extremists should be taken out and shot.

---

From: Pascal J.Bourguignon <[email-masked]>
Date: Fri Oct 3 12:43:12 2003

>    moreover, it does not cons up a lambda).

For some definition of best, it is:

    (defun join (list-of-strings)
      (do ((result  (make-string (reduce (function +) list-of-strings)))
           (los list-of-strings (cdr los))
           (pos 0))
          ((null los) result)
       (replace result (car los) :start1 pos)
       (incf pos (length (car los)))))

Note that (length a-string) is O(1) in Lisp, so the complexity of this
function is  O(n) with n  = (length result) [assuming  that n>>(length
list-of-strings)].

-- 
__Pascal_Bourguignon__
http://www.informatimago.com/
Do not adjust your mind, there is a fault in reality.

---

From: "John K. Hinsdale" <[email-masked]>
Date: Sun Dec 21 11:26:04 2003

>         (reduce #'ext:string-concat list-of-strings)

I do a lot of string concatenation, generating a large string of HTML
page, built from lots of small strings retrieved from a database, so I
wrote a replacement for EXT:STRING-CONCAT that speeds things up a lot
for my appl.  It works by working with a growable string array and
pre-allocating space as it gets bigger.

It seems to speed things about at least twice as much for me.  Your
mileage may vary of course.  Code is below.  It should work as a
drop-in replacement for STRING-CONCAT.

---
John Hinsdale, Alma Mater Software, Inc., Tarrytown, NY 10591-3710 USA
[email-masked] | http://www.alma.com/staff/hin | +1 914 631 4690

; -------  Cut here -------
; MY-STRING-CONCAT -- Concatenate together string arguments into a
; single string

(defun my-string-concat (&rest args)
  (labels
   ((append-adjustable (astr s)
       (let ((alen (length astr))
             (slen (length s)))
         (if (= 0 slen)
             astr
           (let ((newlen (+ alen slen)))
             (when (<= (array-dimension astr 0) newlen)
                   ; Reduce growth factor if tight on space
                   (adjust-array astr (* 2 newlen)))
             ; Append chars onto result
             (setf (fill-pointer astr) newlen)
             (replace astr s :start1 alen :end1 newlen)))))
    (aconcat (astr args)
      (cond ((atom args) (append-adjustable astr args))
            (t (dolist (s args)
                       (aconcat astr s))
               astr))))
   (aconcat (make-array
             ; Minimum string size to allocate for result
             100
             :element-type 'character
             :fill-pointer 0 :adjustable t)
            args)))

; -------  Cut here -------

; Test case
(setf l nil)
(dotimes (i 2000)
   (push "xxxxxxxxxx" l))
(print "Starting concat using EXT:STRING-CONCAT")
(reduce #'ext:string-concat l)
(print "Done")
(print "Starting concat using MY-STRING-CONCAT")
(reduce #'my-string-concat l)
(print "Done")

; -------  Cut here -------

---

From: Sam Steingold <[email-masked]>
Date: Sun Dec 21 11:56:02 2003

> * John K. Hinsdale <[email-masked]> [2003-12-21 14:25:32 -0500]:
>

the return value is not a simple string.
if you are doing (reduce foo), why not get rid of reduce?

(defun concat-strings (strings)
  (let ((ret (make-array (reduce #'+ strings :key #'length)
                         :element-type 'character))
        (start 0))
    (dolist (string strings ret)
      (replace ret string :start1 start)
      (incf start (length string)))))

this is pretty much the same as (apply #'string-concat strings).

-- 
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/>
<http://www.mideasttruth.com/> <http://www.honestreporting.com>
Diplomacy is the art of saying "nice doggy" until you can find a rock.

---

From: "John K. Hinsdale" <[email-masked]>
Date: Sun Dec 21 16:24:01 2003

>> I wrote a replacement for EXT:STRING-CONCAT that speeds things up a
  >> lot for my appl.  It works by working with a growable string array
  >> and pre-allocating space as it gets bigger.

 > the return value is not a simple string.

not sure why this matters to me?  My application works the same either way...

 > ...

This is at least 100 times faster than my function (!) Can you give me a
hint as to why?  And thanks!

---

---

From: Sam Steingold <[email-masked]>
Date: Sun Dec 21 17:14:26 2003

> * John K. Hinsdale <[email-masked]> [2003-12-21 19:23:11 -0500]:
>

you can check and see that (apply #'string-concat strings) is even
better because it's in C, not bytecode.

> This is at least 100 times faster than my function (!) Can you give me
> a hint as to why?  And thanks!

1. never allocates any garbage - moreover, allocates exactly the amount
   of memory needed.

2. avoids funcall overhead: one function call instead of (length
   arglist) funcalls inside reduce

-- 
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/>
<http://www.mideasttruth.com/> <http://www.honestreporting.com>
C combines the power of assembler with the portability of assembler.

---

From: Pascal J.Bourguignon <[email-masked]>
Date: Sun Dec 21 17:38:01 2003

> hint as to why?  And thanks!

For: (dotimes (i 2000) (push "xxxxxxxxxx" l))
you'll end up with a string of 20000 characters.

Your function  will have  to allocate (ceiling  (/ (log  (/ total-size
100)) (log 2))) [= 8 for 20000 characters] strings of increasing sizes
[O(log(n)], with copying the intermediary concatenations [O(n*log(n))]
while the other function will  allocate one string [O(1)] and copy the
bytes once [O(n)].  [Note that for strings, (length s) is O(1)].

-- 
__Pascal_Bourguignon__                              .  *   * . * .* .
http://www.informatimago.com/                        .   *   .   .*
There is no worse tyranny than to force             * .  . /\  (   . *
a man to pay for what he does not                    . .  / .\   . * .
want merely because you think it                    .*.  / *  \  . .
would be good for him. -- Robert Heinlein             . /*   o \     .
http://www.theadvocates.org/                        *   '''||'''   .
SCO Spam-magnet: [email-masked]                 ******************

---

From: "John K. Hinsdale" <[email-masked]>
Date: Sun Dec 21 18:09:01 2003

> better because it's in C, not bytecode.

Yes, but I think you said a while back that using APPLY will construct
an actual function call w/ list of arguments as determined by STRINGS
arg ... which in my situations will blow out CALL-ARGUMENTS-LIMIT (my
lists get quite huge).

Thanks for all the explantations; my code will benefit.

---

---

From: Sam Steingold <[email-masked]>
Date: Sun Dec 21 18:30:03 2003

> * John K. Hinsdale <[email-masked]> [2003-12-21 21:08:29 -0500]:
>

yes, and this is why you are doomed to using either REDUCE or my function.

-- 
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/>
<http://www.mideasttruth.com/> <http://www.honestreporting.com>
Don't use force -- get a bigger hammer.