I have a list of data that I'm going to need to remove elements from,
and select elements from randomly. I am wondering the array functions
in common lisp would be more effective (in terms of execution time)
then using remove to remove and creating a loop that takes the car if
iterations has reached the random number, and recursively calls itself
on the cdr with a greater value of iterations otherwise. Coding
complexity is not an issue.
Thanks in advance.
On 2006-10-29 22:22:52 -0500, ·················@gmail.com"
<················@gmail.com> said:
> I have a list of data that I'm going to need to remove elements from,
> and select elements from randomly. I am wondering the array functions
> in common lisp would be more effective (in terms of execution time)
> then using remove to remove and creating a loop that takes the car if
> iterations has reached the random number, and recursively calls itself
> on the cdr with a greater value of iterations otherwise. Coding
> complexity is not an issue.
Also consider a hash table if you really need to remove items.
················@gmail.com <················@gmail.com> wrote:
+---------------
| I have a list of data that I'm going to need to remove elements from,
| and select elements from randomly. I am wondering the array functions
| in common lisp would be more effective (in terms of execution time)
| then using remove to remove and creating a loop that takes the car if
| iterations has reached the random number, and recursively calls itself
| on the cdr with a greater value of iterations otherwise.
+---------------
Probably *way* more efficient than the list-based algorithm you're
describing. Here's one quick & dirty way of doing it with arrays:
> (defun randomize-list (list)
(loop with vector = (coerce list 'vector)
for limit from (length vector) downto 1
for index = (random limit)
for item = (aref vector index)
do (setf (aref vector index) (aref vector (1- limit)))
collect item))
RANDOMIZE-LIST
cmu> (defvar *data* '(0 1 2 3 4 5 6 7 8 9 foo bar baz gorp quux))
*DATA*
cmu> (randomize-list *data*)
(6 5 BAZ 1 8 BAR 0 2 3 9 FOO 4 QUUX 7 GORP)
cmu> (randomize-list *data*)
(FOO 4 2 5 BAZ 6 BAR 3 GORP 1 0 8 9 QUUX 7)
cmu> (randomize-list *data*)
(0 1 6 GORP 7 QUUX 9 FOO BAR BAZ 2 3 4 8 5)
cmu>
>
For extra credit... ;-}
1. The above does unneeded work in some cases. Remove them.
2. Shuffle the vector in-place, and return the vector instead of a list.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Giorgos Keramidas
Subject: Re: Efficiency of arrays in LISP
Date:
Message-ID: <87mz6xqu5v.fsf@kobe.laptop>
On Sun, 29 Oct 2006 23:35:08 -0600, ····@rpw3.org (Rob Warnock) wrote:
> ················@gmail.com <················@gmail.com> wrote:
> +---------------
> | I have a list of data that I'm going to need to remove elements from,
> | and select elements from randomly. I am wondering the array functions
> | in common lisp would be more effective (in terms of execution time)
> | then using remove to remove and creating a loop that takes the car if
> | iterations has reached the random number, and recursively calls itself
> | on the cdr with a greater value of iterations otherwise.
> +---------------
>
> Probably *way* more efficient than the list-based algorithm you're
> describing. Here's one quick & dirty way of doing it with arrays:
>
> > (defun randomize-list (list)
> (loop with vector = (coerce list 'vector)
> for limit from (length vector) downto 1
> for index = (random limit)
> for item = (aref vector index)
> do (setf (aref vector index) (aref vector (1- limit)))
> collect item))
> RANDOMIZE-LIST
> cmu> (defvar *data* '(0 1 2 3 4 5 6 7 8 9 foo bar baz gorp quux))
>
> *DATA*
> cmu> (randomize-list *data*)
>
> (6 5 BAZ 1 8 BAR 0 2 3 9 FOO 4 QUUX 7 GORP)
> cmu> (randomize-list *data*)
>
> (FOO 4 2 5 BAZ 6 BAR 3 GORP 1 0 8 9 QUUX 7)
> cmu> (randomize-list *data*)
>
> (0 1 6 GORP 7 QUUX 9 FOO BAR BAZ 2 3 4 8 5)
> cmu>
> >
>
> For extra credit... ;-}
>
> 1. The above does unneeded work in some cases. Remove them.
>
> 2. Shuffle the vector in-place, and return the vector instead of a list.
Would something like the following be considered a 'good' way to do
this?
% CL-USER> (defun randomize-vector (vec)
% (let ((vector-size (length vec)))
% (loop for index below vector-size
% do (let ((random (random vector-size)))
% (let ((alpha (aref vec index))
% (beta (aref vec random)))
% (setf (aref vec index) beta)
% (setf (aref vec random) alpha)))
% finally (return vec))))
% CL-USER> (defparameter *data* #(0 1 2 3 4 5 6 7 8 9))
% *DATA*
% CL-USER> (randomize-vector *data*)
% #(9 0 5 8 7 6 3 4 2 1)
% CL-USER>
I am not sure I like the double (aref vec ...) for each element, but I
couldn't find a good way of doing the same without saving the values of
`alpha' and `beta' before doing the actual assignment to vector
elements.
Giorgos Keramidas <········@ceid.upatras.gr> writes:
> On Sun, 29 Oct 2006 23:35:08 -0600, ····@rpw3.org (Rob Warnock) wrote:
> > ················@gmail.com <················@gmail.com> wrote:
> > +---------------
> > | I have a list of data that I'm going to need to remove elements from,
> > | and select elements from randomly. I am wondering the array functions
> > | in common lisp would be more effective (in terms of execution time)
> > | then using remove to remove and creating a loop that takes the car if
> > | iterations has reached the random number, and recursively calls itself
> > | on the cdr with a greater value of iterations otherwise.
> > +---------------
> >
> > Probably *way* more efficient than the list-based algorithm you're
> > describing. Here's one quick & dirty way of doing it with arrays:
> >
> > > (defun randomize-list (list)
> > (loop with vector = (coerce list 'vector)
> > for limit from (length vector) downto 1
> > for index = (random limit)
> > for item = (aref vector index)
> > do (setf (aref vector index) (aref vector (1- limit)))
> > collect item))
> > RANDOMIZE-LIST
> > cmu> (defvar *data* '(0 1 2 3 4 5 6 7 8 9 foo bar baz gorp quux))
> >
> > *DATA*
> > cmu> (randomize-list *data*)
> >
> > (6 5 BAZ 1 8 BAR 0 2 3 9 FOO 4 QUUX 7 GORP)
> > cmu> (randomize-list *data*)
> >
> > (FOO 4 2 5 BAZ 6 BAR 3 GORP 1 0 8 9 QUUX 7)
> > cmu> (randomize-list *data*)
> >
> > (0 1 6 GORP 7 QUUX 9 FOO BAR BAZ 2 3 4 8 5)
> > cmu>
> > >
> >
> > For extra credit... ;-}
> >
> > 1. The above does unneeded work in some cases. Remove them.
> >
> > 2. Shuffle the vector in-place, and return the vector instead of a list.
>
> Would something like the following be considered a 'good' way to do
> this?
>
> % CL-USER> (defun randomize-vector (vec)
> % (let ((vector-size (length vec)))
> % (loop for index below vector-size
> % do (let ((random (random vector-size)))
> % (let ((alpha (aref vec index))
> % (beta (aref vec random)))
> % (setf (aref vec index) beta)
> % (setf (aref vec random) alpha)))
> % finally (return vec))))
> % CL-USER> (defparameter *data* #(0 1 2 3 4 5 6 7 8 9))
> % *DATA*
> % CL-USER> (randomize-vector *data*)
> % #(9 0 5 8 7 6 3 4 2 1)
> % CL-USER>
>
> I am not sure I like the double (aref vec ...) for each element, but I
> couldn't find a good way of doing the same without saving the values of
> `alpha' and `beta' before doing the actual assignment to vector
> elements.
Try rotatef. Also, since you're using loop anyway you could use for random = bla
etc. instead of the lets. Maybe more importantly, from a cursory glance I
think your algorithm is broken (i.e. the chance of item i eventually becoming
j is not constant).
'as
On 2006-11-12 03:24:12 +0100, Giorgos Keramidas
<········@ceid.upatras.gr> said:
> Would something like the following be considered a 'good' way to do
> this?
>
> % CL-USER> (defun randomize-vector (vec)
> % (let ((vector-size (length vec)))
> % (loop for index below vector-size
> % do (let ((random (random vector-size)))
> % (let ((alpha (aref vec index))
> % (beta (aref vec random)))
> % (setf (aref vec index) beta)
> % (setf (aref vec random) alpha)))
> % finally (return vec))))
> % CL-USER> (defparameter *data* #(0 1 2 3 4 5 6 7 8 9))
> % *DATA*
> % CL-USER> (randomize-vector *data*)
> % #(9 0 5 8 7 6 3 4 2 1)
> % CL-USER>
>
> I am not sure I like the double (aref vec ...) for each element, but I
> couldn't find a good way of doing the same without saving the values of
> `alpha' and `beta' before doing the actual assignment to vector
> elements.
rotatef?
(defun randomize-vector (vec)
(let ((vector-size (length vec)))
(loop for index below vector-size
do (rotatef (aref vec index)
(aref vec (random vector-size)))
finally (return vec))))
Michal
From: Giorgos Keramidas
Subject: Re: Efficiency of arrays in LISP
Date:
Message-ID: <87bqnc6uyk.fsf@kobe.laptop>
On Sun, 12 Nov 2006 16:28:00 +0100, Michal Krupka <·······@mac.com> wrote:
>On 2006-11-12 03:24:12 +0100, Giorgos Keramidas
><········@ceid.upatras.gr> said:
>> Would something like the following be considered a 'good' way to do
>> this?
>>
>> % CL-USER> (defun randomize-vector (vec)
>> % (let ((vector-size (length vec)))
>> % (loop for index below vector-size
>> % do (let ((random (random vector-size)))
>> % (let ((alpha (aref vec index))
>> % (beta (aref vec random)))
>> % (setf (aref vec index) beta)
>> % (setf (aref vec random) alpha)))
>> % finally (return vec))))
>> % CL-USER> (defparameter *data* #(0 1 2 3 4 5 6 7 8 9))
>> % *DATA*
>> % CL-USER> (randomize-vector *data*)
>> % #(9 0 5 8 7 6 3 4 2 1)
>> % CL-USER>
>>
>> I am not sure I like the double (aref vec ...) for each element, but I
>> couldn't find a good way of doing the same without saving the values of
>> `alpha' and `beta' before doing the actual assignment to vector
>> elements.
>
> rotatef?
>
> (defun randomize-vector (vec)
> (let ((vector-size (length vec)))
> (loop for index below vector-size
> do (rotatef (aref vec index)
> (aref vec (random vector-size)))
> finally (return vec))))
Excellent! This is exactly the piece I was missing. Thank you :)
In article <························@m7g2000cwm.googlegroups.com>,
·················@gmail.com" <················@gmail.com> wrote:
> I have a list of data that I'm going to need to remove elements from,
> and select elements from randomly. I am wondering the array functions
> in common lisp would be more effective (in terms of execution time)
> then using remove to remove and creating a loop that takes the car if
> iterations has reached the random number, and recursively calls itself
> on the cdr with a greater value of iterations otherwise. Coding
> complexity is not an issue.
Arrays tend to be more efficient than lists if you need to do lots of
random access, but don't need to insert/remove very often. The latter
operations require shifting all the following entries up/down.
Lists are efficient for sequential access and inserting/deleting,
because these can be done simply by updating a couple of CDR slots.
There's not really a single data structure that's likely to be optimal
for all operations. That's why we have several different collection
types -- you get to choose which one fits your needs best.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Actually I had a similar more newbie - ish question relating to
SBCL/CMUCL: when passing small tuples (vectors, matrices for 3d and 2d
around) a lot - which is more efficent, small arrays, a struct or
multiple-values?
My guess was multiple values for the 2-3-4 tuples (they live in
registors or on the stack, don't they?) and small arrays of single
floats for the 9-16 tuples (matrices)..
I guess I should DISSASEMBLE and find out, rather than be lazy and ask
the group. Although the group might know of implementation gotchas that
I don't
On Oct 30, 3:22 am, ·················@gmail.com"
<················@gmail.com> wrote:
> I have a list of data that I'm going to need to remove elements from,
> and select elements from randomly. I am wondering the array functions
> in common lisp would be more effective (in terms of execution time)
> then using remove to remove and creating a loop that takes the car if
> iterations has reached the random number, and recursively calls itself
> on the cdr with a greater value of iterations otherwise. Coding
> complexity is not an issue.
>
> Thanks in advance.
JohnFredCee wrote:
> Actually I had a similar more newbie - ish question relating to
> SBCL/CMUCL: when passing small tuples (vectors, matrices for 3d and 2d
> around) a lot - which is more efficent, small arrays, a struct or
> multiple-values?
>
> My guess was multiple values for the 2-3-4 tuples (they live in
> registors or on the stack, don't they?) and small arrays of single
> floats for the 9-16 tuples (matrices)..
>
> I guess I should DISSASEMBLE and find out, rather than be lazy and ask
> the group. Although the group might know of implementation gotchas that
> I don't
I would expect multiple-values assuming that 1. you're not capturing
them with MULTIPLE-VALUE-LIST 2. the function providing them is
inlined.
If the function is not inlined, and the values are eg. double-floats,
every one is going to get heap-allocated separately, in which case it
_might_ be faster to allocate a specialized array and store them there.
No way to know without profiling, though.
Cheers,
-- Nikodemus Siivola
·········@random-state.net wrote:
> JohnFredCee wrote:
> > Actually I had a similar more newbie - ish question relating to
> > SBCL/CMUCL: when passing small tuples (vectors, matrices for 3d and 2d
> > around) a lot - which is more efficent, small arrays, a struct or
> > multiple-values?
> >
> > My guess was multiple values for the 2-3-4 tuples (they live in
> > registors or on the stack, don't they?) and small arrays of single
> > floats for the 9-16 tuples (matrices)..
> >
> > I guess I should DISSASEMBLE and find out, rather than be lazy and ask
> > the group. Although the group might know of implementation gotchas that
> > I don't
>
> I would expect multiple-values assuming that 1. you're not capturing
> them with MULTIPLE-VALUE-LIST 2. the function providing them is
> inlined.
>
> If the function is not inlined, and the values are eg. double-floats,
> every one is going to get heap-allocated separately, in which case it
> _might_ be faster to allocate a specialized array and store them there.
> No way to know without profiling, though.
>
> Cheers,
>
> -- Nikodemus Siivola
So, with a couple of hours to spare I came up with this monster: a set
of macros
that generate macros. I bailed when I realised that to give it a nice
frontend with
a simple declarative form per tuple-type I was going to have to write a
macro
that created a macro that created a macro..is there any simpler way of
doing this?
;; make #{ .. } notation become a short hand for (values ...)
(defun |#{-reader| (stream char arg)
(declare (ignore char arg))
`(values ,@(read-delimited-list #\} stream t)))
(set-dispatch-macro-character #\# #\{ #'|#{-reader|)
(set-macro-character #\} (get-macro-character #\) nil))
(defmacro make-tuple-struct (&key type-name tuple-type
tuple-default-value elements)
"Create a structure in the form needed for tuple / packing
unpacking. All fields should have the same type and default value."
`(defstruct ,type-name
,@(loop
for element in elements
collect (list element tuple-default-value :type tuple-type))))
;; test code
(make-tuple-struct :type-name vector2d :tuple-type single-float
:tuple-default-value 0.0 :elements (x y))
(make-tuple-struct :type-name vector3d :tuple-type single-float
:tuple-default-value 0.0 :elements (x y z))
(make-tuple-struct :type-name vector4d :tuple-type single-float
:tuple-default-value 0.0 :elements (x y z w))
(make-tuple-struct :type-name quaternion :tuple-type single-float
:tuple-default-value 0.0 :elements (x y z w))
(make-tuple-struct :type-name color :tuple-type single-float
:tuple-default-value 0.0 :elements (r g b a))
(defmacro with-gensyms (syms &body body)
`(let ,(mapcar #'(lambda (s) `(,s (gensym)))
syms)
,@body))
(defmacro make-tuple-unpacker (&key type-name elements)
"Create an unpacker function such as (vector? vector4d) that takes an
instance
of a struct and unpacks it to tuples (aka multiple values)"
(labels
((make-macro-name (type-name)
(intern (concatenate 'string
(symbol-name type-name)
"?")))
(make-element-names (elements)
(mapcar #'(lambda (x)
(find-symbol
(concatenate 'string
(symbol-name type-name) "-"
(symbol-name x))))
elements)))
`(defmacro ,(make-macro-name type-name) (packed-tuple)
(let ((packed-tuple-sym (gensym)))
`(let
((,packed-tuple-sym ,packed-tuple))
(values ,@(loop
for element-name in (quote ,(make-element-names elements))
collect (list element-name packed-tuple-sym))))))))
(make-tuple-unpacker :type-name vector2d :elements (x y))
(make-tuple-unpacker :type-name vector3d :elements (x y z))
(make-tuple-unpacker :type-name vector4d :elements (x y z w))
(make-tuple-unpacker :type-name quaternion :elements (x y z w))
(make-tuple-unpacker :type-name color :elements (r g b a))
(defmacro make-with-tuple (&key type-name)
"Create a macro that can be used to bind members of the tuples
to symbols"
(labels
((make-unpacker-name (type-name)
(intern (concatenate 'string
(symbol-name type-name)
"?")))
(make-macro-name (type-name)
(intern (concatenate 'string
"WITH-"
(symbol-name type-name)))))
`(defmacro ,(make-macro-name type-name) (element-syms tuple
&body forms)
`(multiple-value-bind
,(loop
for element-sym in element-syms
collect element-sym)
(,',(make-unpacker-name type-name) ,tuple)
,@forms))))
(make-with-tuple :type-name vector2d)
(make-with-tuple :type-name vector3d)
(make-with-tuple :type-name vector4d)
(make-with-tuple :type-name quarternion)
(make-with-tuple :type-name color)
(defmacro make-tuple-packer (&key type-name elements)
"Create a tuple-name! macro for packing multiple values into
a tuple struct"
(labels
((make-packer-name (type-name)
(intern (concatenate 'string
(symbol-name type-name)
"!")))
(make-element-names (elements)
(mapcar #'(lambda (x)
(find-symbol
(concatenate 'string
(symbol-name type-name) "-"
(symbol-name x))))
elements)))
`(defmacro ,(make-packer-name type-name) (target-sym tuple-values)
(let* ((element-name-list ',(make-element-names elements))
(varlist (mapcar #'(lambda (x) (gensym (symbol-name x)))
element-name-list)))
`(multiple-value-bind
,(mapcar #'(lambda (x) x) varlist)
,tuple-values
(progn ,@(mapcar #'(lambda (p v) `(setf (,p ,target-sym) ,v))
element-name-list varlist)))))))
·················@gmail.com" <················@gmail.com> writes:
> I have a list of data that I'm going to need to remove elements from,
> and select elements from randomly. I am wondering the array functions
> in common lisp would be more effective (in terms of execution time)
> then using remove to remove and creating a loop that takes the car if
> iterations has reached the random number, and recursively calls itself
> on the cdr with a greater value of iterations otherwise. Coding
> complexity is not an issue.
Ah good. Since coding complexity is not an issue, you might consider
rewriting the Judy algorithm in CL (or writting a FFI to the C
library, but this might be more complex to use).
http://judy.sourceforge.net/
--
__Pascal Bourguignon__ http://www.informatimago.com/
HEALTH WARNING: Care should be taken when lifting this product,
since its mass, and thus its weight, is dependent on its velocity
relative to the user.
················@gmail.com skrev:
> I have a list of data that I'm going to need to remove elements from,
> and select elements from randomly.
Is delete and random-access the only operations needed after
the initial creation?
--
Jens Axel S�gaard