Implementing the most efficient array shuffling method in JavaScript

Implementing the most efficient array shuffling method in JavaScript_javascript skills

WBOY

Release： 2016-05-16 16:34:10

Original

2033 people have browsed it

Array reordering means disrupting the order of all elements in the array.

A common method is to pass a function into the native sort method of the array. This function randomly returns 1 or -1 to achieve the purpose of randomly arranging the array elements.

Copy code The code is as follows:

arr.sort(function(a,b){ return Math.random()>.5 ? -1 : 1;});

Although this method is intuitive, it is not very efficient. After my test, the time it takes to scramble an array of 10,000 elements is about 35ms (firefox)

I have always had the good quality of asking for answers, so I searched for an efficient method. See the original text here

Copy code The code is as follows:

if (!Array.prototype.shuffle) {

Array.prototype.shuffle = function() {

for(var j, x, i = this.length; i; j = parseInt(Math.random() * i), x = this[--i], this[i] = this[j], this[j ] = x);

         return this;

};

}

arr.shuffle();

This method adds a function to Array.prototype called shuffle - but the name is not important, what is important is its efficiency.

Take my above array of 10,000 elements to test. It only takes 7 or 8 milliseconds to complete the out-of-order operation using this method.

Increase the array elements 10 times to 100000 to test. The first sort method takes about 500 ms, and the shuffle method takes about 40 ms. The difference is huge.

Full test code:

Copy code The code is as follows:

var count = 100000,arr = [];
for(var i=0;i.5 ? -1 : 1;});
Array.prototype.sort.call(arr,function(a,b){ return Math.random()>.5 ? -1 : 1;});
document.write(arr '
');
var t1 = new Date().getTime();
document.write(t1-t);

//The following method is the most efficient
if (!Array.prototype.shuffle) {
Array.prototype.shuffle = function() {
for(var j, x, i = this.length; i; j = parseInt(Math.random() * i), x = this[--i], this[i] = this[j], this[j ] = x);
return this;
};
}
var t = new Date().getTime();
arr.shuffle();
document.write('
' arr '
');
var t1 = new Date().getTime();
document.write(t1-t);

In addition, have you noticed that the for loop in the shuffle code does not have the second half! That is, there is only for(..) but no {..} behind it. It can be written like this! And it actually executes normally! It’s curious, I have to go to the blog park and ask.