Re: Efficiency of arrays in LISP
- From: rpw3@xxxxxxxx (Rob Warnock)
- Date: Sun, 29 Oct 2006 23:35:08 -0600
robinganemccalla@xxxxxxxxx <robinganemccalla@xxxxxxxxx> 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@xxxxxxxx>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
.
- References:
- Efficiency of arrays in LISP
- From: robinganemccalla@xxxxxxxxx
- Efficiency of arrays in LISP
- Prev by Date: Re: Using "internal" macros of a CL implementation
- Next by Date: Current state of Symbolics
- Previous by thread: Re: Efficiency of arrays in LISP
- Next by thread: Re: Efficiency of arrays in LISP
- Index(es):
Relevant Pages
|
