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"
Any ideas?
Lowell
On Tue, Mar 16, 2004 at 06:53:11PM -0800, Lowell Kirsh wrote:
> 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"
>
> Any ideas?
(defun join (list)
(format nil "~{~A~^:~}" list))
or
(defun join (list &optional (delim ":"))
(with-output-to-string (stream)
(loop for cons on list do
(princ (car cons) stream)
(when (cdr cons) (princ delim stream)))))
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
Matthew Danish <·······@andrew.cmu.edu> writes:
> On Tue, Mar 16, 2004 at 06:53:11PM -0800, Lowell Kirsh wrote:
> > 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"
> >
> > Any ideas?
>
> (defun join (list)
> (format nil "~{~A~^:~}" list))
>
> or
>
> (defun join (list &optional (delim ":"))
> (with-output-to-string (stream)
> (loop for cons on list do
> (princ (car cons) stream)
> (when (cdr cons) (princ delim stream)))))
It's just a small difference but I like this idiom for LOOP:
(defun join (list &optional (delim ":"))
(with-output-to-string (stream)
(loop for (string . morep) on list do
(princ string stream)
(when morep (princ delim stream)))))
In general though I would use the FORMAT version.. I use the hell out
of FORMAT.
Hi Matthew Danish,
> On Tue, Mar 16, 2004 at 06:53:11PM -0800, Lowell Kirsh wrote:
>> 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"
>>
>> Any ideas?
>
> (defun join (list)
> (format nil "~{~A~^:~}" list))
The above is a good demo of FORMAT's compact language.
(time (dotimes (i 100000) (join '("foo" "bar" "baz")))) on one
particular system running CMUCL with default compilation settings:
2.51s
212,800,192 bytes consed
> (defun join (list &optional (delim ":"))
> (with-output-to-string (stream)
> (loop for cons on list do
> (princ (car cons) stream)
> (when (cdr cons) (princ delim stream)))))
2.28s
297,600,320 bytes consed
My version:
0.23s
13,600,000 bytes consed
For Lowell's benefit: Even though I traversed the list twice (once for
determining its length and once in the dolist) it allowed me to establish
a low consing, quicker test for whether the delimiter should be printed.
Given the overhead of setting up a string stream my version takes only
twice as long (0.46s) traversing three times the number of elements.
i.e. (time (dotimes (i 100000)
(join '("foo" "bar" "baz" "foo" "bar" "baz" "foo" "bar" "baz"))))
takes 0.46s with 16,000,000 bytes consed on one particular system running
CMUCL.
Regards,
Adam
On Wed, Mar 17, 2004 at 06:32:28PM +1300, Adam Warner wrote:
> For Lowell's benefit: Even though I traversed the list twice (once for
> determining its length and once in the dolist) it allowed me to establish
> a low consing, quicker test for whether the delimiter should be printed.
> Given the overhead of setting up a string stream my version takes only
> twice as long (0.46s) traversing three times the number of elements.
> i.e. (time (dotimes (i 100000)
> (join '("foo" "bar" "baz" "foo" "bar" "baz" "foo" "bar" "baz"))))
> takes 0.46s with 16,000,000 bytes consed on one particular system running
> CMUCL.
For Adam's benefit: Looping through the conses of a list, and testing
for NIL, does not cons. PRINC does. Try my version with WRITE-STRING
and WRITE-CHAR.
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
Hi Matthew Danish,
> For Adam's benefit: Looping through the conses of a list, and testing
> for NIL, does not cons. PRINC does. Try my version with WRITE-STRING
> and WRITE-CHAR.
Thanks Matthew. You'll see I figured this out and benchmarked new versions
of your code using WRITE-STRING and WRITE-CHAR and posted my update just
before your reply. Sorry for jumping to conclusions as to why your code
was so darn slow ;-)
Regards,
Adam
> For Lowell's benefit: Even though I traversed the list twice (once for
> determining its length and once in the dolist) it allowed me to establish
> a low consing, quicker test for whether the delimiter should be printed.
> Given the overhead of setting up a string stream my version takes only
> twice as long (0.46s) traversing three times the number of elements.
> i.e. (time (dotimes (i 100000)
> (join '("foo" "bar" "baz" "foo" "bar" "baz" "foo" "bar" "baz"))))
> takes 0.46s with 16,000,000 bytes consed on one particular system running
> CMUCL.
However the main reason my version was faster is that I used WRITE-STRING
instead of PRINC. Replace Matthew's PRINCs with WRITE-STRINGs and his
version is almost exactly the same speed with three elements (0.25s). With
three times the number of elements it takes 0.63s.
But if I also replace Matthew's use of a string for a delimiter with a
character then his version appears to be exactly the same speed as mine
(or perhaps a hundredth of a second or two faster)!
[I had hoped that my use of ZEROP would allow CMUCL to perform the
countdown comparison without having to load a register to compare
against. This may not be possible because CMUCL's fixnum representation
has tag bits and therefore 0 doesn't correspond to a machine value of 0]
Regards,
Adam
In article <······························@consulting.net.nz>,
Adam Warner <······@consulting.net.nz> wrote:
> However the main reason my version was faster is that I used WRITE-STRING
> instead of PRINC. Replace Matthew's PRINCs with WRITE-STRINGs and his
> version is almost exactly the same speed with three elements (0.25s). With
> three times the number of elements it takes 0.63s.
Binding *PRINT-PRETTY* to NIL has the same effect. It also makes the
FORMAT only solution run over twice as fast and cons 1/5 as much.
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
On 8686 day of my life Adam Warner wrote:
> [I had hoped that my use of ZEROP would allow CMUCL to perform the
> countdown comparison without having to load a register to compare
> against. This may not be possible because CMUCL's fixnum
> representation has tag bits and therefore 0 doesn't correspond to a
> machine value of 0]
It does. Adam, is it really you or some spoofer? :)
--
Ivan Boldyrev
Assembly of a Japanese bicycle requires greatest peace of spirit.
Hi Ivan Boldyrev,
> On 8686 day of my life Adam Warner wrote:
>> [I had hoped that my use of ZEROP would allow CMUCL to perform the
>> countdown comparison without having to load a register to compare
>> against. This may not be possible because CMUCL's fixnum
>> representation has tag bits and therefore 0 doesn't correspond to a
>> machine value of 0]
>
> It does. Adam, is it really you or some spoofer? :)
Hi, I'm the new and improved version.
If I don't misread this disassembly (by glancing at the assignment of 4
to ECX):
(disassemble
(compile nil (lambda () (declare (optimize (speed 3) (safety 0)))
(print 0))))
I see that EDX is being set to a machine value of 0 using the XOR idiom.
A little more experimentation with (print 1) and (print 2) shows that a
machine integer is four times the size of a CMUCL fixnum. Thus the only
time the Lisp representation matches the machine representation is when
the Lisp fixnum is zero.
I built a countdown variable hoping that a more efficient test could be
built by the compiler than a comparison to NIL. If we replace the above
disassembly with (print nil) we see that NIL is represented as a memory
location. Whether an object is NIL involves comparing an object to this
address, e.g. CMP EDX, #x2800000B, where #x2800000B is the address of NIL.
A comparison to zero doesn't require this address overhead. But there was
a fatal flaw: I didn't declare the type of the countdown variable. If we
look at this disassembly we will see that hideous generic arithmetic is
used to determine whether x is equal to zero:
(disassemble
(compile nil (lambda (x) (declare (optimize (speed 3) (safety 0)))
(zerop x))))
96: xor edi, edi ; No-arg-parsing entry point
98: call #x100004DE ; #x100004DE: generic-=
9D: mov esp, ebx
9F: cmp edx, #x2800000B ; nil
A5: jne L1
This call to a generic equal is much slower than comparing to the
address of NIL.
Let's see what the disassembly looks like if I declare x to be a fixnum:
(disassemble
(compile nil (lambda (x) (declare (optimize (speed 3) (safety 0))
(fixnum x))
(zerop x))))
70E: test edx, edx ; No-arg-parsing entry point
710: jeq L1
That's more like it!
My countdown variable was bound to the length of the list and LENGTH
returns a non-negative integer, not a fixnum.
Regards,
Adam
Adam Warner <······@consulting.net.nz> wrote:
+---------------
| I see that EDX is being set to a machine value of 0 using the XOR idiom.
| A little more experimentation with (print 1) and (print 2) shows that a
| machine integer is four times the size of a CMUCL fixnum.
+---------------
To be precise, it is four times the *range*, not size. The size of a
machine word is the *same* as the size of a fixnum, as is any other
CMUCL Lisp object (a.k.a. descriptor). The two low-order bits of CMUCL
fixnums are always zero. which which why they range over only 1/4
of the value space. (See "internal-design.txt"[1] for more detail.)
+---------------
| Thus the only time the Lisp representation matches the machine
| representation is when the Lisp fixnum is zero.
+---------------
Uh... Don't forget about the contents of elements of specialized arrays!
These can be identical to the machine representation.
+---------------
| I built a countdown variable hoping that a more efficient test could be
| built by the compiler than a comparison to NIL. If we replace the above
| disassembly with (print nil) we see that NIL is represented as a memory
| location. Whether an object is NIL involves comparing an object to this
| address, e.g. CMP EDX, #x2800000B, where #x2800000B is the address of NIL.
+---------------
This is a design choice CMUCL made, just one of several ways to
do it. In Common Lisp, NIL is a bit of a difficult case for type
representation, since it is *both* a symbol and the list terminator --
(AND (SYMBOLP NIL) (ENDP NIL)) ==> T -- *and* you want CAR/CDR to
be fast on it. CMUCL chose[1] to pun a CONS cell into the middle of
the NIL symbol object, said cell containing (CONS NIL NIL). Then they
put that symbol object in a fixed virtual address (#x2800000B). So
both CAR/CDR & symbol ops are fast,
One could choose some other representation for NIL to speed the ENDP
test, but then all of the *other* operations on NIL would be slowed down.
+---------------
| A comparison to zero doesn't require this address overhead.
+---------------
But if you steal the zero machine word for NIL, then you can't
do fast fixnum arithmetic without constantly adjusting offsets.
There's no free lunch.
Personally, I think the choices CMUCL made are generally pretty
reasonable, but YMMV.
-Rob
[1] As ${CMUCL-18E}/lib/cmucl/doc/impl/internal-design.txt notes,
the *3* lower bits of a machine word are used for tags, but
both the 000 and 100 (binary) codepoints are assigned to fixnums.
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
> In Common Lisp, NIL is a bit of a difficult case for type
> representation, since it is *both* a symbol and the list terminator --
> (AND (SYMBOLP NIL) (ENDP NIL)) ==> T -- *and* you want CAR/CDR to
> be fast on it.
Do you? Surely almost any time you write (even implicitly)
a CAR or CDR you expect it to be applied to something non-null.
When does the speed of (CAR NIL) and (CDR NIL) matter?
--
Gareth McCaughan
.sig under construc
Gareth McCaughan <················@pobox.com> writes:
> Rob Warnock wrote:
>
>> In Common Lisp, NIL is a bit of a difficult case for type
>> representation, since it is *both* a symbol and the list terminator --
>> (AND (SYMBOLP NIL) (ENDP NIL)) ==> T -- *and* you want CAR/CDR to
>> be fast on it.
>
> Do you? Surely almost any time you write (even implicitly)
> a CAR or CDR you expect it to be applied to something non-null.
> When does the speed of (CAR NIL) and (CDR NIL) matter?
See http://www.lisp.org/humor/large-programs.html for an example.
Zach
Gareth McCaughan wrote:
> Rob Warnock wrote:
>
>
>> In Common Lisp, NIL is a bit of a difficult case for type
>>representation, since it is *both* a symbol and the list terminator --
>>(AND (SYMBOLP NIL) (ENDP NIL)) ==> T -- *and* you want CAR/CDR to
>>be fast on it.
>
>
> Do you? Surely almost any time you write (even implicitly)
> a CAR or CDR you expect it to be applied to something non-null.
> When does the speed of (CAR NIL) and (CDR NIL) matter?
When you're using it as a termination test in a shortish loop, or any
other test where NIL is going to pop up a significant percentage of the
time. You don't need the test to be blazingly fast, but if it took
10x or more the number of cycles as the non-nil case it would start to
add up.
paul
Lowell Kirsh <······@cs.ubc.ca> wrote in message news:<············@mughi.cs.ubc.ca>...
> 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.
(defun join (seq delim)
(flet ((join-two (&optional (a "") (b ""))
(if (string= b "")
a
(concatenate 'string a delim b))))
(reduce #'join-two seq)))
maybe?
On Tue, 16 Mar 2004 18:53:11 -0800, Lowell Kirsh <······@cs.ubc.ca> wrote:
> 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"
>
> Any ideas?
>
> Lowell
>
format is too inefficient. try:
(defun join (delimitter list)
(reduce (lambda (a b) (concatenate 'string a delimitter b)) list)
note that delimitter must be s string not a char so
(join ":" '("1" "2" "3" "4")) gives "1:2:3:4"
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
On Wed, 17 Mar 2004 07:56:55 +0100, John Thingstad wrote:
> format is too inefficient. try:
>
> (defun join (delimitter list)
> (reduce (lambda (a b) (concatenate 'string a delimitter b)) list)
This is even less efficient: O(n^2) for large lists, format can be O(n).
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> wrote in message news:<······························@knm.org.pl>...
> On Wed, 17 Mar 2004 07:56:55 +0100, John Thingstad wrote:
> > format is too inefficient. try:
> > (defun join (delimitter list)
> > (reduce (lambda (a b) (concatenate 'string a delimitter b)) list)
>
> This is even less efficient: O(n^2) for large lists, format can be O(n).
Whatchoo talkin' about, Willis? Looks like O(n) to me. Through 10k
and 100k trials, my following two versions show O(n) performance. (My
functional version is very similar to John's.)
In fact, the functional version was 10X faster than the format
version.
;; format version
(defun join (list delimiter)
"Concatenate strings in list, but with delimiter in between."
(let ((format-string (concatenate 'string
"~{~A~^"
(string delimiter)
"~}")))
(format nil format-string list)))
;; functional version
(defun join (list delimiter)
"Concatenate strings in list, but with delimiter in between."
(reduce (lambda (x y)
(concatenate 'string x (string delimiter) y))
list))
;; tests
(string= "do:re:mi" (join '( "do" "re" "mi" ) ":"))
(string= "do:re:mi:" (join '( "do" "re" "mi" "") ":"))
(string= ":do:re:mi:" (join '("" "do" "re" "mi" "") ":"))
(string= "do:re:mi" (join '( "do" "re" "mi" ) #\:))
(string= "do:re:mi:" (join '( "do" "re" "mi" "") #\:))
(string= ":do:re:mi:" (join '("" "do" "re" "mi" "") #\:))
···········@yahoo.com (Tayssir John Gabbour) wrote in message news:<····························@posting.google.com>...
> Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> wrote in message news:<······························@knm.org.pl>...
> > On Wed, 17 Mar 2004 07:56:55 +0100, John Thingstad wrote:
> > > format is too inefficient. try:
> > > (defun join (delimitter list)
> > > (reduce (lambda (a b) (concatenate 'string a delimitter b)) list)
> >
> > This is even less efficient: O(n^2) for large lists, format can be O(n).
>
> Looks like O(n) to me.
I retract this statement. I completely misread.
···········@yahoo.com (Tayssir John Gabbour) wrote in message news:<····························@posting.google.com>...
> Whatchoo talkin' about, Willis? Looks like O(n) to me. Through 10k
> and 100k trials, my following two versions show O(n) performance. (My
> functional version is very similar to John's.)
CONCATENATE has to repeatedly copy a growing string:
"foo" ":" "bar" -> "foo:bar"
"foo:bar" ":" "fish" -> "foo:bar:fish"
and so on.
If you want a really brutal one, the best approach is likely to
traverse the list once, computing a buffer size, allocate a string
that big, and then traverse the list again copying elements (and
delimiters) into it. For added value be careful not to allocate a
too-fat string.
--tim
··········@tfeb.org (Tim Bradshaw) wrote in message news:<····························@posting.google.com>...
> If you want a really brutal one, the best approach is likely to
> traverse the list once, computing a buffer size, allocate a string
> that big, and then traverse the list again copying elements (and
> delimiters) into it. For added value be careful not to allocate a
> too-fat string.
Here is one like that, probably somewhat over-clever.
(defun join-strings (strings &key (delimiter #\Space)
(leading nil)
(trailing nil))
;; Optimized string joiner. LEADING and TRAILING are not implemented,
;; but if they were would cause leading & trailing delimiters
;; to be added
;; This makes heroic attempts to allocate just enough space and to
;; produce an appropriately-typed string. I suspect that a better
;; approach to typing the string would be to assume some narrow type
;; but be willing to punt with a wider type if need be.
(declare (type list strings)
(type (or character string) delimiter)
(optimize speed))
(when (or leading trailing)
(error "Not implemented, sorry"))
(when (null strings)
(return-from join-strings nil))
(flet ((et (et oet)
;; Make a hack job of deducing an appropriate string elt
;; type from two existing types
(cond ((null oet)
et)
((eql et oet)
et)
(t 'character))))
(declare (inline et))
(multiple-value-bind (slen num elt-type)
(loop for i upfrom 0
for s in strings
for eet = nil then (et (progn
(unless (stringp s)
(error 'type-error
:datum s
:expected-type 'string))
(array-element-type s)) eet)
summing (length s) into len
finally (return (values len i eet)))
(etypecase delimiter
(character
;; LW spends a long time in TYPE-OF here.
(loop with buf = (make-string (+ slen (1- num))
:element-type (et (type-of delimiter)
elt-type))
for s in strings
for l = (length s)
for i = 0 then (+ i l 1)
do
(unless (zerop i)
(setf (char buf (1- i)) delimiter))
(setf (subseq buf i) s)
finally (return buf)))
(string
(loop with dlen = (length delimiter)
with buf = (make-string (+ slen (* (1- num) dlen))
:element-type (et (array-element-type
delimiter)
elt-type))
for s in strings
for l = (length s)
for i = 0 then (+ i l dlen)
do
(unless (zerop i)
(setf (subseq buf (- i dlen)) delimiter))
(setf (subseq buf i) s)
finally (return buf)))))))
The difference is not as dramatic as it may seem...
> (profiling (join-format) (test-join #'join-format 10000))
JOIN-FORMAT, 3.47796
NIL
> (profiling (join-John-Thingstad) (test-join #'join-John-Thingstad 10000))
JOIN-JOHN-THINGSTAD, 1.193333
NIL
> (profiling (join-strings) (test-join #'join-strings 10000))
JOIN-STRINGS, 0.741098
NIL
So I still think reduce-concatenate strikes the balance right
On 17 Mar 2004 23:43:59 -0800, Tim Bradshaw <··········@tfeb.org> wrote:
> ··········@tfeb.org (Tim Bradshaw) wrote in message
> news:<····························@posting.google.com>...
>
>> If you want a really brutal one, the best approach is likely to
>> traverse the list once, computing a buffer size, allocate a string
>> that big, and then traverse the list again copying elements (and
>> delimiters) into it. For added value be careful not to allocate a
>> too-fat string.
>
> Here is one like that, probably somewhat over-clever.
...
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
John Thingstad <··············@chello.no> writes:
> The difference is not as dramatic as it may seem...
>
>> (profiling (join-format) (test-join #'join-format 10000))
> JOIN-FORMAT, 3.47796
> NIL
>
>> (profiling (join-John-Thingstad) (test-join #'join-John-Thingstad 10000))
> JOIN-JOHN-THINGSTAD, 1.193333
> NIL
>
>> (profiling (join-strings) (test-join #'join-strings 10000))
> JOIN-STRINGS, 0.741098
> NIL
Tim's version is about 33% faster than yours. My
with-output-to-string version is about three times faster than Tim's
version, which should make it about 4 times faster than yours.
--
Raymond Wiker Mail: ·············@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60
Try FAST Search: http://alltheweb.com/
Raymond Wiker <·············@fast.no> wrote in message news:<··············@raw.grenland.fast.no>...
> Tim's version is about 33% faster than yours. My
> with-output-to-string version is about three times faster than Tim's
> version, which should make it about 4 times faster than yours.
Humorously, that absurd thing I typed out, where I sent a huge
parameter list to concatenate, benchmarked the fastest on Clisp/Win2k
at various generated list sizes. About 37% faster than nearest
competitor on list of 100 elements, 16% faster on list of 1k.
(Elements had 10 chars, delimiter had 1.)
Apparently those Clisp guys really optmized concatenate.
However, testing 10k elements blew out the max # of parameters allowed
to a function. ;) So some trickery may be needed to choose the
appropriate code at compiletime or runtime.
Your solution and Tim's benchmarked nearly the same. Of course, since
you both optimized on your personal machines, I have little doubt you
both found your version faster the other guy's. ;)
Hmm, I should one day bulid a suite of random data for benchmarking
purposes... never know how smart lisp compilers are at exploiting
patterns, seeing that lisp used to be the AI language. I don't really
care about benchmarking, but OTOH it's not that hard for it to be part
of my test suite. It could complain if it empirically finds bad time
or space complexity.
···········@yahoo.com (Tayssir John Gabbour) writes:
> Raymond Wiker <·············@fast.no> wrote in message news:<··············@raw.grenland.fast.no>...
> > Tim's version is about 33% faster than yours. My
> > with-output-to-string version is about three times faster than Tim's
> > version, which should make it about 4 times faster than yours.
>
> Humorously, that absurd thing I typed out, where I sent a huge
> parameter list to concatenate, benchmarked the fastest on Clisp/Win2k
> at various generated list sizes. About 37% faster than nearest
> competitor on list of 100 elements, 16% faster on list of 1k.
> (Elements had 10 chars, delimiter had 1.)
>
> Apparently those Clisp guys really optmized concatenate.
CLISP is very weird. It's based around a byte-code interpreter, which
means there's a huge performance penalty for running your own code,
compared to the system functions, which are written in C, and thus
compiled to native code. Any performance characteristics you find
will amost certainly be exclusive to CLISP itself. Maximally
efficient code in CLISP isn't achieved by giving the compiler
opportunities to optimize, nor even necessarily by choosing the best
algorithmic complexity, but by stuffing as much computation into
built-in functions as is possible.
*IF* you're writing code for CLISP, that's fine. If you're speaking
about the efficiency of Lisp code in general, and if CLISP produces a
varying result, it's almost useless to bring it up.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
···········@yahoo.com (Tayssir John Gabbour) writes:
> Raymond Wiker <·············@fast.no> wrote in message news:<··············@raw.grenland.fast.no>...
> Your solution and Tim's benchmarked nearly the same. Of course, since
> you both optimized on your personal machines, I have little doubt you
> both found your version faster the other guy's. ;)
I didn't really look closely at Tim's code until after I had
posted my message, but it seems that his code is not restricted to a
list of strings. His code also conses *much* less than mine.
That said, I did not optimize my code... but I've previously
seen that sbcl is *very* good at producing good results for "simple"
code --- it's not just humans that have trouble following
hand-optimized code :-)
--
Raymond Wiker Mail: ·············@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60
Try FAST Search: http://alltheweb.com/
Raymond Wiker <·············@fast.no> wrote in message news:<··············@raw.grenland.fast.no>...
> I didn't really look closely at Tim's code until after I had
> posted my message, but it seems that his code is not restricted to a
> list of strings. His code also conses *much* less than mine.
I think it is restricted. What it does do is allow either a character
or a string as a delimiter, but it does that fairly badly - by having
two completely separate loops rather than having a string-only loop
and creating a stringy delimiter from a character one - that's just
misdesign I think.
What it *does* do is make some significant effort to produce a string
which is no fatter than it needs to be, assuming the lisp has multiple
string types, which I think most of the unicode-supporting ones do.
That has significant performance impact on LW, anyway. A way around
that would probably be to have an optional element-type argument,
which if given would cause it to bypass all the cleverness.
If yours is the repeatedly-concatenate one, then I think you
automatically get an optimal string type anyway, from properties of
concatenate.
One can spend for ever arguing about the design of these things. It's
generally better just to write one which does what you want rather
than try and get the design good enough for a library. Typically what
happens instead is that a `library-quality' one gets created which
actually isn't library-quality. Varous Java libraries are good
examples of this (as are some lisp ones, but I'm feeling polite today
so I'll name no names).
--tim
On 19 Mar 2004 02:54:46 -0800, ··········@tfeb.org (Tim Bradshaw) wrote:
> Typically what happens instead is that a `library-quality' one gets
> created which actually isn't library-quality. Varous Java libraries
> are good examples of this (as are some lisp ones, but I'm feeling
> polite today so I'll name no names).
Being someone who has occasionally published CL libraries I'd be happy
to hear (er, read) substantiated criticism. I think anyone who
releases code to the general public should be able to cope with
negative comments.
Edi.
Edi Weitz <···@agharta.de> wrote in message news:<··············@bird.agharta.de>...
> Being someone who has occasionally published CL libraries I'd be happy
> to hear (er, read) substantiated criticism. I think anyone who
> releases code to the general public should be able to cope with
> negative comments.
The problem is that I can't substantiate the criticism without
spending time looking at the things I want to be rude about, and I
don't have time. So I'd rather just attempt to cause a feeling of
general unease and stress if I can.
--tim
From: Joe Marshall
Subject: Re: How do I construct this string?
Date:
Message-ID: <r7vjeq53.fsf@comcast.net>
··········@tfeb.org (Tim Bradshaw) writes:
> The problem is that I can't substantiate the criticism without
> spending time looking at the things I want to be rude about, and I
> don't have time. So I'd rather just attempt to cause a feeling of
> general unease and stress if I can.
That's the usenet spirit!
--
~jrm
Tayssir John Gabbour <···········@yahoo.com> wrote:
> However, testing 10k elements blew out the max # of parameters allowed
> to a function. ;)
That's because you used (APPLY #'CONCATENATE '(STRING <some very big list>))
This will blow up when the list contains CALL-ARGUMENTS-LIMIT elements
or more. In theory, call-arguments-limit can be as low as 50 (see the
Hyperspec); in practice, Lispworks has a call-arguments-limit of 255.
The standard advice is to use REDUCE instead of APPLY in situations like this.
--
Arthur Lemmens
Raymond Wiker <·············@fast.no> wrote in message news:<··············@raw.grenland.fast.no>...
> Tim's version is about 33% faster than yours. My
> with-output-to-string version is about three times faster than Tim's
> version, which should make it about 4 times faster than yours.
I think it's worth bearing in mind that they don't do the same thing.
Mine spends a lot of effort making sure it produces a string no fatter
than it needs to, whereas some of the others (actually I think just
the stream one) will either produce a maximally fat string all the
time or just fail in some cases. Of course some rudimantary CL
implementations may not have multiple string types I guess.
The performance is also very implementation-dependent, especially the
string-stream stuff. On LW (which has multiple string types), Mine is
about 2x as slow as the string-stream one, but mine without the
type-cleverness is about 3x as fast.
--tim
Tim Bradshaw wrote:
> ··········@tfeb.org (Tim Bradshaw) wrote in message news:<····························@posting.google.com>...
>
>
>>If you want a really brutal one, the best approach is likely to
>>traverse the list once, computing a buffer size, allocate a string
>>that big, and then traverse the list again copying elements (and
>>delimiters) into it. For added value be careful not to allocate a
>>too-fat string.
>
>
> Here is one like that, probably somewhat over-clever.
Hi.
On my machine --
athon 1.6GHz, SBCL, strings length: 2-11, lists length: 2-21, no of lists 150K:
-------------------------------------------------------------------------------------
your version *** 2.913 seconds of real time ***
(defun join-strings (strings &key (delimiter #\Space)
(leading nil)
(trailing nil))
(declare (type list strings)
(type (or character string) delimiter)
(optimize (speed 3) (safety 0) (debug 0)))
.........
.........
-------------------------------------------------------------------------------------
my version *** 4.504 seconds of real time ***
(defun join-s (lst) (declare (optimize (speed 3) (safety 0) (debug 0)))
(let* ((lst2 (list (car lst))) (x (last lst2)))
(mapc (lambda (z) (rplacd x (list ":" z)) (setq x (cddr x))) (cdr lst))
(apply #'concatenate 'string lst2)))
-------------------------------------------------------------------------------------
Matthew Danish version *** 1.08 seconds of real time ***
(defun join-md (list) (declare (optimize (speed 3) (safety 0) (debug 0)))
(with-output-to-string (stream)
(loop for cons on list do
(write-string (car cons) stream)
(when (cdr cons) (write-string ":" stream)))))
regards, szymon.
···········@yahoo.com (Tayssir John Gabbour) wrote in message news:<····························@posting.google.com>...
> ;; functional version
> (defun join (list delimiter)
> "Concatenate strings in list, but with delimiter in between."
> (reduce (lambda (x y)
> (concatenate 'string x (string delimiter) y))
> list))
(defmacro nil? (&rest rest)
`(null ,@rest))
(defun join (list delimiter)
"Concatenate strings in list with delimiter in between."
(let ((d (string delimiter)))
(labels ((join-helper (list)
(cond ((nil? list)
nil)
((nil? (cdr list))
list) ;no delim
(t
(cons (car list)
(cons d
(join-helper (cdr list))))))))
(apply #'concatenate (cons 'string (join-helper list))))))
This is vaguely what I'd do. The implementation of concatenate on my
machine appears to work in O(n). I'm sure the code can be far cleaner
but I'm rather annoyed.
Maybe I'm thinking of Java's StringBuffer, who knows. I hate this.
···········@yahoo.com (Tayssir John Gabbour) writes:
> ···········@yahoo.com (Tayssir John Gabbour) wrote in message news:<····························@posting.google.com>...
>> ;; functional version
>> (defun join (list delimiter)
>> "Concatenate strings in list, but with delimiter in between."
>> (reduce (lambda (x y)
>> (concatenate 'string x (string delimiter) y))
>> list))
>
>
> (defmacro nil? (&rest rest)
> `(null ,@rest))
>
>
> (defun join (list delimiter)
> "Concatenate strings in list with delimiter in between."
> (let ((d (string delimiter)))
> (labels ((join-helper (list)
> (cond ((nil? list)
> nil)
> ((nil? (cdr list))
> list) ;no delim
> (t
> (cons (car list)
> (cons d
> (join-helper (cdr list))))))))
>
> (apply #'concatenate (cons 'string (join-helper list))))))
>
>
> This is vaguely what I'd do. The implementation of concatenate on my
> machine appears to work in O(n). I'm sure the code can be far cleaner
> but I'm rather annoyed.
>
> Maybe I'm thinking of Java's StringBuffer, who knows. I hate this.
(defparameter *test-list* (make-list 1000 :initial-element "foo"))
(defun join (list delimiter)
(with-output-to-string (ret)
(loop for (elt . next) on list
do (progn (write-string elt ret)
(when next
(write-string delimiter ret))))))
CL-USER> (time (progn (join *test-list* ":") (values)))
Evaluation took:
0.002 seconds of real time
0.0 seconds of user run time
0.001376 seconds of system run time
1 page fault and
17992 bytes consed.
; No value
CL-USER>
I'm not sure how this compares with other implementations, but
it should be quite similar to Java's StringBuffer (and C++'s
std::ostringstream).
--
Raymond Wiker Mail: ·············@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60
Try FAST Search: http://alltheweb.com/
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> wrote in message news:<······························@knm.org.pl>...
> On Wed, 17 Mar 2004 07:56:55 +0100, John Thingstad wrote:
> > (defun join (delimitter list)
> > (reduce (lambda (a b) (concatenate 'string a delimitter b)) list)
>
> This is even less efficient: O(n^2) for large lists, format can be O(n).
Incidentally, more testcases. My posts take a while to show up on Google.
(string= "" (join '("") "" ))
(string= "" (join '("") "X" ))
(string= "X" (join '("X") "" ))
(string= "X" (join '("X") ":" ))
On Wed, 17 Mar 2004 08:41:10 +0100, Marcin 'Qrczak' Kowalczyk
<······@knm.org.pl> wrote:
> On Wed, 17 Mar 2004 07:56:55 +0100, John Thingstad wrote:
>
>> format is too inefficient. try:
>>
>> (defun join (delimitter list)
>> (reduce (lambda (a b) (concatenate 'string a delimitter b)) list)
>
> This is even less efficient: O(n^2) for large lists, format can be O(n).
>
I just compared the time used for 100000 itterations for (join ":" ("foo"
"bar "baz"))
2.1 seconds for reduce.. 21 seconds for format.
Now be practical.
Why would you want a huge size to these strings.
The normal use would be to print it in a readable format on a screen.
You are far more likely to have a large number of such lines.
Altso the reduce - concatinate combo has a higher "coolness factor" ;)
consider this from othello.lisp (my implementation, not norvig's)
(defun print-moves (moves)
"function: print-moves
in: list of moves. See find-moves return type for details
returns: comma seperated moves
ex: \"A1, B2, C5\""
(if moves
(format t "~&Legal move~P ~:[is~;are~] ~A~%"
(length moves) (> (length moves) 1)
(reduce (lambda (e1 e2) (concatenate 'string e1 ", " e2))
(mapcar (lambda (e) (pos->string (pos e))) moves)))
(format t "~&No moves. You must pass!~%")
))
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
Hi John Thingstad,
> Also the reduce - concatenate combo has a higher "coolness factor" ;)
It does! But it looks like you need an extra conditional to deal with
empty lists. I tried playing with an :INITIAL-VALUE without success.
(defun join (delimiter list)
(if list
(reduce (lambda (a b) (concatenate 'string a delimiter b)) list)
""))
Regards,
Adam
Hi Marcin 'Qrczak' Kowalczyk,
> On Wed, 17 Mar 2004 07:56:55 +0100, John Thingstad wrote:
>
>> format is too inefficient. try:
>>
>> (defun join (delimitter list)
>> (reduce (lambda (a b) (concatenate 'string a delimitter b)) list)
>
> This is even less efficient: O(n^2) for large lists, format can be O(n).
Also, the function supplied to REDUCE is unable to deal with zero
arguments, which happens when the list is empty.
(join ":" '()) => Wrong argument count, wanted 2 and got 0.
Unless an :INITIAL-VALUE is supplied to REDUCE the function supplied
to REDUCE must be able to accept 0 or 2 arguments.
Regards,
Adam
From: szymon
Subject: Re: How do I construct this string? -- strange results (sbcl).
Date:
Message-ID: <c39nf1$487$1@nemesis.news.tpi.pl>
Lowell Kirsh wrote:
> 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"
>
> Any ideas?
;SBCL 0.8.8
;(JOIN-JOHN-THINGSTAD ":" *test-list*) ---> Evaluation took: 112.7 seconds
;(JOIN-MATTHEW-DANISH *test-list*) ---> Evaluation took: 41.2 seconds
;(JOIN-SZYMON *test-list*) ---> Evaluation took: 6.39 seconds
(defun join-szymon (lst)
(let* ((lst2 (list (car lst))) (x (last lst2)))
(mapc (lambda (z)
(rplacd x (list (concatenate 'string ":" z))) (setq x (cdr x)))
(cdr lst))
(apply #'concatenate 'string lst2)))
(defun join-Matthew-Danish (list &optional (delim ":"))
(with-output-to-string (stream)
(loop for cons on list do
(princ (car cons) stream)
(when (cdr cons) (princ delim stream)))))
(defun join-John-Thingstad (delimitter list)
(reduce (lambda (a b) (concatenate 'string a delimitter b)) list))
(defun set-test-list NIL
(setq
*test-list*
(loop repeat 20000
collect (apply
#'concatenate 'string
(loop repeat (1+ (random 10))
collect (do ((x (random 123) (random 123)))
((or
(and (> x 64) (< x 91))
(and (> x 96) (< x 123)))
(string (code-char x)))))))))
;regards. szymon.
From: Matthew Danish
Subject: Re: How do I construct this string? -- strange results (sbcl).
Date:
Message-ID: <20040317204112.GC26870@mapcar.org>
Please, compare apples with apples:
(defun join-matthew-danish (list &optional (delim ":"))
(with-output-to-string (stream)
(loop for cons on list do
(write-string (car cons) stream)
(when (cdr cons) (write-string delim stream)))))
PRINC is a lot more general.
CL-USER> (time (test 'join-szymon))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 1.44 seconds of real time
; 1.41 seconds of user run time
; 0.02 seconds of system run time
; 2,641,938,552 CPU cycles
; 0 page faults and
; 3,074,400 bytes consed.
;
; No value
CL-USER> (time (test 'join-matthew-danish))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 0.01 seconds of real time
; 0.0 seconds of user run time
; 0.0 seconds of system run time
; 12,735,483 CPU cycles
; 0 page faults and
; 458,984 bytes consed.
;
; No value
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
szymon wrote:
> Lowell Kirsh wrote:
>
>> 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"
>>
>> Any ideas?
>
>
> ;SBCL 0.8.8
>
> ;(JOIN-JOHN-THINGSTAD ":" *test-list*) ---> Evaluation took: 112.7
> seconds
>
> ;(JOIN-MATTHEW-DANISH *test-list*) ---> Evaluation took: 41.2 seconds
>
> ;(JOIN-SZYMON *test-list*) ---> Evaluation took: 6.39 seconds
>
>
> (defun join-szymon (lst)
> (let* ((lst2 (list (car lst))) (x (last lst2)))
> (mapc (lambda (z)
> (rplacd x (list (concatenate 'string ":" z))) (setq x (cdr x)))
> (cdr lst))
> (apply #'concatenate 'string lst2)))
>
>
> (defun join-Matthew-Danish (list &optional (delim ":"))
> (with-output-to-string (stream)
> (loop for cons on list do
> (princ (car cons) stream)
> (when (cdr cons) (princ delim stream)))))
>
>
> (defun join-John-Thingstad (delimitter list)
> (reduce (lambda (a b) (concatenate 'string a delimitter b)) list))
>
>
>
> (defun set-test-list NIL
> (setq
> *test-list*
> (loop repeat 20000
> collect (apply
> #'concatenate 'string
> (loop repeat (1+ (random 10))
> collect (do ((x (random 123) (random 123)))
> ((or
> (and (> x 64) (< x 91))
> (and (> x 96) (< x 123)))
> (string (code-char x)))))))))
>
> ;regards. szymon.
CL-USER> (defun test-jt nil (time (mapcar #'(lambda (x) (JOIN-JOHN-THINGSTAD ":" x)) *test-listsss*)) nil)
TEST-JT
CL-USER> (compile 'test-jt)
.....
.....
.....
CL-USER> (test-s) ; Evaluation took: 0.38 seconds of real time
CL-USER> (test-jt) ; Evaluation took: 0.38 seconds of real time
CL-USER> (test-md) ; Evaluation took: 1.14 seconds of real time
(defun set-test-short-list-s NIL
(setq *test-listsss* (list (list "foo" "bar")))
(loop repeat 20000 do
(push (loop repeat (+ 3 (random 5)) collect
(apply
#'concatenate 'string
(loop repeat (1+ (random 10)) collect
(do ((x (random 123) (random 123)))
((or
(and (> x 64) (< x 91))
(and (> x 96) (< x 123)))
(string (code-char x)))))))
*test-listsss*)))
regards. szymon.
From: John Thingstad
Subject: Re: How do I construct this string? -- strange results (sbcl).
Date:
Message-ID: <opr40k74uuxfnb1n@news.chello.no>
On Wed, 17 Mar 2004 15:22:21 +0100, szymon <······@dont.have.email> wrote:
my algoriotm runs n^2.
reduce has order n * concatenate of order n.
What you have generated is a absolute worst case.
The number of elements to concatenate is 20000 * 3 * 10000 = 600 000 000
operations!
This algorithm works ok for more normal cases of say 10 elements done many
times.
Here is I belive a more realistic example.
(defconstant ascii-size 26)
(defconstant ascii-upper 65)
(defconstant ascii-lower 97)
(defun rnd-letter ()
(code-char
(if (zerop (random 2))
(+ #.ascii-lower (random #.ascii-size))
(+ #.ascii-upper (random #.ascii-size)))))
(defun rnd-word ()
(let* ((size (1+ (random 10)))
(word (make-string size)))
(dotimes (i size)
(setf (aref word i) (rnd-letter)))
word))
(defun rnd-list ()
(loop repeat (1+ (random 10)) collect (rnd-word)))
(defun test-join (join-function times)
(loop repeat times do
(funcall join-function (rnd-list))))
> (time (test-join #'join-szymon 10000))
Total Execution time: 2.835839 seconds
Time spent garbage collecting: 0.045884 seconds
NIL
> (time (test-join #'join-Matthew-Danish 10000))
Total Execution time: 3.571486 seconds
Time spent garbage collecting: 0.125904 seconds
NIL
> (time (test-join #'join-John-Thingstad 10000))
Total Execution time: 3.163052 seconds
Time spent garbage collecting: 0.052283 seconds
NIL
> Lowell Kirsh wrote:
>> 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"
>>
>> Any ideas?
>
> ;SBCL 0.8.8
>
> ;(JOIN-JOHN-THINGSTAD ":" *test-list*) ---> Evaluation took: 112.7
> seconds
>
> ;(JOIN-MATTHEW-DANISH *test-list*) ---> Evaluation took: 41.2
> seconds
>
> ;(JOIN-SZYMON *test-list*) ---> Evaluation took: 6.39
> seconds
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
From: szymon
Subject: Re: How do I construct this string? -- strange results (sbcl).
Date:
Message-ID: <c3ami2$ic7$2@nemesis.news.tpi.pl>
John Thingstad wrote:
> On Wed, 17 Mar 2004 15:22:21 +0100, szymon <······@dont.have.email> wrote:
>
> my algoriotm runs n^2.
> reduce has order n * concatenate of order n.
> What you have generated is a absolute worst case.
> The number of elements to concatenate is 20000 * 3 * 10000 = 600 000 000
> operations!
> This algorithm works ok for more normal cases of say 10 elements done
> many times.
> Here is I belive a more realistic example.
Ok, thanks for reply.
From: Espen Vestre
Subject: Re: How do I construct this string? -- strange results (sbcl).
Date:
Message-ID: <kwr7vqjyac.fsf@merced.netfonds.no>
John Thingstad <··············@chello.no> writes:
>> (time (test-join #'join-szymon 10000))
> Total Execution time: 2.835839 seconds
> Time spent garbage collecting: 0.045884 seconds
> NIL
>> (time (test-join #'join-Matthew-Danish 10000))
> Total Execution time: 3.571486 seconds
> Time spent garbage collecting: 0.125904 seconds
> NIL
On LW 4.3.6/linux (Athlon 2200xp+), the Matthew Danish version
is considerably faster, which I think is quite neat, since it's
such a straightforward nice little function.
CL-USER 71 > (time (test-join #'join-szymon 100000))
Timing the evaluation of (TEST-JOIN (FUNCTION JOIN-SZYMON) 100000)
user time = 4.170
system time = 0.010
Elapsed time = 0:00:06
Allocation = 35228656 bytes standard / 35384646 bytes conses
0 Page faults
Calls to %EVAL 35
NIL
CL-USER 72 > (time (test-join #'join-matthew-danish 100000))
Timing the evaluation of (TEST-JOIN (FUNCTION JOIN-MATTHEW-DANISH) 100000)
user time = 2.220
system time = 0.000
Elapsed time = 0:00:03
Allocation = 22067216 bytes standard / 7333568 bytes conses
0 Page faults
Calls to %EVAL 591
NIL
--
(espen)
Lowell Kirsh <······@cs.ubc.ca> writes:
> 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"
I would vote to add such a function (and its inverse) to
COMMON-LISP-2010. It seems we can't spend a week without someone
asking for it.
--
__Pascal_Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he doesn't
want merely because you think it would be good for him.--Robert Heinlein
http://www.theadvocates.org/
Pascal Bourguignon <····@thalassa.informatimago.com> writes:
> I would vote to add such a function (and its inverse) to
> COMMON-LISP-2010. It seems we can't spend a week without someone
> asking for it.
Sure, we need something to give the perl-heads approaching lisp
a warm welcome :-)
--
(espen)
From: Grzegorz =?UTF-8?B?Q2hydXBhxYJh?=
Subject: Re: How do I construct this string?
Date:
Message-ID: <c3a4sn$29t$1@news.ya.com>
Pascal Bourguignon wrote:
>
> Lowell Kirsh <······@cs.ubc.ca> writes:
>
>> 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"
>
> I would vote to add such a function (and its inverse) to
> COMMON-LISP-2010. It seems we can't spend a week without someone
> asking for it.
>
Shouldn't CL have a something along the lines of the SRFI process to
semi-standardize common libraries? Scheme has had a great standard string
library (srfi-13) for quite a few years now.
--
Grzegorz Chrupała
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))))))
Regards,
Adam
In article <······························@consulting.net.nz>,
Adam Warner <······@consulting.net.nz> 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))))))
>
> Regards,
> Adam
Since you can compute the length of the new string, why not
create the new string with the right length and copy the other
stuff into the new string?
Hi Rainer Joswig,
>> (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))))))
>>
>> Regards,
>> Adam
>
> Since you can compute the length of the new string, why not
> create the new string with the right length and copy the other
> stuff into the new string?
This also involves calculating the length of every string. The approach
appears to be slower but it conses five times less on the implementation I
tested (CMUCL):
(defun join (list &optional (delimiter #\:))
(if list
(let ((1+string-len 0) (index 0))
(declare (fixnum 1+string-len index))
(dolist (item list)
(setf 1+string-len (+ 1+string-len (length item) 1)))
(let ((string (make-string (1- 1+string-len)
:initial-element delimiter)))
(dolist (item list)
(setf (subseq string index) item)
(setf index (+ index (length item) 1)))
string))
""))
Regards,
Adam
Can it be final version? It's small, fast and loopy.
Thanks everyone for nice examples.
(defun join (lst)
(with-output-to-string (s)
(loop for (a . d) on lst do (write-string a s)
if d do (write-char #\: s))))
regards, szymon.
szymon <······@dont.have.email> writes:
> (defun join (lst)
> (with-output-to-string (s)
> (loop for (a . d) on lst do (write-string a s)
> if d do (write-char #\: s))))
Stylistically, I'd suggest this:
(defun join (list)
(with-output-to-string (s)
(loop for (a . d) on list
do (write-string a s)
(when d (write-char #\: s)))))
I.e. to use loop's keywords only when it is necessary, and otherwise
prefer the normal lisp control oprators, in this case "when".
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld wrote:
> szymon <······@dont.have.email> writes:
>
>
>>(defun join (lst)
>> (with-output-to-string (s)
>> (loop for (a . d) on lst do (write-string a s)
>> if d do (write-char #\: s))))
>
>
> Stylistically, I'd suggest this:
>
> (defun join (list)
> (with-output-to-string (s)
> (loop for (a . d) on list
> do (write-string a s)
> (when d (write-char #\: s)))))
>
>
> I.e. to use loop's keywords only when it is necessary, and otherwise
> prefer the normal lisp control oprators, in this case "when".
>
... which happen to be a LOOP keyword
(defun join (string-list)
(with-output-to-string (s)
(loop for (string . more-strings) on string-list
do (write-string string s)
when more-strings do (write-char #\: s))))
Cheers
--
Marco
Frode Vatvedt Fjeld wrote:
>> [..] I.e. to use loop's keywords only when it is necessary, and
>> otherwise prefer the normal lisp control oprators, in this case
>> "when".
Marco Antoniotti <·······@cs.nyu.edu> writes:
> ... which happen to be a LOOP keyword [..]
I know, but my point was not "when" vs. "if", but that I think it is
good style to prefer the regular lisp operators when one has a choice
between those and the loop keywords. That means that one uses the loop
keywords (like when) only in situations like this:
(loop for (a . b) on list
collect a
when b collect separator)
Because you can't say something like
(loop for (a . b) on list
collect a
do (when b (collect separator)))
Not that this is terribly important, though.
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld wrote:
> Stylistically, I'd suggest this:
[.....]
> I.e. to use loop's keywords only when it is necessary, and otherwise
> prefer the normal lisp control oprators, in this case "when".
For some days now I have been trying to use the LOOP operator as
I noticed that some programmers were making use of it (in spite of
the opinion that the LOOP had been badly designed) - simply I want
to give it a try, maybe I will like it?
In other circumstances I would write it as:
(defun join (lst)
(with-output-to-string (s)
(write-string (car lst) s)
(mapc (lambda (string) (write-char #\: s) (write-string string s)) (cdr lst))))
but I reckon everything should be given a fair chance [if I get some
free time, I would like very much to get acquainted with R.C.Waters's
invention (SERIES)].
regards, szymon.
Lowell Kirsh wrote:
> 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"
A lot of great suggestions have been made, but I didn't see one using
the Series package [1], so if you're interested in that, here's my go:
(defun join (string-list &optional (separator ":"))
(collect-append 'string
(spread (catenate (make-series 0) (series 1))
(scan string-list)
separator)))
I'm not sure how it compares in performance to the other methods. With
the implementation at [1] JOIN's body macroexpands into a loop that
conses up a list, nreverses it, and applies CONCATENATE 'string to it.
Regards,
Dirk Gerrits
[1] Get it at http://series.sourceforge.net/.
Additional documentation in AIM-1082 and AIM-1083 at
http://publications.ai.mit.edu/publications/pubsDB/pubs.html.