nth vs ca[d...]r ... and more?

Hi all,

Immediate question:
When to use nth vs car cdr combinations?

For example, would ca[d...]rs be better here, or does it not matter?
;;; Calculates the cross product of two three-element vectors
(defun CrossProd (arglst / a b)
(mapcar 'set '(a b) arglst)
(list (- (* (nth 1 a) (nth 2 b)) (* (nth 2 a) (nth 1 b)))
(- (* (nth 2 a) (nth 0 b)) (* (nth 0 a) (nth 2 b)))
(- (* (nth 0 a) (nth 1 b)) (* (nth 1 a) (nth 0 b)))
)
)


More general if anyone's interested:
I've seen many sidebar discussions regarding the efficiencies of various
list manipulation approaches, but can't seem to locate a collected
discussion of these matters. Anyone care to point me in the right
direction, or banter several here in one place? Like;

;To incrementally build a list
(setq lst (cons itm lst))
;and reverse at end if needed is better than
(setq lst (append (list itm) lst))
;right?

;to remove the last element, is
(reverse (cdr (reverse lst)))
;better than building a new list omitting the last item?

;to append one element to an existing list, is
(reverse (cons itm (reverse lst)))
;better than
(append lst (list itm))
;?

....and I'm sure plenty others that do not immediatly come to mind.

 

James,

In most cases, I can't see where it matters if you use (nth) vs (car/cadr..)
functions. In the CrossProd function example, it's more evident in reading the
code which element in the list you are after, so that may be the deciding
factor.

I have a sneaking suspicion that the (cadr) type functions are really shortcut
wrappers for an (nth)-type function anyway, where the desired element's position
is already known. I seem to recall that most of the basic LISP functions we all
know and love are really offshoots of even more primitive functions and
constructs. But someone who knows the inner workings of LISP could answer that
better than me.

Matt

 

My preference is to use cxxxxr functions where possible.

 

I have a sneaking suspicion that the (cadr) type functions are really
shortcut

In the original lisp paper, McCarthy showed how a complete symbolic logic
language could be built out of about a half dozen primitive functions:
quote, atom, eq, cons, car, cdr, and cond. So the c****r cousins seem to be
"older" than nth. Somewhere I read that the only reason to limit these to
four levels was that's about all a normal person can hold in their head.

Paul Graham shows some cool examples at http://www.paulgraham.com ...

defun null (x)
(eq x '()))

(defun and (x y)
(cond (x (cond (y 't) ('t '())))
('t '())))

(defun not (x)
(cond (x '())
('t 't)))

Whether or not any functions are defined internally in terms of simpler
primitives in current lisp implementations, I have no idea, but kind of
doubt it.

Personally I tend to use car and cdr, occasionally a c**r, and usually nth
for anything over 3 elements. Though if the list is of any length, I try not
to avoid depending on its length or order.

 

Hi James Allen schrieb:

In addition to the other replies you might consider:

You can't replace cd[*]r by nth...

IMHO, ca[d...]rs are faster...

Yes, like a Ferrari versus an old beetle...

Using of append depends also from code context, examples:
$ (apply 'append '((1 2 0) (3 4 0) (5 6 0)))
(1 2 0 3 4 0 5 6 0)
$ (apply 'append '((1 2) nil (3 4) nil))
(1 2 3 4)
this can't be done by cons...

Cheers

 

Here are my tests.

As it has already been said,

although there is not a substantial difference
among Ca[d...]r and Nth I prefer to use Ca[d...]r.

For the function Nth read also the thread:

Date: Jan/01/05 "a zero length list?"

see below for a "cut".

Instead, cons is very faster than append.

Cheers.

--

Marc'Antonio Alessi
http://xoomer.virgilio.it/alessi
(strcat "NOT a " (substr (ver) 8 4) " guru.")

--


(defun Car___Test (val / ) (car val))
(defun Nth_0_Test (val / ) (nth 0 val))
(defun Cadr__Test (val / ) (cadr val))
(defun Nth_1_Test (val / ) (nth 1 val))
(defun Caddr_Test (val / ) (caddr val))
(defun Nth_2_Test (val / ) (nth 2 val))
(defun CadddrTest (val / ) (cadddr val))
(defun Nth_3_Test (val / ) (nth 3 val))

(timerU '(Car___Test '(0 1 2 3)) 100000)
(timerU '(Nth_0_Test '(0 1 2 3)) 100000)
(timerU '(Cadr__Test '(0 1 2 3)) 100000)
(timerU '(Nth_1_Test '(0 1 2 3)) 100000)
(timerU '(Caddr_Test '(0 1 2 3)) 100000)
(timerU '(Nth_2_Test '(0 1 2 3)) 100000)
(timerU '(CadddrTest '(0 1 2 3)) 100000)
(timerU '(Nth_3_Test '(0 1 2 3)) 100000)

; CAR___TEST > 100000 iterations: 3.09 secs.
; NTH_0_TEST > 100000 iterations: 3.1 secs.
; CADR__TEST > 100000 iterations: 3.1 secs.
; NTH_1_TEST > 100000 iterations: 3.13 secs.
; CADDR_TEST > 100000 iterations: 3.09 secs.
; NTH_2_TEST > 100000 iterations: 3.11 secs.
; CADDDRTEST > 100000 iterations: 3.09 secs.
; NTH_3_TEST > 100000 iterations: 3.12 secs.

; -----------------------------------------------------


(defun Cons__Test (itm lst / ) (cons itm lst))
(defun AppendTest (itm lst / ) (append (list itm) lst))

; on small list the difference is small

(timerU '(Cons__Test 0 '(1 2 3)) 100000)
(timerU '(AppendTest 0 '(1 2 3)) 100000)

; CONS__TEST > 100000 iterations: 3.26 secs.
; APPENDTEST > 100000 iterations: 3.45 secs.

; on big list the difference is bigger

(setq i 1 Lst nil Ntimes 10000)
(repeat Ntimes (setq Lst (cons i Lst) i (1+ i)))

(timerU '(Cons__Test 0 Lst) 10000)
(timerU '(AppendTest 0 Lst) 10000)

; CONS__TEST > 10000 iterations: 0.29 secs.
; APPENDTEST > 10000 iterations: 17.5 secs.

;|
Reply From: Tony Tanzillo
Date: Jan/01/05 - 12:41 (GMT)

Re: a zero length list?

Sorry, but I fail to see your point. Nil _is_ the value
of the CDR of the last element of every list with the
exception of 'dotted lists' (simply because every normal
list is terminated by nil - while dotted lists are terminated
by the last element).

When you create a list, you can do it using either of
the following two basic semantic conventions, the
first and most common one being 'short-hand' for the
second:

(setq mylist '(1 2 3))

(setq mylist '(1 2 3 . NIL))

So in reality (and what the PRINT function hides
from you), is the real composition of a normal or
'non-dotted' list:

(1 2 3 . NIL)

Which (print) displays as simply

(1 2 3)

Given that, I fail to see any relevance between the
use of NIL to terminate a list (the result of CDR), and
what NTH should do when its given an invalid index.

I don't see any point to debating a fundamental and
widely accepted principles of software engineering and
language/api design, such as this question. In that
sense, you would find yourself in the minority, especially
when you consider that it isn't a language-specific issue.

So, I see no legitimate reason for NTH to return anything
but an error if its given an invalid index. I also see no
relevance between that and the result of CDR or its
derivatives.

 

Maybe this is a better test:

(defun Car___Test (val / ) (repeat 100000 (car val)))
(defun Nth_0_Test (val / ) (repeat 100000 (nth 0 val)))
(defun Cadr__Test (val / ) (repeat 100000 (cadr val)))
(defun Nth_1_Test (val / ) (repeat 100000 (nth 1 val)))
(defun Caddr_Test (val / ) (repeat 100000 (caddr val)))
(defun Nth_2_Test (val / ) (repeat 100000 (nth 2 val)))
(defun CadddrTest (val / ) (repeat 100000 (cadddr val)))
(defun Nth_3_Test (val / ) (repeat 100000 (nth 3 val)))

(timerU '(Car___Test '(0 1 2 3)) 10)
(timerU '(Nth_0_Test '(0 1 2 3)) 10)
(timerU '(Cadr__Test '(0 1 2 3)) 10)
(timerU '(Nth_1_Test '(0 1 2 3)) 10)
(timerU '(Caddr_Test '(0 1 2 3)) 10)
(timerU '(Nth_2_Test '(0 1 2 3)) 10)
(timerU '(CadddrTest '(0 1 2 3)) 10)
(timerU '(Nth_3_Test '(0 1 2 3)) 10)

; CAR___TEST > 10 iterations: 0.64 secs.
; NTH_0_TEST > 10 iterations: 1.03 secs.
; CADR__TEST > 10 iterations: 0.92 secs.
; NTH_1_TEST > 10 iterations: 1.06 secs.
; CADDR_TEST > 10 iterations: 0.66 secs.
; NTH_2_TEST > 10 iterations: 1.05 secs.
; CADDDRTEST > 10 iterations: 0.68 secs.
; NTH_3_TEST > 10 iterations: 1.1 secs.

; It is interesting to notice that cadr is always
; slower of car-caddr-cadddr, why?

--

Marc'Antonio Alessi
http://xoomer.virgilio.it/alessi
(strcat "NOT a " (substr (ver) 8 4) " guru.")

--

 

While perfectly valid, that comparison overlooks
one key advantage CxR functions have over NTH,
which is their ability to access nested list elements
in a single call, where mutliple calls to NTH would
otherwise be required.

Command: (setq alist '(a (b c (d e) f) g))
(A (B C (D E) F) G)

Command: (cadadr alist)
C

Command: (nth 1 (nth 1 alist))
C

Of course, you could always make a recursive
nth to do it, but that's still isn't a single built-in
function call:

(defun deep-nth (index alist)
(cond
( (not index) alist)
(t (deep-nth
(cdr index)
(nth (car index) alist)
)
)
)
)

Command: (deep-nth '(1 1) alist)
C

Or what no single CxR function call can do:

Command: (setq alist '(A B C (D E (F G H) I) J))
(A B C (D E (F G H) I) J)

Command: (deep-nth '(3 2 1) alist)
G

 

Wouldn't that depend on the list?

Example:
(setq myList '(1 2 3))

I think that the following is more sensible.

(list (car myList) (cadr myList))

than

(reverse (cdr (reverse myList)))

 

Yes. Append has to copy its argument(s) except the last one on every
call, so it generates garbage proportional to the second power of the
length of the list. On small lists this won't matter much: for
100-element list we are talking about 1100 versus 6000 cons cells,
for 1000 elements it would be about 11000 versus 510000 cons cells.
(for a little test program I ran in an interpreter; compiled code
would produce less garbage)

Given that building the new list is easiest done in AutoLisp with cons +
reverse, these should be almost the same.

Here append would copy the list once, the reverses twice. Most effective
would be to change the logic so that wou could add the new item to the
start of the list, not to the end, so you could use cons.

--

 

And might it depend on the LENGTH of the list? If an earlier post on
another thread was correct that you can only use up to four a's and d's
between the c and the r, then I would think (nth 45 ...) on a 63-item list
would be the only way to go.

 

Thanks Tony,

always very interesting your participations.


Cheers.

Marco

 

(nth 45 ...) on a 63-item list

Kent, certainly you'd need to use nth in that case. But the related
discussion on zero length lists got me thinking about this. Why would you
ever need to access that specific element of that long a list?

In processing a very long list, you'd generally use a foreach, or some kind
of recursion to keep stripping off the car, then dealing with the cdr, until
nothing was left. If an "index" identifying a particular piece of data was
needed, you'd use an association list, so that the group code was tied to
the data regardless of the order of the list. I couldn't think of a scenario
where I'd need or want to use an (nth 45 ...). Just wondering if you had
anything particular in mind.

 

Consider an ASCII file read and stored as a list
of strings (not uncommon). Or a list of layers,
list of blocks, list of values coming from a dialog
box etc ...

 

Consider an ASCII file read and stored as a list

Thanks. I've done this in simple cases, like the return from a dialog box,
where I might have an order-dependent list of maybe a dozen items. (Usually
I end up wishing I'd set it up as an association list instead.) And I can
see that if you're processing an ordered ASCII file that way, you'd want to
be able to retrieve the nth string in the list, for instance if that
represented the 45th sentence in a paragraph.

But I was really questioning the sheer magnitude of the list -- to scale it
up an order, when would you need to identify the 450th element of a 630-item
list? If my dialog box return had more than about a dozen items, it would
become a nightmare, I think, to keep track of what the nth element was
supposed to mean.

As far as lists of layers, blocks, and so forth, what might you be doing
with the list that would hinge on the index of an item? In other words, why
wouldn't you use foreach to do whatever you intended with the list? Just
asking.

 

Hi Tom. I was just responding to the "I couldn't think
of a scenario ..." statement. To full circle back to the
original poster, I use nth when I'm interested in an item
that is not associated with a key, cannot be extracted
using member or when it produces code that is far easier to
understand or assemble than equivalent car / cdr combinations.

 

To put into perspective the frequency of use ...

In a source file with 18965 lines of code there were
29 nth calls, 258 car calls and 242 cdr calls.

 

... I use nth when I'm interested in an item

Me too. Car and cdr a cinch, I'll use a c**r when it's clear to me, and
caddr to get the z coordinate of a point, but I don't think I've ever used a
four-level c****r. Makes my head hurt!

 

I think the most convoluted I use is probably cdadr
for xdata, but said use is not that frequent. Gotta
get back to work; cheers.

 

Thanks to all who contributed here. This helps.

James