Prev: Creating an Object that extends Array functionality
Next: Limit of 4K
From: Jorge on 29 Oct 2009 17:03
http://code.google.com/p/jslibs/wiki/JavascriptTips

--
Jorge.
From: John G Harris on 30 Oct 2009 12:40
On Thu, 29 Oct 2009 at 14:03:49, in comp.lang.javascript, Jorge wrote:
>http://code.google.com/p/jslibs/wiki/JavascriptTips

The section 'shuffle the Array' looks rather dodgy.

It's also slower for large arrays than the usual algorithm.

John
--
John Harris
From: Lasse Reichstein Nielsen on 30 Oct 2009 13:06
John G Harris <john(a)nospam.demon.co.uk> writes:

> On Thu, 29 Oct 2009 at 14:03:49, in comp.lang.javascript, Jorge wrote:
>>http://code.google.com/p/jslibs/wiki/JavascriptTips
>
> The section 'shuffle the Array' looks rather dodgy.

Indeed. The "algorithm" is:
list = list.sort(function() Math.random() - 0.5)

What will happen depends on the underlying sorting algorithm, the only
thing that's safe to assume is that the shuffling will not have
an (approximatly) even distribution of the possible permutations.

If, e.g., it uses insertion sort (often used for small arrays), the
last element has a 50% chance of staying where it is, and 25% chance
of moving only one position.

It's not even remotely usable for actual shuffling.

(Not to mention that I've seen at least one sort implementation that
that didn't necessarily terminate for a non-stable comparison!)

/L
--
Lasse Reichstein Holst Nielsen
'Javascript frameworks is a disruptive technology'

From: Jorge on 30 Oct 2009 13:46
On Oct 30, 6:06 pm, Lasse Reichstein Nielsen <lrn.unr...(a)gmail.com>
wrote:
> John G Harris <j...(a)nospam.demon.co.uk> writes:
>
> > On Thu, 29 Oct 2009 at 14:03:49, in comp.lang.javascript, Jorge wrote:
> >>http://code.google.com/p/jslibs/wiki/JavascriptTips
>
> > The section 'shuffle the Array' looks rather dodgy.
>
> Indeed. The "algorithm" is:
>  list = list.sort(function() Math.random() - 0.5)
>
> What will happen depends on the underlying sorting algorithm, the only
> thing that's safe to assume is that the shuffling will not have
> an (approximatly) even distribution of the possible permutations.
>
> If, e.g., it uses insertion sort (often used for small arrays), the
> last element has a 50% chance of staying where it is, and 25% chance
> of moving only one position.
>
> It's not even remotely usable for actual shuffling.
>
> (Not to mention that I've seen at least one sort implementation that
> that didn't necessarily terminate for a non-stable comparison!)


Yes...

http://groups.google.com/group/comp.lang.javascript/browse_thread/thread/781e50864cc96088/5d3754682dbf61db#d6bc5f084b91bf85
--
Jorge.
From: Lasse Reichstein Nielsen on 30 Oct 2009 14:10
Jorge <jorge(a)jorgechamorro.com> writes:

> Yes...
>
> http://groups.google.com/group/comp.lang.javascript/browse_thread/thread/781e50864cc96088/5d3754682dbf61db#d6bc5f084b91bf85

Ahem, yes, I see. Ok, I do repeat myself.
But it's still true! :)

/L
--
Lasse Reichstein Holst Nielsen
'Javascript frameworks is a disruptive technology'

 |  Next  |  Last
Pages: 1 2 3 4
Prev: Creating an Object that extends Array functionality
Next: Limit of 4K