Author |
Message |
Vladimir V. Zolotyc #1 / 24
|
JOIN[1-3]
Hello I needed to join strings. I wrote three version of JOIN function. Which one is preferable from point of good style, efficiency, clarity etc. ? (defun join1 (&rest strings) (flet ((f (s) (apply #'concatenate (cons 'string (map 'list #'(lambda (x) (concatenate 'string x " ")) s))))) (let* ((s (f strings)) (n (length s))) (subseq s 0 (1- n))))) (f strings))) (defun join2 (&rest strings) (let ((r "") (need-separator 0)) (declare (type string r)) (declare (type fixnum need-separator)) (do ((s strings (cdr s))) ((null s)) (when (plusp need-separator) (setf r (concatenate 'string r " "))) (incf need-separator) (setf r (concatenate 'string r (car s)))) r)) (defun join3 (&rest strings) (loop with r of-type string = "" for s of-type string in strings for need-separator of-type fixnum from 0 when (plusp need-separator) do (setf r (concatenate 'string r " ")) do (setf r (concatenate 'string r s)) finally (return r))) I'm sure your version will be much better. I'll study it carefully if you let me know about it. Probably COMMON LISP already has such function. I didn't find it. I'm not knowing CLHS very well yet. Thanks in advance --
|
Mon, 04 Aug 2003 01:34:18 GMT |
|
|
Janis Dzerin #2 / 24
|
JOIN[1-3]
Quote: > I needed to join strings. I wrote > three version of JOIN function.
From your post looks like concatenate is not what you need. From your source looks like you want to make a string which contains strings passed as parameter, but separated by spaces. I'd suggesst looking at REDUCE. My version using it takes 4 lines (and takes separator as a keyword argument). (If nobody posts the answer and you still can't come up with the solution, let me know.) Janis Dzerins -- If million people say a stupid thing it's still a stupid thing.
|
Mon, 04 Aug 2003 01:42:02 GMT |
|
|
Geoff Summerhaye #3 / 24
|
JOIN[1-3]
Quote: > Hello > I needed to join strings. I wrote > three version of JOIN function. > Which one is preferable from point of good style, > efficiency, clarity etc. ? > (defun join1 (&rest strings) > (flet ((f (s) > (apply #'concatenate > (cons 'string (map 'list #'(lambda (x) (concatenate > 'string x " ")) s))))) > (let* ((s (f strings)) > (n (length s))) > (subseq s 0 (1- n))))) > (f strings))) > (defun join2 (&rest strings) > (let ((r "") > (need-separator 0)) > (declare (type string r)) > (declare (type fixnum need-separator)) > (do ((s strings (cdr s))) > ((null s)) > (when (plusp need-separator) (setf r (concatenate 'string r " "))) > (incf need-separator) > (setf r (concatenate 'string r (car s)))) > r)) > (defun join3 (&rest strings) > (loop with r of-type string = "" > for s of-type string in strings > for need-separator of-type fixnum from 0 > when (plusp need-separator) do (setf r (concatenate 'string r > " ")) > do (setf r (concatenate 'string r s)) > finally (return r))) > I'm sure your version will be much better. I'll study it > carefully if you let me know about it. > Probably COMMON LISP already has such function. I didn't find it. > I'm not knowing CLHS very well yet.
I'm just a newbie myself, but I'll take a stab at this in hopes of learning something. (defun join-ex (x y) (concatenate 'string x y)) (defun join (&rest strings) (reduce #'join-ex strings)) How's that? Geoff
|
Mon, 04 Aug 2003 01:51:29 GMT |
|
|
Tim Bradsha #4 / 24
|
JOIN[1-3]
Quote:
> I'd suggesst looking at REDUCE. My version using it takes 4 lines (and > takes separator as a keyword argument).
Nah. (format nil "~{~A~^ ~}" strings) Vastly increased crypticness, and it really annoys the linguistic-purity brigade by reminding them that there's this whole other language they need to get rid of once they've done for LOOP, which is always a good thing. For added annoyance value you should define some special syntax for this, I usually go for something like: #{nil "~{~A~^ ~}" strings} --tim, for the campaign for linguistic impurity
|
Mon, 04 Aug 2003 02:30:06 GMT |
|
|
Geoff Summerhaye #5 / 24
|
JOIN[1-3]
Quote: > I needed to join strings. I wrote > three version of JOIN function.
Well, after posting two functions that use concatenate to do what concatenate does by default, I came up with this: (defun join (&rest strings) (reduce #'join-ex (append (mapcar #'(lambda (x) (concatenate 'string x " ")) (butlast strings)) (last strings)))) (defun join-ex (x y) (concatenate 'string x y)) Hideous, yes? My copy of Graham's ANSI CL arrived yesterday, so don't beat me up too badly. I like Tim's (format nil...) solution, you just have to love a language that allows so many choices to accomplish the same thing, even if it allows you to come up with things like my little gem. Now all I need is more time to play with the language, work wants C/C++ and VB(shudder), the AI course last term used Prolog, and the course in numerical methods this term uses Java of all things. Geoff
|
Mon, 04 Aug 2003 03:53:06 GMT |
|
|
Geoff Summerhaye #6 / 24
|
JOIN[1-3]
Quote:
> > I needed to join strings. I wrote > > three version of JOIN function. > Well, after posting two functions that use concatenate to do what > concatenate does by default, I came up with this: > (defun join (&rest strings) > (reduce #'join-ex > (append > (mapcar #'(lambda (x) (concatenate 'string x " ")) > (butlast strings)) > (last strings)))) > (defun join-ex (x y) > (concatenate 'string x y))
Ohh, what an idiot I am!! (defun join-ex(x y) (concatenate 'string x " " y)) (defun join (&rest strings) (reduce #'join-ex strings)) Geoff
|
Mon, 04 Aug 2003 04:31:38 GMT |
|
|
Lieven Marchan #7 / 24
|
JOIN[1-3]
Quote: > I'm sure your version will be much better. I'll study it > carefully if you let me know about it. > Probably COMMON LISP already has such function. I didn't find it. > I'm not knowing CLHS very well yet.
I don't know about better. Some people won't like the following because it uses another little language embedded in CL but for your entertainment: (defun join (&rest strings)
--
Glaer ok reifr skyli gumna hverr, unz sinn ber bana.
|
Mon, 04 Aug 2003 04:38:28 GMT |
|
|
Thomas A. Ru #8 / 24
|
JOIN[1-3]
Quote:
> Well, after posting two functions that use concatenate to do what > concatenate does by default, I came up with this:
Since there was some mention in this thread about efficiency and style, I will take this example to show how to avoid some common Lisp pitfalls in algorithm design. The existence of convenient but expensive functions like BUTLAST, LAST and APPEND can often lead one astray. Quote: > (defun join (&rest strings) > (reduce #'join-ex > (append > (mapcar #'(lambda (x) (concatenate 'string x " ")) > (butlast strings)) > (last strings))))
This function ends up traversing the list of strings 5 times: 1. Construct a new list of all but the last string 2. Mapcar over that list 3. Find the last element 4. Traverse and copy the results of the mapcar list in append. 5. Reduce on the results A very simple rewrite of this function produces a much better algorithm without even changing the general operation. (defun join (&rest strings) (reduce #'join-ex (cons (first strings) (mapcar #'(lambda (x) (concatenate 'string " " x)) (rest strings))))) This reduces the list traversal from 5 to 2: 1. The mapcar on rest 2. The reduce on the results Although (as other parts of the thread indicate) there may be better solutions, I chose to use this to illustrate how thinking a little bit about the the operations involved and the order in which things are done can already yield nicer results. I have recently converted a number of loops inherited from a predecessor that had exactly the same structure. Given a list of objects and something that was to be inserted between them, one can choose to view the process as either treating the last element specially or treating the first element specially. I think there is a "natural" tendency to view the last element specially, since such lists are often written in natural language as 1, 2, 3, 4, 5. with the strong association of the punctuation with the preceding element. However, recasting this as associating the inter-element punctuation with the following element and treating the first element and the trailing punctuation specially allows one to process the list without the need to first figure out how many elements are there. Quote: > (defun join-ex (x y) > (concatenate 'string x y))
--
|
Mon, 04 Aug 2003 06:54:11 GMT |
|
|
Thomas A. Ru #9 / 24
|
JOIN[1-3]
Quote:
> (defun join (&rest strings)
Or (defun join (&rest strings) (format nil "~{~A~^ ~}" strings)) --
|
Mon, 04 Aug 2003 06:40:21 GMT |
|
|
Thomas A. Ru #10 / 24
|
JOIN[1-3]
Quote:
> > I needed to join strings. I wrote > > three version of JOIN function. > > Which one is preferable from point of good style, > > efficiency, clarity etc. ?
Yet another option that I haven't seen yet: (defun join (&rest strings) (with-output-to-string (output-string) (princ (first strings) output-string) (dolist (element (rest strings)) (princ " " output-string) (princ element output-string)))) This is a technique that is more useful if you have fairly complicated and especially non-uniform processing for each element, it is rather overkill for something this uniform. It also works better than multiple calls to CONCATENATE when you have a long list of things to operate on, since each concatenate call ends up creating a new string, most of which are then immediately discarded. --
|
Mon, 04 Aug 2003 07:00:29 GMT |
|
|
Geoffrey Summerhaye #11 / 24
|
JOIN[1-3]
Quote: > A very simple rewrite of this function produces a much better algorithm > without even changing the general operation. > (defun join (&rest strings) > (reduce #'join-ex > (cons (first strings) > (mapcar #'(lambda (x) (concatenate 'string " " x)) > (rest strings)))))
Yes, I shuddered as I wrote it. I knew it was way too computationally expensive. Thanks for the tips. Geoff
|
Mon, 04 Aug 2003 11:29:10 GMT |
|
|
Geoffrey Summerhaye #12 / 24
|
JOIN[1-3]
Quote: ----- Original Message -----
Newsgroups: comp.lang.lisp Sent: February 14, 2001 5:54 PM Subject: Re: JOIN[1-3] | | Since there was some mention in this thread about efficiency and style, | I will take this example to show how to avoid some common Lisp pitfalls | in algorithm design. The existence of convenient but expensive | functions like BUTLAST, LAST and APPEND can often lead one astray. Oops! Before I go for the night, what did you think of the last one? I reiterate it here, replacing the join-ex function with a lambda. (defun join (&rest strings) (reduce #'(lambda (x y) (concatenate 'string x " " y)) strings)) How the heck do you decide where to put whitespace, by the way? Is this OK? Geoff
|
Mon, 04 Aug 2003 12:17:25 GMT |
|
|
Bernhard Pfahring #13 / 24
|
JOIN[1-3]
Quote: > Hello >I needed to join strings. I wrote >three version of JOIN function. >Which one is preferable from point of good style, >efficiency, clarity etc. ?
Unfortunately, these points are conflicting goals quite often. Tim Bradshaw's and Thom Russ' version is definitely the most concise version (and also the clearest one, if you happen to speak the format-sublanguage :-) (defun join (&rest strings) (format nil "~{~A~^ ~}" strings)) If you need utmost efficiency, you'd probably end up with C-like Lisp as in the following, which happens to beat the above by a factor of 20 when joining 1000 strings of length 1000. One reason is that this algorithm has linear behaviour in the number of input-strings. (defun join (&rest strings) (if (null strings) "" (loop with result = (make-array (1- (loop for string in strings sum (1+ (length string)))) :element-type 'base-char :initial-element #\space) for string in strings as start = 0 then (1+ end) as end = (+ start (length string)) do (setf (subseq result start end) string) finally (return result)))) cheers, Bernhard -- -------------------------------------------------------------------------- Bernhard Pfahringer Dept. of Computer Science, University of Waikato http://www.cs.waikato.ac.nz/~bernhard +64 7 838 4041 --------------------------------------------------------------------------
|
Mon, 04 Aug 2003 12:51:22 GMT |
|
|
Vebjorn Ljos #14 / 24
|
JOIN[1-3]
| | I needed to join strings. I wrote | three version of JOIN function. | | Which one is preferable from point of good style, | efficiency, clarity etc. ? here's my suggestion: (defun interleave (separator list) (loop for x on list collect (car x) until (null (cdr x)) collect separator)) (defun join-strings (strings &optional (separator " ")) (apply #'concatenate (cons 'string (interleave separator strings)))) I'm sure it can be done more efficiently (without consing at all), but this is easy to read, and INTERLEAVE is useful in its own right. -- Vebjorn
|
Mon, 04 Aug 2003 16:07:06 GMT |
|
|
Jason Trenout #15 / 24
|
JOIN[1-3]
Quote:
> | > | I needed to join strings. I wrote > | three version of JOIN function. > | > | Which one is preferable from point of good style, > | efficiency, clarity etc. ? > here's my suggestion: > (defun interleave (separator list) > (loop > for x on list > collect (car x) > until (null (cdr x)) > collect separator))
Remember you can do destructuring in LOOP: (defun interleave (separator list) (loop for (x . more) on list collect x until (not more) collect separator)) __Jason
|
Mon, 04 Aug 2003 17:59:04 GMT |
|
|