please any comments on this common-lisp code:
(defun remove-nth (a n)
(declare (list a) (fixnum n))
(loop for item in (remove nil
(loop for i of-type fixnum from 0 below (length a) collect
(if (/= i n)
(cons (nth i a) nil))))
collect (car item)))
(defun randomize-list (lst)
(let (l n (len (length lst)))
(loop while (> len 0) do
(setf n (random len))
(push (nth n lst) l) ; copy element
; copy all from list a to list b but nth 'n element
(setf lst (remove-nth lst n))
(decf len))
l))
In article <························@m36g2000hse.googlegroups.com>,
··········@hotmail.com wrote:
> please any comments on this common-lisp code:
>
> (defun remove-nth (a n)
> (declare (list a) (fixnum n))
> (loop for item in (remove nil
> (loop for i of-type fixnum from 0 below (length a) collect
> (if (/= i n)
> (cons (nth i a) nil))))
> collect (car item)))
>
> (defun randomize-list (lst)
> (let (l n (len (length lst)))
> (loop while (> len 0) do
> (setf n (random len))
> (push (nth n lst) l) ; copy element
> ; copy all from list a to list b but nth 'n element
> (setf lst (remove-nth lst n))
> (decf len))
> l))
* documentation?
* what should it do? args? results?
* why did you write it this way?
* example usage?
* who are you?
* is it homework?
--
http://lispm.dyndns.org
Thanks for all the replys. Made an new version from the rotatef
version you suggested.
> * documentation?
> * what should it do? args? results?
Shuffle a list randomly without sideffects.
> * why did you write it this way?
My initial version was made to ensure my mind that the list
was truly randomly shuffled as good as RANDOM can go.
> * example usage?
I'm using this to shuffle the learning data feeded to an neural
network. It is alot of data so it can't be shuffled destructively.
> * who are you?
I'm larry thank you, and you ?
> * is it homework?
No, i'm just no expert in random numbers.
Here is a second try:
(defun randomize-list (lst)
(let ((len (length lst))
(new (copy-list lst)))
(loop for i from 0 below len do
(rotatef (elt new i) (elt new (random len))))
new))
··········@hotmail.com writes:
> Here is a second try:
>
> (defun randomize-list (lst)
> (let ((len (length lst))
> (new (copy-list lst)))
> (loop for i from 0 below len do
> (rotatef (elt new i) (elt new (random len))))
> new))
Slightly better, but:
1- it's still O(n�),
2- it's not equiprobable.
It doesn't give equiprobable results, assuming an equiprobable RANDOM,
because you can rotate twice or more elements below i.
If you insist on processing a list, instead of using a temporary
vector as showed in previous articles, you could write:
(defun shuffle-list (list)
(do* ((list (copy-list list) list)
(length (length list) (1- length))
(current list (cdr list)))
((< 2 length) list)
(rotatef (first current) (elt current (random length)))))
It would give correct results. It is still O(n�), but with better
constants. For very short lists, it might be quicker than converting
to and from a vector, but soon enough it should be slower.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
Pascal Bourguignon <···@informatimago.com> writes:
> ··········@hotmail.com writes:
> > Here is a second try:
> >
> > (defun randomize-list (lst)
> > (let ((len (length lst))
> > (new (copy-list lst)))
> > (loop for i from 0 below len do
> > (rotatef (elt new i) (elt new (random len))))
> > new))
>
> Slightly better, but:
> 1- it's still O(n�),
> 2- it's not equiprobable.
>
> It doesn't give equiprobable results, assuming an equiprobable RANDOM,
> because you can rotate twice or more elements below i.
>
>
> If you insist on processing a list, instead of using a temporary
> vector as showed in previous articles, you could write:
>
> (defun shuffle-list (list)
> (do* ((list (copy-list list) list)
> (length (length list) (1- length))
> (current list (cdr list)))
> ((< 2 length) list)
> (rotatef (first current) (elt current (random length)))))
>
> It would give correct results. It is still O(n�), but with better
> constants. For very short lists, it might be quicker than converting
> to and from a vector, but soon enough it should be slower.
If you use this algorithm but store the elements in a balanced binary
search tree (which can be implemented without side effects) you should
get a shuffle in which each permutation has equal probability. The
cost should be O(n log n). I don't think you can get a shuffle without
side effects that is better than that.
Sven-Olof Nystr�m
On Mon, 28 May 2007 17:19:48 +0200, <··········@hotmail.com> wrote:
>> * example usage?
> I'm using this to shuffle the learning data feeded to an neural
> network. It is alot of data so it can't be shuffled destructively.
>
Then why are you storing it a list? It has a overhead of 64 bytes (at
least)
pr element compared to storing the dataset in a array.
Also the shuffeling is now order n instead of n^2.
It is more common to use arrays to construct neural nets anyways.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
··········@hotmail.com wrote:
> I'm using this to shuffle the learning data feeded to an neural
> network. It is alot of data so it can't be shuffled destructively.
(1) Just leave the data as it stands, and access it via a list of
indices; shuffle the list of indices. This introduces a minor
overhead each time you access a datum, but you save more
time when you make a shuffle.
(2) Google for "Knuth shuffle".
(3) Use R (http://r-project.org). There is a neural network add-on
package, written by a reputable name in the field.
FWIW
Robert Dodier
On 28 May 2007 08:19:48 -0700, ··········@hotmail.com wrote:
>I'm using this to shuffle the learning data feeded to an neural
>network. It is alot of data so it can't be shuffled destructively.
Neural networks do not need their learning data to be presented in a
shuffled order.
Steve
--
Steve Wolstenholme Neural Planner Software Ltd
EasyNN-plus. The easy way to build neural networks.
http://www.easynn.com
> Neural networks do not need their learning data to be presented in a
> shuffled order.
Could you elaborate on this? I always had the impression that shuffeling is good
practice and experienced better results with shuffling in some of my experiments.
Regards,
Stefan
In article <···············@mid.dfncis.de>, Stefan Mandl wrote:
>> Neural networks do not need their learning data to be presented in a
>> shuffled order.
>
>Could you elaborate on this? I always had the impression that shuffeling is
>good practice and experienced better results with shuffling in some of my
>experiments.
Hi,
I suppose it depends on you training data. It also depends on your neural
network type, incuding the type of activation function you use.
Sigmoid-activated feed-forward nets can easily converge toward a local
error minimum when trained with backpropagation. I therefore agree with you
that, as a general rule, shuffling is good practice.
But, just out of interest, what type of experiments were you doing?
--
Oyvin
> Sigmoid-activated feed-forward nets can easily converge toward a local
> error minimum when trained with backpropagation. I therefore agree with you
> that, as a general rule, shuffling is good practice.
>
> But, just out of interest, what type of experiments were you doing?
This was for a course I gave several times ... experiments were different every time:
game board classfication, image classification, classifier for "walls" for a mobile robot,
classifier for "dangerous situations" in an offroad racing game.
I used the (J/S)NNS and Weka packages for the experiments.
(J/S)NNS implements a large variety of activation functions and learning algorithms and we
usually played around with those; there was no specific combination of activation functions
and learning algrorithm that we experienced to work all the time though.
Regards,
Stefan
··········@hotmail.com writes:
> please any comments on this common-lisp code:
>
> (defun remove-nth (a n)
> (declare (list a) (fixnum n))
> (loop for item in (remove nil
> (loop for i of-type fixnum from 0 below (length a) collect
> (if (/= i n)
> (cons (nth i a) nil))))
> collect (car item)))
(defun remove-nth (index list)
(remove-if (constantly t) list :start index :end (1+ index)))
> (defun randomize-list (lst)
> (let (l n (len (length lst)))
> (loop while (> len 0) do
> (setf n (random len))
> (push (nth n lst) l) ; copy element
> ; copy all from list a to list b but nth 'n element
> (setf lst (remove-nth lst n))
> (decf len))
> l))
(defun randomize-sequence (sequence)
(loop
:with vector = (coerce sequence 'vector)
:for i :from (1- (length vector)) :downto 1
:do (rotatef (aref vector i) (aref vector (random i)))
:finally (return (coerce vector (type-of sequence)))))
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Fri, 25 May 2007 16:22:27 +0200, <··········@hotmail.com> wrote:
> please any comments on this common-lisp code:
>
> (defun remove-nth (a n)
> (declare (list a) (fixnum n))
> (loop for item in (remove nil
> (loop for i of-type fixnum from 0 below (length a) collect
> (if (/= i n)
> (cons (nth i a) nil))))
> collect (car item)))
>
> (defun randomize-list (lst)
> (let (l n (len (length lst)))
> (loop while (> len 0) do
> (setf n (random len))
> (push (nth n lst) l) ; copy element
> ; copy all from list a to list b but nth 'n element
> (setf lst (remove-nth lst n))
> (decf len))
> l))
>
It is very inefficient to randomize a list.
Better the to use a array where length and nth are O(1).
If necessary you can make a array from the list first and put it back when
you are finished.
Like this perhaps..
(defmethod scramble ((sequence array))
(loop with len = (length sequence)
for i from 0 below len do
(rotatef (aref sequence i) (aref sequence (+ (random (- len i))
i))))
sequence)
(defmethod scramble ((sequence list))
(coerce (scramble
(make-array (length sequence) :initial-contents sequence))
'list))
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On Fri, 25 May 2007 17:27:32 +0200, John Thingstad
<··············@chello.no> wrote:
>
> (defmethod scramble ((sequence array))
> (loop with len = (length sequence)
> for i from 0 below len do
> (rotatef (aref sequence i) (aref sequence (+ (random (- len i))
> i))))
> sequence)
>
> (defmethod scramble ((sequence list))
> (coerce (scramble
> (make-array (length sequence) :initial-contents sequence))
> 'list))
Looking at the other suggestins made some (trivial) improvements.
(defmethod shuffle ((sequence array))
(loop with len = (length sequence)
for i from 0 below len do
(rotatef (aref sequence i) (aref sequence (+ (random (- len i))
i))))
sequence)
(defmethod shuffle ((sequence list))
(coerce (scramble (coerce sequence 'vector)) 'list))
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
(message (Hello 'John)
(you :wrote :on '(Fri, 25 May 2007 17:27:32 +0200))
(
JT> It is very inefficient to randomize a list.
really? it's inefficient to randomize list this way, swaping to random
elements.
but in general, i think there is efficient list shuffling algorithm, since
people doing pure functional programming deal with immutable structures, so
they need to emulate mutable structures with lists and trees, and as far as
i know they achieve good results on most algorithms.
here's a perfect shuffle in Haskell:
http://okmij.org/ftp/Haskell/perfect-shuffle.txt
it appears that sort-based shuffle is not perfect because numbers can
repeat. i think if we use float numbers, they are very unlikely to repeat:
(defun sort-list-shuffle (list)
(mapcar #'car
(sort
(mapcar (lambda (c) (cons c (random 1.0))) list)
#'> :key #'cdr)))
on my implementation of choise it runs only 2.5 times slower than your
version -- at least no "very" inefficient :)
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"I am everything you want and I am everything you need")
On Sat, 26 May 2007 15:08:22 +0200, Alex Mizrahi
<········@users.sourceforge.net> wrote:
>
> (defun sort-list-shuffle (list)
> (mapcar #'car
> (sort
> (mapcar (lambda (c) (cons c (random 1.0))) list)
> #'> :key #'cdr)))
>
> on my implementation of choise it runs only 2.5 times slower than your
> version -- at least no "very" inefficient :)
>
I'd say this is a example where a applicative approach beats a functional
one.
Incidentally you code uses sort which is destructive on it's input..
Not that it matters here.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Hi,
> (defun sort-list-shuffle (list)
> (mapcar #'car
> (sort
> (mapcar (lambda (c) (cons c (random 1.0))) list)
> #'> :key #'cdr)))
>
> on my implementation of choise it runs only 2.5 times slower than your
> version -- at least no "very" inefficient :)
Hmm... How about:
(defun sort-list-shuffle (list)
(sort list #'< :key (lambda (x) (declare (ignore x)) (random 1.0))))
Would that work as well?
Bye-bye,
Matthias
Hi again,
> Hmm... How about:
>
> (defun sort-list-shuffle (list)
> (sort list #'< :key (lambda (x) (declare (ignore x)) (random 1.0))))
>
> Would that work as well?
Ah, I guess it depends on how SORT is implemented. Probably won't
work the way it's supposed to in general.
Bye-bye,
Matthias
Matthias Benkard <··········@gmail.com> writes:
> Hi,
>
> > (defun sort-list-shuffle (list)
> > (mapcar #'car
> > (sort
> > (mapcar (lambda (c) (cons c (random 1.0))) list)
> > #'> :key #'cdr)))
> >
> > on my implementation of choise it runs only 2.5 times slower than your
> > version -- at least no "very" inefficient :)
>
> Hmm... How about:
>
> (defun sort-list-shuffle (list)
> (sort list #'< :key (lambda (x) (declare (ignore x)) (random 1.0))))
Well, I think this violates some of the assumptions of sort keys as
expressed in the CL standard. One problem is that you aren't sure how
often your KEY function would get called. IIRC one of the techniques
suggested in CLtL for a sort is to use the KEY function to create a
shadow sequence of keys to sort, and then order the underlying
sequence. In that case, you would call the key function once per
element. On the other hand, if the key is used for each comparison,
then you would be looking at multiple calls for at least some of the
elements, and a potential to blow up the algorithm completely, because
you don't have a stable partial order.
I think you therefore need to associate the random value with the
element.
--
Thomas A. Russ, USC/Information Sciences Institute
(message (Hello 'Matthias)
(you :wrote :on '(28 May 2007 02:26:48 -0700))
(
MB> Hmm... How about:
MB> (defun sort-list-shuffle (list)
MB> (sort list #'< :key (lambda (x) (declare (ignore x)) (random 1.0))))
MB> Would that work as well?
although some (naive, or over-optimized) implementations of sort can either
duplicate/omit elements, or hang, it apears that standard requires sort to
return something even if predicate or key is weird:
---
If the key and predicate always return, then the sorting operation will
always terminate, producing a sequence containing the same elements as
sequence (that is, the result is a permutation of sequence). This is
guaranteed even if the predicate does not really consistently represent a
total order (in which case the elements will be scrambled in some
unpredictable way, but no element will be lost).
---
and does not require predicate or key to be consistent:
---
If the key consistently returns meaningful keys,
---
i think "If" here implicitly allows key to return inconsistent and
non-meaningful keys :)
so i think this should work, although i wouldn't bet that all
implementations handle this correctly :)
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"I am everything you want and I am everything you need")
(message (Hello ···········@hotmail.com)
(you :wrote :on '(25 May 2007 07:22:27 -0700))
(
s> please any comments on this common-lisp code:
it's horrid. if you really need that algorithm, search for "shuffle list" in
google.
in general, you'd better use functional algorithm or macro rotatef
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"I am everything you want and I am everything you need")
On May 25, 7:22 am, ··········@hotmail.com wrote:
I wrote a long post, but I guess the computer ate it. GRRRRR.
Anyway, try this one:
(defun shuffle (list)
(if (or (null list)
(null (cdr list)))
list
(do ((tail list (cdr tail))
(odd '() (cons (car tail) even))
(even '() odd))
((null tail)
(merge 'list
(shuffle odd)
(shuffle even)
(lambda (a b)
(zerop (random 2))))))))
I haven't convinced myself that it has a flat distribution, though.
It should run a lot quicker than your version.
I wrote the fisher yates random shuffle, known as O(n log n), for
common lisp.
When the program is on SBCL, consing of the tail recursion version is
less than
that of the do-loop version. Random shuffle of 10000 elements vector
is 30 times
faster than that of list.
(fisher-yates lst): the list version
(fisher-yates-vec vec): the vector version
As I use the function with fill-pointer vector, I select "aref" as the
vector
manipulation. But I want to use "svref" ^^;
----
; fisher-yates - algorithm for random shuffle.
; Y.TAKENAKA (reverse "moc.liamgTAakanekat.y") Lastupdate May
25,2007
(proclaim '(optimize speed))
(defun swap (pos1 pos2 lst)
"caution: swap function has side-effects to lst."
(unless (eql pos1 pos2 )
(rotatef
(nth (the unsigned-byte pos1) lst)
(nth (the unsigned-byte pos2) lst)))
lst)
(defun fisher-yates (lst)
"The fisher yates random shuffle algorithm for list"
(let ((len (the unsigned-byte (length lst))))
(labels ((fy (lst pos)
(declare (type unsigned-byte pos))
(declare (inline swap))
(if (zerop pos)
lst
(fy
(swap
(the unsigned-byte pos)
(the unsigned-byte (random pos)) lst)
(the unsigned-byte (1- pos))))))
(fy lst (the unsigned-byte (1- len))))))
(defun vec-swap (pos1 pos2 vec)
"caution: swap function has side-effects to lst."
(unless (eql pos1 pos2 )
(rotatef
(aref vec (the unsigned-byte pos1))
(aref vec (the unsigned-byte pos2))))
vec)
(defun vec-fisher-yates (vec)
"The fisher yates random shuffle algorithm for vector"
(let ((len (the unsigned-byte (length vec))))
(labels ((fy (vec pos)
(declare (type unsigned-byte pos))
(declare (inline vec-swap))
(if (zerop pos)
vec
(fy
(vec-swap
(the unsigned-byte pos)
(the unsigned-byte (random pos)) vec)
(the unsigned-byte (1- pos))))))
(fy vec (the unsigned-byte (1- len))))))
----