If I want to put an atom at the end of a list, which is better ?
Suppose,
(setf my-atom 'D)
(setf my-list '(A B C))
I want to return
'(A B C D)
Then this,
(append my-list (list my-atom))
or this,
(reverse (cons my-atom (reverse my-list)))
is better???
comments??
Nikhil Ketkar
From: Pascal Costanza
Subject: Re: If I want to put an atom at the end of a list, which is better ?
Date:
Message-ID: <3d942pF6lieubU1@individual.net>
Nikhil Ketkar wrote:
> If I want to put an atom at the end of a list, which is better ?
>
> Suppose,
> (setf my-atom 'D)
> (setf my-list '(A B C))
>
> I want to return
> '(A B C D)
>
> Then this,
> (append my-list (list my-atom))
>
> or this,
>
> (reverse (cons my-atom (reverse my-list)))
>
> is better???
What do you think which of the two versions traverse my-list more often
than the other?
> comments??
If this is part of a larger problem you may want to try to find a way to
reorganize your algorithm so that the list traversals inherent in append
and reverse are not necessary. Usually, the list that you want to append
to has been created at some other stage, and it may be possible to
arrange the data structure (or the algorithm) to be better "appendable"
later on.
It's (also) usually possible to use the LOOP macro together with COLLECT
to avoid such traversals.
Of course, if efficiency doesn't matter for your problem, you can ignore
this.
Just a note on terminology: You are not appending an atom at the end of
the list. The end of a (proper) list is always NIL. It is indeed
possible to have a list ending in an atom, but then it is not a proper
list. Your wording suggests that you want '(A B C . D) as a result.
(It's good that you have posted an example to clarify what you really want.)
Pascal
--
2nd European Lisp and Scheme Workshop
July 26 - Glasgow, Scotland - co-located with ECOOP 2005
http://lisp-ecoop05.bknr.net/
I really want to write good Lisp code (optimised).
I am getting the feeling that I should actually write a small Lisp
interpreter myself so as to understand the optimization issues.
Would this be the right way to go ?
Thanks,
Nikhil Ketkar
From: André Thieme
Subject: Re: If I want to put an atom at the end of a list, which is better ?
Date:
Message-ID: <d4ntkc$ibf$1@ulric.tng.de>
Nikhil Ketkar schrieb:
> I really want to write good Lisp code (optimised).
> I am getting the feeling that I should actually write a small Lisp
> interpreter myself so as to understand the optimization issues.
> Would this be the right way to go ?
I don't know why writing a Lisp interpreter (in Lisp) will make a you
better Lisp programmer.
Andr�
--
"Nikhil Ketkar" <············@gmail.com> writes:
> I really want to write good Lisp code (optimised).
Define optimised?
What do you want to optimize?
- the time the programmer spends on providing a correct, working program?
- the time the maintainer will understand the code and be able to modify
it to change or add features?
- the time the program will need to run an a small data set?
- the time the program will need to run an a big data set?
- the memory the program will need to run an a small data set?
- the memory the program will need to run an a big data set?
As has explained Matthieu, the times the program will need depends a
lot on the implementation you're using.
Assuming you've answered to Pascal's questions, you should now know that:
(append my-list (list my-atom))
has a space complexity in O(N) (N==(length my-list))
and a time complexity in O(N), while
(reverse (cons my-atom (reverse my-list)))
has a space complexity in O(2N)=O(N)
and a time complexity in O(2N)=O(N).
(nreverse (cons my-atom (nreverse my-list)))
would have a space complexity in O(1) on most implementation, but
could still be O(2N) on other, and a time complexity in O(2N)=O(N).
(nconc my-list (list my-atom))
would have a space complexity in O(1), and a time complexity in O(N),
but you could not apply it if my-list is taken from the source of your
program, eg. if you wrote (setf my-list '(1 2 3)). You'd have to make
sure that my-list mutable: (setf my-list (list 1 2 3)).
Then if you want to optimize more, you should keep a "pointer" to the tail:
(defstruct htlist head tail)
(defun htnull (htl) (null (htlist-head htl)))
(defun htfirst (htl) (car (htlist-head htl)))
(defun htrest (htl) (make-htlist :head (cdr (htlist-head htl))
:tail (when (cdr (htlist-head htl))
(htlist-tail htl))))
(defun htlist (&rest items)
;; this could be "optimized":
(let ((items (copy-list items)))
(make-htlist :head items :tail (last items))))
(defun htenqueue (htl item)
(setf (cdr (htlist-tail htl)) (cons item nil))
(setf (htlist-tail htl) (cdr (htlist-tail htl)))
item)
(defparameter l (htlist 1 2 3))
(htenqueue l 4)
(print l)
Here the space complexity of htenqueue is O(1) and the time
complexityis O(1) but the constants are highter, so if the lists are
small, it might be actually slowwer, but if the lists are big it'll be
faster and less greedy.
> I am getting the feeling that I should actually write a small Lisp
> interpreter myself so as to understand the optimization issues.
What optimization do you mean?
If you want to optimize the run time of the lisp programs, you'll want
to write a compiler, not an interpreter.
If you want to optimize the time between the user pressing RETURN and
the first line of output of a script, you may prefer an intepreter and
you'll want to reduce the working set of this interpreted to lead to
fast loading times, or you'll want to optimize the compilation time,
even if the run time of the script is ten times slower.
> Would this be the right way to go ?
It's very interesting, instructive and exiting to write interpreters
and compilers. But I'm not sure it's the right way to go...
--
__Pascal Bourguignon__ http://www.informatimago.com/
Pascal Costanza wrote:
> If this is part of a larger problem you may want to try to find a
> way to reorganize your algorithm so that the list traversals
> inherent in append and reverse are not necessary. Usually, the
> list that you want to append to has been created at some other
> stage, and it may be possible to arrange the data structure (or
> the algorithm) to be better "appendable" later on.
There was a paper by Waters/Norvig on queues...
http://www.merl.com/papers/TR91-04/
Bunch of other nice papers at http://lisp.tech.coop/Paper