1

I have seen people[1] suggesting the use of 

function choose(arr, n){
    if(n > arr.length)    throw "Invalid";
    return arr.sort(() => 0.5 - Math.random()).slice(0, n);
}

to randomly choose n elements from a list. However, depending on the sorting algorithm implementation, it might not terminate due to how the compare function is not consistent over time.

My question would be does the specification guarantee termination, i.e. efficiency aside, is the above function safe to use. §22.1.3.25 doesn't seem to give any information on it[2].

Derek 朕會功夫
  • 92,235
  • 44
  • 185
  • 247
  • 1
    Doesn’t look like that’s guaranteed by the spec. Given how common a mistake it is, though, I can’t imagine any implementation choosing a sort that might not terminate. Just the implementation-definedness (and actual non-uniform behaviour) are enough to make it wrong, though, and it’s super wasteful for something that could take linear time on the number of choices instead in not many lines of code. – Ry- Aug 07 '17 at 22:41
  • You might start by reading the specification for [*Array.prototype.sort*](http://ecma-international.org/ecma-262/8.0/#sec-array.prototype.sort). In particular, "*If comparefn … is not a consistent comparison function for the elements of this array (see below), the sort order is implementation-defined.*" – RobG Aug 07 '17 at 22:42
  • @RobG: That is the [2] link in the question. – Ry- Aug 07 '17 at 22:44
  • Yes, highlighting the relevant bit. The compare function isn't consistent, so the result is implementation dependent. It might choose to terminate after a certain number of iterations, or some memory limit, or continue infinitely, whatever. It's up to the implementation. – RobG Aug 07 '17 at 22:46
  • Thanks everyone, I believe the answer is that the specification indeed does not guarantee termination and might not be safe to use the code described in the question. – Derek 朕會功夫 Aug 07 '17 at 22:49
  • that code doesn't randomize a list, not even close, yet i see it often, smh... (use it to shuffle the alphabet and see how often "B" comes in last, should be 1/26) – dandavis Aug 08 '17 at 02:19

0 Answers0