I wrote two recursive versions of a function that takes a list, an
index and an empty list and returns three values:
1. The list of elements before the element at the given index
2. The element at the given index
3. The rest of the list after the given index
For example, (test1 '(a b c d e f) 3 nil) would return
(A B C)
D
(E F)
The functions are:
(defUn test1 (lst ind bef)
(cond ((null lst) (values (reverse bef) nil (cdr lst)))
((= ind 0) (values (reverse bef) (car lst) (cdr lst)))
(t (test1 (cdr lst) (- ind 1) (cons (car lst) bef)))))
(defUn test2 (lst ind bef)
(cond ((null lst) (values bef nil (cdr lst)))
((= ind 0) (values bef (car lst) (cdr lst)))
(t (test2 (cdr lst) (- ind 1) (append bef (list (car
lst)))))))
1. I wonder if it is better to cons elements as I do in test1 and then
reverse the list before returning it or use append as in test2 and
construct the list in proper order?
2. How expensive is to call the length function on a list of elements?
My theory is that the length of the list is stored somewhere
internally and the length function accesses it somehow. In other
words, I do not think length actually counts the list elements... Am I
right?
····@yandex.ru (Tyro) writes:
> I wrote two recursive versions of a function that takes a list, an
> index and an empty list and returns three values:
> 1. The list of elements before the element at the given index
> 2. The element at the given index
> 3. The rest of the list after the given index
>
> For example, (test1 '(a b c d e f) 3 nil) would return
> (A B C)
> D
> (E F)
>
> The functions are:
> (defUn test1 (lst ind bef)
> (cond ((null lst) (values (reverse bef) nil (cdr lst)))
> ((= ind 0) (values (reverse bef) (car lst) (cdr lst)))
> (t (test1 (cdr lst) (- ind 1) (cons (car lst) bef)))))
>
> (defUn test2 (lst ind bef)
> (cond ((null lst) (values bef nil (cdr lst)))
> ((= ind 0) (values bef (car lst) (cdr lst)))
> (t (test2 (cdr lst) (- ind 1) (append bef (list (car
> lst)))))))
>
> 1. I wonder if it is better to cons elements as I do in test1 and then
> reverse the list before returning it or use append as in test2 and
> construct the list in proper order?
*NEVER* use APPEND like that. It turns your linear process into an
N^2 process. (try your test on a list with several thousand elements).
> 2. How expensive is to call the length function on a list of elements?
O(n) in the number of elements.
> My theory is that the length of the list is stored somewhere
> internally and the length function accesses it somehow.
Nice theory. How does it handle random mutation in the middle of a
list? What about circular lists?
> In other words, I do not think length actually counts the list
> elements... Am I right?
The easiest way to test this is to time how long it takes to find
the length of a list.
From: Christopher C. Stacy
Subject: Re: Newbie: reverse or append?
Date:
Message-ID: <ud6bi2ebn.fsf@dtpq.com>
>>>>> On 24 Nov 2003 02:20:26 -0800, Tyro ("Tyro") writes:
Tyro> 1. I wonder if it is better to cons elements as I do in test1 and then
Tyro> reverse the list before returning it or use append as in test2 and
Tyro> construct the list in proper order?
Draw a picture to work out what would happen to all the CONS cells
using the two techniques, and see which one would be more efficient.
REVERSE is usually implemented as efficiently as it can be.
Tyro> 2. How expensive is to call the length function on a list of elements?
It counts them by going down the list. You should read about a data
structure called a "linked list", which is not specific to Lisp.
······@dtpq.com (Christopher C. Stacy) wrote in message news:<·············@dtpq.com>...
> >>>>> On 24 Nov 2003 02:20:26 -0800, Tyro ("Tyro") writes:
> Tyro> 1. I wonder if it is better to cons elements as I do in test1 and then
> Tyro> reverse the list before returning it or use append as in test2 and
> Tyro> construct the list in proper order?
>
> Draw a picture to work out what would happen to all the CONS cells
> using the two techniques, and see which one would be more efficient.
> REVERSE is usually implemented as efficiently as it can be.
And you can often replace it with the destructive NREVERSE,
particuarly in cases where your code just consed up the list, so it is
obvious by inspection that nothing else in the program has references
to pieces of the list.
It seems to me that you are trying to program in Scheme instead of
Common Lisp. ;)
Here is a version of what you are trying to do using Common Lisp's LOOP
facility:
(defun test3 (list index)
(loop with at
for element in list
for i = 0 then (1+ i)
if (< i index) collect element into before
else if (= i index) do (setf at element)
else if (> i index) collect element into after
finally return (values before at after)))
If you think that this is too "unlispy", check out
http://www.tfeb.org/lisp/hax.html#COLLECTING
Pascal
Tyro wrote:
> I wrote two recursive versions of a function that takes a list, an
> index and an empty list and returns three values:
> 1. The list of elements before the element at the given index
> 2. The element at the given index
> 3. The rest of the list after the given index
>
> For example, (test1 '(a b c d e f) 3 nil) would return
> (A B C)
> D
> (E F)
>
> The functions are:
> (defUn test1 (lst ind bef)
> (cond ((null lst) (values (reverse bef) nil (cdr lst)))
> ((= ind 0) (values (reverse bef) (car lst) (cdr lst)))
> (t (test1 (cdr lst) (- ind 1) (cons (car lst) bef)))))
>
> (defUn test2 (lst ind bef)
> (cond ((null lst) (values bef nil (cdr lst)))
> ((= ind 0) (values bef (car lst) (cdr lst)))
> (t (test2 (cdr lst) (- ind 1) (append bef (list (car
> lst)))))))
>
> 1. I wonder if it is better to cons elements as I do in test1 and then
> reverse the list before returning it or use append as in test2 and
> construct the list in proper order?
>
> 2. How expensive is to call the length function on a list of elements?
> My theory is that the length of the list is stored somewhere
> internally and the length function accesses it somehow. In other
> words, I do not think length actually counts the list elements... Am I
> right?
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
Pascal Costanza <········@web.de> wrote in message news:<···········@newsreader3.netcologne.de>...
> It seems to me that you are trying to program in Scheme instead of
> Common Lisp. ;)
>
> Here is a version of what you are trying to do using Common Lisp's LOOP
> facility:
>
> (defun test3 (list index)
> (loop with at
> for element in list
> for i = 0 then (1+ i)
> if (< i index) collect element into before
> else if (= i index) do (setf at element)
> else if (> i index) collect element into after
> finally return (values before at after)))
>
> If you think that this is too "unlispy", check out
> http://www.tfeb.org/lisp/hax.html#COLLECTING
>
>
> Pascal
>
> Tyro wrote:
> > I wrote two recursive versions of a function that takes a list, an
> > index and an empty list and returns three values:
> > 1. The list of elements before the element at the given index
> > 2. The element at the given index
> > 3. The rest of the list after the given index
> >
> > For example, (test1 '(a b c d e f) 3 nil) would return
> > (A B C)
> > D
> > (E F)
> >
> > The functions are:
> > (defUn test1 (lst ind bef)
> > (cond ((null lst) (values (reverse bef) nil (cdr lst)))
> > ((= ind 0) (values (reverse bef) (car lst) (cdr lst)))
> > (t (test1 (cdr lst) (- ind 1) (cons (car lst) bef)))))
> >
> > (defUn test2 (lst ind bef)
> > (cond ((null lst) (values bef nil (cdr lst)))
> > ((= ind 0) (values bef (car lst) (cdr lst)))
> > (t (test2 (cdr lst) (- ind 1) (append bef (list (car
> > lst)))))))
> >
> > 1. I wonder if it is better to cons elements as I do in test1 and then
> > reverse the list before returning it or use append as in test2 and
> > construct the list in proper order?
> >
> > 2. How expensive is to call the length function on a list of elements?
> > My theory is that the length of the list is stored somewhere
> > internally and the length function accesses it somehow. In other
> > words, I do not think length actually counts the list elements... Am I
> > right?
Actually, you are quite right. I do come from the realm of Scheme... ;-)
····@yandex.ru (Tyro) writes:
> I wrote two recursive versions of a function that takes a list, an
> index and an empty list and returns three values:
> 1. The list of elements before the element at the given index
> 2. The element at the given index
> 3. The rest of the list after the given index
>
> For example, (test1 '(a b c d e f) 3 nil) would return
> (A B C)
> D
> (E F)
>
> The functions are:
> (defUn test1 (lst ind bef)
> (cond ((null lst) (values (reverse bef) nil (cdr lst)))
> ((= ind 0) (values (reverse bef) (car lst) (cdr lst)))
> (t (test1 (cdr lst) (- ind 1) (cons (car lst) bef)))))
>
> (defUn test2 (lst ind bef)
> (cond ((null lst) (values bef nil (cdr lst)))
> ((= ind 0) (values bef (car lst) (cdr lst)))
> (t (test2 (cdr lst) (- ind 1) (append bef (list (car
> lst)))))))
Adam Warner gave a version similar in spirit to this (using SUBSEQ)
but, hey, who can give up a chance to use LDIFF. This is still open to
optimization since it has to walk down INDEX cons cells twice--once in
NTHCDR and again in LDIFF. But it is as efficient as the versions that
build up the list and then destructively reverse it. (I.e. it has to
follow the same number of CDRs and cons as many new cons cells.) If
you meditate a bit on why this is so, you may achieve some small
amount of enlightement.
(defun split-list (list index)
(let ((split-at (nthcdr index list)))
(values (ldiff list split-at)
(car split-at)
(cdr split-at))))
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel <·····@javamonkey.com> writes:
> Adam Warner gave a version similar in spirit to this (using SUBSEQ)
> but, hey, who can give up a chance to use LDIFF. This is still open to
> optimization since it has to walk down INDEX cons cells twice--once in
> NTHCDR and again in LDIFF. But it is as efficient as the versions that
> build up the list and then destructively reverse it. (I.e. it has to
> follow the same number of CDRs and cons as many new cons cells.)
Er, unless of course LDIFF itself is implemented using the
cons-up-a-list-and-reverse it idiom.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Hi Tyro,
> I wrote two recursive versions of a function that takes a list, an
> index and an empty list and returns three values:
> 1. The list of elements before the element at the given index
> 2. The element at the given index
> 3. The rest of the list after the given index
>
> For example, (test1 '(a b c d e f) 3 nil) would return
> (A B C)
> D
> (E F)
Note that '(a b c d e f) is a list literal and cannot be destructively
modified in a portable manner.
Your major cost is list traversal. You want to be able to leverage a
pointer into the list.
[a|-]->[b|-]->[c|-]->[d|-]->[e|-]->[f|nil]
^
If you can establish a pointer here then it will be
cheap to obtain the car of the list to return the
second value and the cdr of the list to return the
third value.
I'd suggest the first value could be copied using subseq. Putting it
together:
(defun split (list i)
(let ((right (nthcdr i list)))
(values (subseq list 0 i) (car right) (cdr right))))
We might improve the efficiency in a native code compiling implementation
using a dedicated function to return two values (the problem with subseq
in this case is that it is throwing away information we need to avoiding
have to traverse part of the the list again). We want to reuse the pointer
after the left list traversal. Here's a function which will give us this
information:
(defun split-list (list index)
(let (left)
(dotimes (i index)
(push (car list) left)
(setf list (cdr list)))
(values (nreverse left) list)))
We can now write a split2 as:
(defun split2 (list i)
(multiple-value-bind (left right) (split-list list i)
(values left (car right) (cdr right))))
While your recursive versions are neat they expose an unnecessary issue as
part of the interface, i.e. you shouldn't have to supply an empty list as
one of the input terms. This should be handled internally in your function.
You could use &optional to obscure this, i.e.:
(defun test1 (lst ind &optional bef)
(cond ((null lst) (values (reverse bef) nil (cdr lst)))
((= ind 0) (values (reverse bef) (car lst) (cdr lst)))
(t (test1 (cdr lst) (- ind 1) (cons (car lst) bef)))))
Now you're able to evaluate (test1 '(a b c d e f) 3).
> 1. I wonder if it is better to cons elements as I do in test1 and then
> reverse the list before returning it or use append as in test2 and
> construct the list in proper order?
When you have to construct a new list you're better in general to push the
values on and destructively nreverse the list at the end. append becomes
increasingly slower as the length of the list increases. pushing values
onto a list (which naturally results in a reversed order) has a constant
cost.
> 2. How expensive is to call the length function on a list of elements?
> My theory is that the length of the list is stored somewhere
> internally and the length function accesses it somehow. In other
> words, I do not think length actually counts the list elements... Am I
> right?
To convince yourself that length traverses a list to count its elements
check out this disassembly:
* (disassemble (lambda (list)
(declare (list list) (optimize (speed 3) (safety 0)))
(length list)))
48086AA8: .entry "lambda (list)"(list) ; (function (list) (mod 536870911))
C0: pop dword ptr [ebp-8]
C3: lea esp, [ebp-32]
C6: xor eax, eax ; No-arg-parsing entry point
C8: cmp edx, #x2800000B ; nil
CE: jeq L1
D0: L0: mov edx, [edx+1]
D3: add eax, 4
D6: cmp edx, #x2800000B ; nil
DC: jne L0
DE: L1: mov edx, eax
E0: mov ecx, [ebp-8]
E3: mov eax, [ebp-4]
E6: add ecx, 2
E9: mov esp, ebp
EB: mov ebp, eax
ED: jmp ecx
EF: nop
xor eax,eax is a cheap way to zero the register eax. edx is being compared
to the address location of nil to locate the end of the list. If this is
found then we jump to L1 where the length of the list is returned.
Otherwise we drop through to L0 and obtain the pointer to the next cons.
eax is incremented by 4 because of the low order tag bits. If the pointer
to the next cons turns to be nil then we drop through to returning the
length of the list. Otherwise the process repeats until the end of the
list is found.
The length of the list is not stored somewhere internally and it would be
very inefficient in general to attempt to maintain this information at
all times.
Regards,
Adam