Cookbook question: How to change a list to a vector?
Thaddeus L Olczyk
One thing that you wish to do is replace a list with a vector
since you can see many inefficient operations on the list.
How would one proceed?
Wolfhard Buß
(lambda (list) (make-array (length list) :initial-contents list))
comes to mind, or
(lambda (list) (map 'vector #'identity list))
An experienced Lisper might find a more sophisticated operator to
coerce a list into a vector;)
--
"Das Auto hat keine Zukunft. Ich setze aufs Pferd." Wilhelm II. (1859-1941)
Janis Dzerins
See function coerce.
--
Janis Dzerins
Eat shit -- billions of flies can't be wrong.
Thaddeus L Olczyk
For those who lack common sense: I am not talking about
coercing lists to vectors ( allthough that might be needed ).
Simply coercing will make your application slower not faster.
I am talking about changing the "type" of a variable from
a list to a vector ( ie replacing all list operations with
vector/array operations. In case you still don't get it:
replacing all list operations with *efficient* vector/array
operations. )
Marco Antoniotti
(defvar *l* (list 1 2 3 4))
(coerce *l* 'vector)
Check the CLHS for the constraints on such coercion.
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
Wade Humeniuk
The simplest is to rewrite your code.
However, before I get into trouble I usually define my own accessors for the
type of data I am passing around.
so... for these list type things I would do (if I am really unsure of what
data type to use)
(defun make-my-sequence (dim &key (initial-element nil))
(make-list dim :initial-element initial-element))
(deftype my-sequnce () 'list)
(defun my-sequence-ref (seq ref)
(nth ref seq))
(defun (setf my-sequence-ref) (newval seq ref)
(setf (nth ref seq) newval))
If the internals need to be changed to a array I would just rewrite
make-my-sequence, deftype my-sequence and my-sequence-ref.
This technique takes some fore-thought and is not bullet proof. Loop comes
to mind with loop across and loop in, dolist.... The debugger will catch
them if you miss any in the rewrite. I suppose you could extend loop.
(Never done that).
Another way might be to use defstruct to do
(defstruct (my-sequence (:type list))
...)
and then change it to
(defstruct (my-sequence (:type vector))
...)
Recompile.. But some slots have to be well defined.
Wade
"Thaddeus L Olczyk" <olc...@interaccess.com> wrote in message
news:3c6f3346...@nntp.interaccess.com...
David Hanley
Wow. I think common sense could heve helped you ask the question
properly! You said you wanted to change a list to a vector. Don't
get down on people for answering your question correctly!
many of the built-in list functions work on vectors, as well.
However, it depends on what operations you're doing. Some things
simply work faster on lists.
I wrote a program that needed an ultra-fast version of remove-if. I
ended up keeping a length variable with my vectors, shuffling the
elements that didn't fit to the end of the array, and decrementing the
size appropriately. Very fast, but it requires a logic shift.
dave
Erik Naggum
| Given a system that is running slower than you would like. One thing
| that you wish to do is replace a list with a vector since you can see
| many inefficient operations on the list. How would one proceed?
For what it is worth, I thought your question was quite clear, but the
answer is also quite obvious: you hunt down all the references to the
list and chnage the design to use a vector, instead, but this you knew.
This is quite trivial, however, since the list is more than a "class": a
data structure with methods, it embodies a particular design. In effect,
your question translates to "how much of the design depends on the choice
of the list data structure?" Individual programs differ greatly in this
regard, but the more you have optimized your code for lists, the more
work it will take to change to vectors. However, it is not very common
to use nth to access list elements, and people tend to pass around other
cons cells than the first in the list. This is especially true for those
who suffer from Scheme exposure, who mistakenly believe that recursion on
lists is a good thing. They have to redesign the whole solution to use
another algorithm they are inexperienced with to get better performance.
///
--
In a fight against something, the fight has value, victory has none.
In a fight for something, the fight is a loss, victory merely relief.
Ralf Kleberhoff
David Hanley schrieb:
> ...
> I wrote a program that needed an ultra-fast version of remove-if. I
> ended up keeping a length variable with my vectors, shuffling the
> elements that didn't fit to the end of the array, and decrementing the
> size appropriately. Very fast, but it requires a logic shift.
That's a vector created with a :fill-pointer keyword, isn't it?
--- Ralf
Ralf Kleberhoff
Thaddeus L Olczyk schrieb:
>
> Given a system that is running slower than you would like.
> One thing that you wish to do is replace a list with a vector
> since you can see many inefficient operations on the list.
Did you confirm this with a speed-profiling tool?
> How would one proceed?
From ~15 years of lisp experience, I often saw programmers
speed-optimizing the wrong part of their program...
1) Get yourself a good profiling tool (e.g. the AllegroCL
profiler has helped me a lot with speed issues) to find
out where your program wastes its time.
I was often surprised to find performance bottlenecks
where I never expected them.
2) THEN think about optimizations.
Lists aren't generally less efficient than vectors. That depends
on the access types. Only for real random-access operations,
vectors have clear advantages. And many types of modification are
much more efficient with lists.
--- Ralf