The more you know, the more you don’t know
The introduction
An array out of order refers to randomly shuffling the order of the elements in an array.
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.
Sort combined with Math. The random
Microsoft did a survey of browser usage on BrowserChoice.eu, which showed users different browsers in random order on the page.
However, where each browser appears is not random. Internet Explorer appears in the last place about 50 percent of the time, and Chrome appears in the top three browsers most of the time.
What’s going on here? Random order?
Here’s the code they use to do random shuffle:
arr.sort((a)= >Math.random() - 0.5);
Copy the codeAt first glance, this seems like a reasonable solution. In fact, if you use a search engine to search for “randomly shuffled arrays”, this method will come up most frequently.
However, this approach is not really out of order in the sense that some elements do not have a chance to compare with each other, and the probability of the final array elements staying in positions is not completely random.
Here’s an example:
/** * array out of order */
function shuffle(arr) {
return arr.sort((a)= > Math.random() - 0.5);
}
Copy the code/** * Used to verify that the shuffle method is completely random */
function test_shuffle(shuffleFn) {
// The number of times the ordinal is out of order
let n = 100000;
// Save the number of occurrences of each element at each position
let countObj = {
a:Array.from({length:10}).fill(0),
b:Array.from({length:10}).fill(0),
c:Array.from({length:10}).fill(0),
d:Array.from({length:10}).fill(0),
e:Array.from({length:10}).fill(0),
f:Array.from({length:10}).fill(0),
g:Array.from({length:10}).fill(0),
h:Array.from({length:10}).fill(0),
i:Array.from({length:10}).fill(0),
j:Array.from({length:10}).fill(0),}for (let i = 0; i < n; i ++) {
let arr = ['a'.'b'.'c'.'d'.'e'.'f'.'g'.'h'.'i'.'j'];
shuffleFn(arr);
countObj.a[arr.indexOf('a')] + +; countObj.b[arr.indexOf('b')] + +; countObj.c[arr.indexOf('c')] + +; countObj.d[arr.indexOf('d')] + +; countObj.e[arr.indexOf('e')] + +; countObj.f[arr.indexOf('f')] + +; countObj.g[arr.indexOf('g')] + +; countObj.h[arr.indexOf('h')] + +; countObj.i[arr.indexOf('i')] + +; countObj.j[arr.indexOf('j')] + +; }console.table(countObj);
}
Copy the code// Verify that the shuffle method is random
test_shuffle(shuffle)
Copy the codeIn this example, we define two functions shuffle that use sort and math.random () for array disordering; shuffle uses sort and math.random () for array disordering. Test_shuffle function defines an array of length of 10 [‘ a ‘, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘I’ and ‘j’], and use the incoming order function for one hundred thousand times a second operation, The number of occurrences of each element in the array in each position is stored in the variable countObj, and countObj is finally printed out.
The results are as follows:
From this table, we can see that the probability of each element appearing in each position varies greatly. For example, element A appears 19415 times at index 0 and only 7026 times at index 4. The frequency of element A appearing in these two positions is very different (the difference is more than double). If sorting were really random, each element would have the same probability of appearing in each position, and the results would be very close to each other, rather than wildly different, as they are now.
Why is that a problem? This starts at the bottom of the array.sort method.
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 quicksort.
In fact, the time complexity of most sorting algorithms is between O(n) and O(n²), 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. These sort random sorting algorithms aren’t really random either.
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.
Incomplete comparison of sort from insertion sort
A simple insert sort code:
function insertSort(list = []) {
for(let i = 1 , len = list.length; i < len; i++){
let j = i - 1;
let temp = list[ i ];
while (j >= 0 && list[ j ] > temp){
list[j + 1] = list[ j ];
j = j - 1;
}
list[j + 1] = temp;
}
return list;
}
Copy the codeIt 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:
Sort (‘a’, ‘b’, ‘c’); sort (‘a’, ‘b’, ‘c’); sort (‘a’, ‘b’, ‘c’);
The demo code is:
var values = ['a'.'b'.'c'];
values.sort(function(){
return Math.random() - 0.5;
});
Copy the codeDetailed analysis is as follows:
Because insertion sort treats the first element as ordered, the outer loop of the array starts at I = 1. Math.random() -0.5 has a 50% chance of being less than 0, and a 50% chance of being greater than 0, so there is a 50% chance that the array will become [‘b’,’a’,’c’], and 50% of the results remain unchanged. Array is still [‘a’,’b’,’c’].
Suppose it is still [‘a’,’b’,’c’], we do the analysis again, then iterate, I = 2, compare b and C:
There’s a 50% chance that the array stays the same, it’s still [‘ A ‘,’b’,’c’], and the loop ends.
There’s a 50% chance that it’s going to be [‘a’,’c’,’b’], because it hasn’t found the right place for C, so there’s a 50% chance that it’s going to compare a and C again, and there’s a 50% chance that the array is going to be [‘a’,’c’,’b’], At this point the traversal is complete, with a 50% chance that the array will change to [‘ C ‘,’a’,’b’].
In conclusion, in the ‘a’, ‘b’, ‘c’], there is a 50% chance of become [‘ a ‘, ‘b’, ‘c’], there is a 25% chance of become [‘ a ‘, ‘c’, ‘b’], there is a 25% chance of become [‘ c ‘, ‘a’, ‘b’].
In the other case [‘b’,’a’,’c’] similar to this analysis, we aggregate the final results into a table:
Modify the combination of sort and math.random ()
We already know that the problem with sort and math.random () is the lack of a comparison between each element, so we might as well transform an array element into an object.
let arr = [
{
val:'a'.ram:Math.random()
},
{
val:'b'.ram:Math.random()
}
/ /...
]
Copy the codeWe store the original value of the array in the object’s val property, and add an attribute RAM to the object with a random value.
Then we just need to sort the random number of each object in the array to get a random array.
The code is as follows:
function shuffle(arr) {
let newArr = arr.map(item= >({val:item,ram:Math.random()}));
newArr.sort((a,b) = >a.ram-b.ram);
arr.splice(0,arr.length,... newArr.map(i= >i.val));
return arr;
}
Copy the codeApply the shuffle method to the validation function test_shuffle that we implemented earlier
test_shuffle(shuffle)
Copy the codeThe results are as follows:
From the table, we can see that the number of occurrences of each element in each position is not much different.
Although the randomness requirement is satisfied, this implementation does not perform well, requiring traversing the group several times and splice the array.
So how high performance implementation of 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.
The algorithm is actually very simple, which is to traverse the array from back to front, and then swap the current element with the element in a random position. Combine the pictures to explain:
First 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 steps, the next is in turn, so simple.
Now let’s implement Fisher-Yates in code
function shuffle(arr) {
let m = arr.length;
while (m > 1) {let index = Math.floor(Math.random() * m--);
[arr[m] , arr[index]] = [arr[index] , arr[m]]
}
return arr;
}
Copy the codeWe then use our previous validation function test_shuffle
test_shuffle(shuffle);
Copy the codeThe results are as follows:
From the table, we can see that the number of occurrences of each element in each position does not differ much, indicating that this method meets the requirement of randomness.
Moreover, Fisher-Yates algorithm only needs one traversal to randomly disarrange the array order, which has excellent performance ~~
At this point, we have found the best way to manipulate arrays out of order: Fisher — Yates~
reference
- How do I properly scramble arrays in Javascript
- JavaScript topics out of order
- Disorderly ordinal group
Series of articles recommended
- “Front-end Advanced” single page routing parsing and implementation
- “Front-end advancement” thoroughly understand the function of currification
- “Front-end advanced” JS stack memory heap memory
- Memory management in “front-end advanced” JS
Write in the last
- If there are any mistakes in this article, please correct them in the comments section. If this article helped you, please
give a likeandFocus on - This article was published simultaneously withgithub, can be ingithubFind more articles, welcome
Watch&Star u - See the following article: Plan
Welcome to pay attention to the wechat public number [front-end small black house], every week 1-3 high-quality articles push, help you to progress
