JavaScript topics out of order

Math.random() can’t be truly out of order.

out-of-order

Out of order means to scramble an array.

Well, no, just look at the code.

Math.random

A common notation is to use math.random () :

var values = [1.2.3.4.5];

values.sort(function(){
    return Math.random() - 0.5;
});

console.log(values)Copy the code

Math.random() -0.5 returns a positive number, a negative number, or a 0, descending if positive, ascending if negative, descending if zero, and then ascending or descending until an array is out of order.

It seems to be a good plan, but in fact, the effect is not satisfactory. Let’s write a demo to test it:

var times = [0.0.0.0.0];

for (var i = 0; i < 100000; i++) {

    let arr = [1.2.3.4.5];

    arr.sort((a)= > Math.random() - 0.5);

    times[arr[4]- 1] + +; }console.log(times)Copy the code

The test principle is: disorder [1, 2, 3, 4, 5] 100,000 times, calculate the number of times that the last element of the disordered array is 1, 2, 3, 4, 5 respectively.

A random result is:

[30636.30906.20456.11743.6259]Copy the code

The result shows that there are 30,636 cases where the last element of the out-of-order array is 1, 30,906 cases where the last element of the out-of-order array is 2, and so on.

We’ll see that the number of times the last element is 5 is much lower than the number of times it is 1, so this scheme is problematic.

But I think it’s a good idea. When you first see it, it’s kind of amazing. Why would that be a problem?

Yes! I’m curious!

Insertion sort

If you want to get to the bottom of the problem, you have to understand how sort works, but ECMAScript only specifies the effect, not the implementation, so different browsers implement it differently.

To solve this problem, let’s take V8 as an example. V8 uses insertion sort when the target array length is less than 10; Instead, use a mixture of quicksort and insert sort.

So let’s take a look at the v8 source code, because it is written in JavaScript, we can also read it.

Source code address: github.com/v8/v8/blob/…

In order to simplify the length, we analyze the array [1, 2, 3]. The array length is 3, and the insertion sort is adopted at this time.

Insert sort

function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
        var element = a[i];
        for (var j = i - 1; j >= from; j--) {
            var tmp = a[j];
            var order = comparefn(tmp, element);
            if (order > 0) {
                a[j + 1] = tmp;
            } else {
                break;
            }
        }
        a[j + 1] = element; }};Copy the code

It works by taking the first element as an ordered sequence, iterating through the array of numbers, and inserting subsequent elements into the constructed ordered sequence.

Here’s a simple diagram:

A concrete analysis

Insert sort (1, 2, 3); insert sort (2, 3);

The demo code is:

var values = [1.2.3];

values.sort(function(){
    return Math.random() - 0.5;
});Copy the code

Note that sort is implemented by InsertionSort. The value of InsertionSort is 0 and the value of to is 3.

We begin to analyze the out-of-order process step by step:

Because insertion sort according to the first element for the orderly, so the array of outer loop since I = 1, a [I] value is 2, the inner loop through right now, compare the compare (1, 2), because Math. The random () 0.5 there is a 50% chance of less than zero, the result of the There is a 50% chance that the array will be greater than 0, so there is a 50% chance that the array will become [2, 1, 3], and the 50% result will remain the same, the array will remain [1, 2, 3].

If (1, 2, 3) is still [1, 2, 3], we make another analysis, then iterate, I = 2, a[I] is 3, then inner loop iterate, compare(2, 3) :

There’s a 50% chance that the array stays the same, it’s still [1, 2, 3], and then the loop ends.

Compare (1, 3, 2) with a 50% chance of changing to [1, 3, 2], because we haven’t found the correct position of 3, we will iterate again, so in this 50% chance, we will compare(1, 3) with a 50% chance of remaining unchanged, the array is [1, 3, 2], at which point the iteration ends, There is a 50% chance that the array will change to [3, 1, 2].

In summary, in [1, 2, 3], there is a 50% probability that it will become [1, 2, 3], a 25% probability that it will become [1, 3, 2], and a 25% probability that it will become [3, 1, 2].

The other case [2, 1, 3] is similar to the analysis. We summarize the final results into a table:

To verify the accuracy of this calculation, let’s write a demo test:

var times = 100000;
var res = {};

for (var i = 0; i < times; i++) {

    var arr = [1.2.3];
    arr.sort((a)= > Math.random() - 0.5);

    var key = JSON.stringify(arr);
    res[key] ? res[key]++ :  res[key] = 1;
}

// For display purposes, convert to a percentage
for (var key in res) {
    res[key] = res[key] / times * 100 + The '%'
}

console.log(res)Copy the code

This is a random result:

We will find that there is a 50% chance that 3 will remain in place (i.e. [1, 2, 3] and [2, 1, 3]).

So what’s the root cause? In fact, in the algorithm of insertion sort, when the element to be sorted is compared with the ordered element, once the position is determined, it will not be compared with the ordered element in front of the position, so the disorder is not complete.

So how do you achieve true out-of-order? And that brings us to the classic Fisher-Yates algorithm.

Fisher – Yates

Why are they called Fisher-Yates? Because this algorithm was first proposed by Ronald Fisher and Frank Yates.

Without further ado, let’s look directly at the JavaScript implementation:

function shuffle(a) {
    var j, x, i;
    for (i = a.length; i; i--) {
        j = Math.floor(Math.random() * i);
        x = a[i - 1];
        a[i - 1] = a[j];
        a[j] = x;
    }
    return a;
}Copy the code

The principle is simple: iterate over a number of elements, and then swap the current element with the next element in a random position. As you can see from the code, this will be more completely out of order.

With ES6, the code can also be simplified to:

function shuffle(a) {
    for (let i = a.length; i; i--) {
        let j = Math.floor(Math.random() * i);
        [a[i - 1], a[j]] = [a[j], a[i - 1]];
    }
    return a;
}Copy the code

Let’s write another demo to test it:

var times = 100000;
var res = {};

for (var i = 0; i < times; i++) {
    var arr = shuffle([1.2.3]);

    var key = JSON.stringify(arr);
    res[key] ? res[key]++ :  res[key] = 1;
}

// For display purposes, convert to a percentage
for (var key in res) {
    res[key] = res[key] / times * 100 + The '%'
}

console.log(res)Copy the code

This is a random result:

The real realization of the disorderly effect!

series

JavaScript Thematic series directory address: github.com/mqyqingfeng… .

The JavaScript series is expected to write about 20 articles, focusing on the implementation of some function points in daily development, such as anti-shaking, throttling, de-weighting, type judgment, copy, maximum value, flat, Currie, recursion, out-of-order, sorting, etc. (Chao) (XI) underscore and jQuery underscore

If there is any mistake or not precise place, please be sure to give correction, thank you very much. If you like or are inspired by it, welcome star and encourage the author.