In depth analysis of javascript random shuffle algorithm

Shuffling algorithm is a common random problem, often encountered in the game, random sorting. It can be abstracted in such a way as to obtain a randomly ordered array of all natural Numbers up to M.

Search in baidu "shuffle algorithm", the first result is "baidu library - shuffling algorithm", scan the contents, many contents are easy to mislead others to the wrong way, including the end of the linked list instead of array, is only a limited optimization (linked list also introduced the loss of reading efficiency).

The first method in this paper can be simply described as: randomly draw CARDS and put them in another group; Draw again, draw an empty card and repeat.
"Draw an empty card and then draw again" this will lead to the opportunity to draw an empty card after more and more, is clearly unreasonable.
Can be optimized into a step: after the card is drawn, the original card becomes less. (instead of leaving an empty card)
The code is as follows:

function shuffle_pick_1(m) // Shuffle the deck  // Draw method 
{
    //M CARDS
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
        arr[i] = i;
    }
    //Draw one card at a time and put it in another pile. It takes a lot of time to pull the elements out of the array and pull all the subsequent elements forward.
    var arr2 = new Array();
    for (var i=m; i>0; i--) {
        var rnd = Math.floor(Math.random()*i);
        arr2.push(arr[rnd]);
        arr.splice(rnd,1);
    }
    return arr2;
}

This is also obviously problematic because if the array is large, deleting an element in the middle causes the queue to move forward, which is a time-consuming action.
Think back to "why did we remove that element?" The goal is not to generate empty CARDS.
Are there other ways we can get rid of an empty card other than by removing that element?
B: yes, we just put the last undrawn card in the place where it was drawn.
So, this idea can be optimized to look like this:

function shuffle_pick(m) // Shuffle the deck  // Drawing optimizes the CARDS 
{
    //M CARDS
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
        arr[i] = i;
    }
    //Draw one card at a time and put it in another pile. Place the last card undrawn on the empty seat.
    var arr2 = new Array();
    for (var i=m; i>0;) {
        var rnd = Math.floor(Math.random()*i);
        arr2.push(arr[rnd]);
        arr[rnd] = arr[--i];
    }
    return arr2;
}

In addition to the idea of drawing CARDS, we can also use the idea of changing CARDS.
"Baidu library - shuffling algorithm" mentioned a way to change the brand: "random exchange of two positions, a total of n times of exchange, the bigger n, the closer to random.
This is not correct, even if n is large (for example, 10 CARDS, 10 swaps), there is still a high probability that "some CARDS did not change position at all."
Along this line of thought, make a small adjustment can be: the I th card and any card swap, change a round.
The code is as follows:

function shuffle_swap(m) // Shuffle the deck  // The card method 
{
    //M CARDS
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
        arr[i] = i;
    }
    //The I th card and any card commutator, change the whole round
    for (var i=0; i<m; i++) {
        var rnd = Math.floor(Math.random()*(i+1)),
            temp = arr[rnd];
        arr[rnd] = arr[i];
        arr[i]=temp;
    }
    return arr;
}

In addition to the idea of drawing and changing CARDS, we can also use the idea of inserting CARDS: first there is a card, the second card has two positions to be inserted randomly (before or after the first card), the third card has three positions to be inserted randomly (after, or in the first card, or in the second card), and so on
The code is as follows:

function shuffle_insert_1(m) // Shuffle the deck  // Insert card method 
{
    //The largest card is generated one at a time and inserted in front of some random card. It's time consuming because you're inserting elements into an array, pushing everything behind you one bit backward.
    var arr = [0];
    for (var i=1; i<m; i++) {
        arr.splice(Math.floor(Math.random()*(i+1)),0,i);
    }
    return arr;
}

There are a few problems with the above code: as the number of CARDS increases, it becomes more and more difficult to insert CARDS, because card inserts cause many CARDS to be pushed back.
Of course, we can also optimize it appropriately: n minus 1 CARDS, the NTH card at the end, and then swap places with any card.
The code is as follows:

function shuffle_insert(m) // Shuffle the deck  // Insert method optimization version, can be proved by mathematical induction, this shuffle is uniform. 
{
    //One card at a time, the largest card, and some random card commutator
    var arr = new Array(m);
    arr[0] = 0;
    for (var i=1; i<m; i++) {
        var rnd = Math.floor(Math.random()*(i+1));
        arr[i] = arr[rnd];
        arr[rnd] = i;
    }
    return arr;
}

All right, the code is as follows. Those of you who are interested can try it on your own machine to see if their respective execution efficiency and the final result is theoretical random.

 

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<title>JK : javascript  Shuffle algorithm  </title>
</head>
<body>
<script type="text/javascript">
function shuffle_pick_1(m) // Shuffle the deck  // Draw method 
{
    //M CARDS
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
        arr[i] = i;
    }
    //Draw one card at a time and put it in another pile. It takes a lot of time to pull the elements out of the array and pull all the subsequent elements forward.
    var arr2 = new Array();
    for (var i=m; i>0; i--) {
        var rnd = Math.floor(Math.random()*i);
        arr2.push(arr[rnd]);
        arr.splice(rnd,1);
    }
    return arr2;
}

function shuffle_pick(m) // Shuffle the deck  // Drawing optimizes the CARDS 
{
    //M CARDS
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
        arr[i] = i;
    }
    //Draw one card at a time and put it in another pile. Place the last card undrawn on the empty seat.
    var arr2 = new Array();
    for (var i=m; i>0;) {
        var rnd = Math.floor(Math.random()*i);
        arr2.push(arr[rnd]);
        arr[rnd] = arr[--i];
    }
    return arr2;
}

function shuffle_swap(m) // Shuffle the deck  // The card method 
{
    //M CARDS
    var arr = new Array(m);
    for (var i=0; i<m; i++) {
        arr[i] = i;
    }
    //The I th card and any card commutator, change the whole round
    for (var i=0; i<m; i++) {
        var rnd = Math.floor(Math.random()*(i+1)),
            temp = arr[rnd];
        arr[rnd] = arr[i];
        arr[i]=temp;
    }
    return arr;
}
function shuffle_insert_1(m) // Shuffle the deck  // Insert card method 
{
    //The largest card is generated one at a time and inserted in front of some random card. It's time consuming because you're inserting elements into an array, pushing everything behind you one bit backward.
    var arr = [0];
    for (var i=1; i<m; i++) {
        arr.splice(Math.floor(Math.random()*(i+1)),0,i);
    }
    return arr;
}
function shuffle_insert(m) // Shuffle the deck  // Insert method optimization version, can be proved by mathematical induction, this shuffle is uniform. 
{
    //One card at a time, the largest card, and some random card commutator
    var arr = new Array(m);
    arr[0] = 0;
    for (var i=1; i<m; i++) {
        var rnd = Math.floor(Math.random()*(i+1));
        arr[i] = arr[rnd];
        arr[rnd] = i;
    }
    return arr;
}

//alert(shuffle_pick(10))

var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert],
    funcNames = [" draw ", " Draw optimization ", " The card ", " Insert card ", " Insert card to optimize "]
    m = 10000,
    times=[];
for(var i = 0; i < funcs.length; i++){
    var d0= new Date();
    funcs[i](m);
    funcNames[i] = (new Date() - d0) + 't' + funcNames[i];
}
alert(funcNames.join('n'));
</script>

</body>
</html>