Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Joining strings

20 views
Skip to first unread message

WJ

unread,
Jul 23, 2016, 5:04:37 PM7/23/16
to
Why this is marked as abuse? It has been marked as abuse.
Report not abuse
Adam Warner wrote:

> Hi Lowell Kirsh,
>
> > I want to write a function to take a list of strings and a delimiter and
> > return a string with the strings put together with the delimiter as glue.
>
> > e.g. (join '("foo" "bar" "baz")) -> "foo:bar:baz"
>
> (defun join (list &optional (delimiter #\:))
> (let ((countdown (length list)))
> (with-output-to-string (stream)
> (dolist (item list)
> (write-string item stream)
> (decf countdown)
> (unless (zerop countdown)
> (write-char delimiter stream))))))

R:

paste(c("foo","bar","baz"), collapse=":")

"foo:bar:baz"

--
From the New York Times of October 11, 1991, ... we learn that ... researchers
at Boston University admitted that, "There is no question but that Dr. King
plagiarized in the dissertation." ... "Dr. Martin Luther King, Jr." [Michael
King] spent his last night on Earth having sexual intercourse with two women at
the motel and physically beating and abusing a third.
www.revilo-oliver.com/Kevin-Strom-personal/Beast_as_Saint.html

Thomas Mannay

unread,
Jul 24, 2016, 12:53:37 PM7/24/16
to
On Sat, 23 Jul 2016 21:04:34 -0000 (UTC)
"WJ" <w_a_...@yahoo.com> wrote:

> Adam Warner wrote:
>
> > Hi Lowell Kirsh,
> >
> > > I want to write a function to take a list of strings and a delimiter and
> > > return a string with the strings put together with the delimiter as glue.
> >
> > > e.g. (join '("foo" "bar" "baz")) -> "foo:bar:baz"
> >
> > (defun join (list &optional (delimiter #\:))
> > (let ((countdown (length list)))
> > (with-output-to-string (stream)
> > (dolist (item list)
> > (write-string item stream)
> > (decf countdown)
> > (unless (zerop countdown)
> > (write-char delimiter stream))))))
>
> R:
>
> paste(c("foo","bar","baz"), collapse=":")
>
> "foo:bar:baz"
>

CL (mildly more efficient than that above):

(defun join (delim &rest strings)
(labels ((helper (x list tmp)
(if (null (cdr list))
(concatenate 'string tmp (car list))
(helper x
(cdr list)
(concatenate 'string
tmp
(car list)
(string x))))))
(helper delim strings "")))

--
Thomas Mannay <audiob...@openmailbox.org>

Raymond Wiker

unread,
Jul 24, 2016, 1:37:36 PM7/24/16
to
(with-output-to-string (s)
(loop for (a . b) on strings by #'cdr
do (progn
(write-string a s)
(when b
(write-string delim s))))))

*Never* build a string by repeated concatenation.

Thomas Mannay

unread,
Jul 24, 2016, 4:15:37 PM7/24/16
to
On Sun, 24 Jul 2016 19:37:32 +0200
Raymond Wiker <rwi...@gmail.com> wrote:

>
> *Never* build a string by repeated concatenation.
>

I'm curious -- matter of style or efficiency? My lisp-foo isn't as strong as I
wish it could be.

--
Thomas Mannay <audiob...@openmailbox.org>

Paul Rubin

unread,
Jul 24, 2016, 4:29:42 PM7/24/16
to
Thomas Mannay <audiob...@openmailbox.org> writes:
>> *Never* build a string by repeated concatenation.
> I'm curious -- matter of style or efficiency?

If concatenation is implemented the obvious way, it can take quadratic
time in the number of strings.

Raymond Wiker

unread,
Jul 24, 2016, 4:33:44 PM7/24/16
to
Thomas Mannay <audiob...@openmailbox.org> writes:

> On Sun, 24 Jul 2016 19:37:32 +0200
> Raymond Wiker <rwi...@gmail.com> wrote:
>
>>
>> *Never* build a string by repeated concatenation.
>>
>
> I'm curious -- matter of style or efficiency? My lisp-foo isn't as strong as I
> wish it could be.

Efficiency. For a small number of strings, it may well be more efficient
to use repeated concatenation, but at some point you'll end up spending
a lot of time copying data (consider that, each time you concatenate two
strings, you (probably) have to allocate new memory to hold the
concatenation, then copy both the source strings).

Pascal J. Bourguignon

unread,
Jul 24, 2016, 8:52:59 PM7/24/16
to
And then *never* build it with with-output-to-string.

There's no reason to assume that it will be any more efficient than
repeated concatenation. It would just depend on the implementation.

If repeated concatenation is not acceptable, then don't depend on the
implementation, implement your concatenating function yourself!

For example:

com.informatimago.common-lisp.cesarum.string:concatenate-strings
or
com.informatimago.common-lisp.cesarum.sequence:concatenate-sequences


--
__Pascal Bourguignon__ http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Raymond Wiker

unread,
Jul 25, 2016, 3:37:28 AM7/25/16
to
Really?

#||
(ql:quickload "com.informatimago.common-lisp.cesarum")
||#

(declaim (optimize (speed 3) (safety 1)))

(defun concatenate-strings/mine (strings)
(with-output-to-string (s)
(loop for string in strings
do (write-string string s))))

(defun concatenate-strings/pjb (strings)
(com.informatimago.common-lisp.cesarum.string:concatenate-strings strings))

(defparameter *strings*
(make-list 100000 :initial-element "foo"))

#||
(time (progn
(concatenate-strings/mine *strings*)
(values)))

(time (progn
(concatenate-strings/pjb *strings*)
(values)))

||#

Evaluation took:
0.010 seconds of real time
0.009297 seconds of total run time (0.008350 user, 0.000947 system)
90.00% CPU
21,449,980 processor cycles
3,150,912 bytes consed

; No value

Evaluation took:
0.015 seconds of real time
0.014656 seconds of total run time (0.013433 user, 0.001223 system)
100.00% CPU
33,808,210 processor cycles
2,805,664 bytes consed

; No value

Looks like the string-stream version is 33% faster than yours :-)

This was using SBCL 1.3.2.114; using Clozure Common Lisp 1.12-dev-r16752
I get 0.015067s and 0.020489s, respectively.

If I increase the number of strings to 10M, concatenate-strings/mine is
more than twice as fast (0.799s versus 1.625s).

Note: after looking at your code, I actually expected it to be faster
than using with-output-to-string.

Pascal J. Bourguignon

unread,
Jul 25, 2016, 1:53:21 PM7/25/16
to
Raymond Wiker <rwi...@gmail.com> writes:
> Note: after looking at your code, I actually expected it to be faster
> than using with-output-to-string.

Yes, optimization in lisp is quite surprising and implementation
dependant :-)
0 new messages