dimanche 19 septembre 2021

Shuffling an array by sorting randomly generated floats - Why can't we use the random number alone to sort (shuffle) the array?

I have uncovered an efficiently presented shuffle function that is desirably brief and quick to read.

https://www.w3docs.com/snippets/javascript/how-to-randomize-shuffle-a-javascript-array.html

    function shuffleArray(arr) {
      arr.sort(() => {
          r = Math.random() - 0.5 
          // console.log(r)
          return r
      });
    }
    let arr = [1, 2, 3, 4, 5];
    shuffleArray(arr);
    console.log(JSON.stringify(arr))

To start, some time ago I took a computer arithmetic course during my studies, and have a basic understanding of IEEE 754 floating point number representation in 32 or 64-bit format, though the specific algorithms in hardware that utilize step by step operations like randomly producing a bit vector that is placed into the mantissa region of the number, or performing floating point arithmetic (add/subtract) operations is not yet currently hardwired in my mind.

Float 32-Bit Layout Float 64-Bit Layout


Upon inserting a console.log() statement in the accepted callback function passed into sort() to examine execution of the entire snippet, I can not reason why we need to offset the random number to be biased around the 0.0 value, as opposed to be producing a number between 0.0 and 1.0 non inclusive. Yes, I have seen this before, but no, I can not convince myself why...

In fact, to confirm, removal of 0.5 from the range shift computation produces the same array that we need to shuffle.

Why is this happening? What is undesirable about the positive random number originally generated to produce a comparable value for each array element during the sort comparison?
Does the .sort() method not work well with values that fall within that (0,1) range and why?




Aucun commentaire:

Enregistrer un commentaire