I recently read a very interesting article about random array sorting in JavaScript by olDJ’s predecessor. It is instructive to point out the problems with the classical notation we use to “sort an array randomly”.
This article will be illustrated with more detailed material and a variety of code demos. And try to use the “Fisher-Yates shuffle” algorithm for the ultimate solution.
Multiple familiar scenarios
Throwing an array out of order is a very simple but very common requirement. For example, “guess what you like”, “click to change batch”, “winning scheme”, etc., may be applied to such processing. I’ve seen it myself when I was writing code. The classic and popular solution is to take array.sort() and pass in a comparison function that returns a random value between [-0.5, 0.5] :
var numbers = [12.4.16.3];
numbers.sort(function() {
return . 5 - Math.random();
});Copy the codeThe rationale for this is not explained here. If you don’t understand, take a look at how the sort function is used in JS.
Toxic array.sort method
As the olDJ predecessor pointed out, using this method to disorder an array can be problematic.
To do this, I wrote a script to verify. And the visualization process is carried out. Clone is strongly recommended to go to Github and try it out on your own.
In the script, I’m right
var letters = ['A'.'B'.'C'.'D'.'E'.'F'.'G'.'H'.'I'.'J'];Copy the codeThe letters array was disordered 10,000 times using array.sort, and each disordered result was stored in Countings. The result is printed on the page:
var countings = [
{A:0.B:0.C:0.D:0.E:0.F:0.G:0.H:0.I:0.J:0},
{A:0.B:0.C:0.D:0.E:0.F:0.G:0.H:0.I:0.J:0},
{A:0.B:0.C:0.D:0.E:0.F:0.G:0.H:0.I:0.J:0},
{A:0.B:0.C:0.D:0.E:0.F:0.G:0.H:0.I:0.J:0},
{A:0.B:0.C:0.D:0.E:0.F:0.G:0.H:0.I:0.J:0},
{A:0.B:0.C:0.D:0.E:0.F:0.G:0.H:0.I:0.J:0},
{A:0.B:0.C:0.D:0.E:0.F:0.G:0.H:0.I:0.J:0},
{A:0.B:0.C:0.D:0.E:0.F:0.G:0.H:0.I:0.J:0},
{A:0.B:0.C:0.D:0.E:0.F:0.G:0.H:0.I:0.J:0},
{A:0.B:0.C:0.D:0.E:0.F:0.G:0.H:0.I:0.J:0}];var letters=['A'.'B'.'C'.'D'.'E'.'F'.'G'.'H'.'I'.'J'];
for (var i = 0; i < 10000; i++) {
var r = ['A'.'B'.'C'.'D'.'E'.'F'.'G'.'H'.'I'.'J'].sort(function() {
return . 5 - Math.random();
});
for(var j = 0; j <= 9; j++) { countings[j][r[j]]++; }}for(var i = 0; i <= 9; i++) {for(var j = 0; j <=9; j++) {document.getElementById('results').rows[i + 1].cells[j + 1].firstChild.data = countings[i][letters[j]]; }}Copy the codeThe results are shown as follows:
The result counts the out-of-order results of each element in the array. If you click the “Recalculate” button, you can conduct more than 10,000 sampling tests.
No matter how many times you click the button, you’ll see that the result is anything but “completely random.” For example, the A element is most likely to appear at the head of the array, the J element is most likely to appear at the end of the array, and all elements are most likely to stay in their original positions.
The crude conclusion is that using array.sort for out-of-order processing is definitely problematic.
How exactly is the array.sort method implemented underneath?
But why is it a problem? This starts at the bottom of the array.sort method. In the Chrome V8 engine source code, you can clearly see that
V8 uses both insert sort and fast sort when dealing with sort. When the target array length is less than 10, insert sort is used. Instead, use quickrow. Chrome’s V8 uses a combination of InsertionSort and QuickSort. That is, if the array is less than 10 elements in length, it uses an InsertionSort.
In fact, no matter what kind of sorting method is used, the time complexity of most sorting algorithms is between O(n) and O(n2), and the number of comparisons between elements is usually much less than n(n-1)/2, which means that some elements have no chance to compare at all (so there is no possibility of random exchange). These sort random sorting algorithms aren’t really random either.
How to understand the above sentence? In fact, we want to use array.sort to sort things out. The ideal or pure out of order scenario is to compare every two elements in the array with a 50% chance of switching places. So the total number of comparisons must be n(n-1). In the sort algorithm, most cases do not meet such conditions. So it’s certainly not a completely random result.
By the way, on the V8 engine sorting scheme, the source code using JS implementation, very conducive to front-end programmers to read. Where, corresponding to different array lengths, the use of fast sorting and insert sort different methods. It also uses a lot of performance optimization techniques, especially the interesting pivot choice for quicksort. Interested readers may wish to research it.
It’s really out of order
In order to achieve a true sense of disorder, it is not difficult. We first avoid the unstable array.sort method. In computer science, there’s a special one: the Fisher-Yates shuffle. If you’re naturally slow with algorithms, don’t panic. Here I step by step to achieve, I believe you must understand.
Let’s take a look at the entire code implementation, which is only 10 lines:
Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length- 1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
return input;
}
var tempArray = [ 1.2.3.4.5.6.7.8.9.10 ]
tempArray.shuffle();
console.log(tempArray); Copy the codeFirst we have an sorted array:
Step1: the first thing you need to do is pick the last element from the end of the array.
In a total of nine positions in the array, a random position is generated, and the element of that position is swapped with the last element.
Step2: in the previous step, we did a random substitution of the last element of the array. Next, work on the second-to-last element of the array. One of the eight positions, excluding the position of the last element already arranged, is randomly generated, and the element is swapped with the next-to-last element.
Step3: understand the first two, the next is in turn, so simple.
Implement out of order yourself
The above method is based on the Fisher-Yates Shuffle algorithm. Below, we need to open their own brains, complete a disorderly program. It’s not that hard, the key is how to produce real disorder. This is because it is often not completely out of order, for which you can refer to The Danger of Naivete.
Let’s take a look at liu Waayong’s series of advanced schemes in the community:
function shuffle (array) {
var copy = [],
n = array.length,
i;
while (n) {
i = Math.floor(Math.random() * array.length);
if (i in array) {
copy.push(array[i]);
deletearray[i]; n--; }}return copy;
}Copy the codeAnalysis of this scheme is also given:
We create a copy array, and then iterate over the target array, copying its elements into the copy array and removing the elements from the target array so that we can skip the sequence number the next time we iterate. And this implementation problem is here, even if a serial number on the element has been processed, the number is generated in the random function random, all the elements are serial number may appear constantly in after the cycle, one is the efficiency problem, another is the logical problem, there is a may be run forever.
The improvement scheme is as follows:
function shuffle(array) {
var copy = [],
n = array.length,
i;
while (n) {
i = Math.floor(Math.random() * n--);
copy.push(array.splice(i, 1) [0]);
}
return copy;
}Copy the codeThe improvement is to remove an element from the target Array using Array’s splice() method after processing it, and also update the target Array’s length. So the next time you iterate, you start with the new length, and you don’t have to do it again.
Of course, there are drawbacks to this scheme: for example, we create a copy array to return, creating a new space in memory. However, this can be completely avoided:
function shuffle(array) {
var m = array.length,
t, i;
while (m) {
i = Math.floor(Math.random() * m--);
t = array[m];
array[m] = array[i];
array[i] = t;
}
return array;
}Copy the codeInterestingly, this implementation is completely equivalent to the fisher-Yates shuffle scheme above.
conclusion
This article examines a simple, but interesting, requirements scenario called “array out of order.” A closer look at this scenario reveals some of the mysteries of JS and computer algorithms. In this paper, the processing of array.sort by V8 engine and fisher-Yates algorithm are briefly introduced. Hope to inspire readers.
Happy Coding!
PS: author Github warehouse, welcome to communicate through various forms of code. Baidu knowledge search department big front continue to recruit, senior engineer, intern positions are interested in quick contact.