How to write good JavaScript is every front-end engineer has been thinking about the problem, Moon shadow teacher told us some good JavaScript principles, but also taught us some of the skills of how to write good JavaScript, today to continue to learn JavaScript with moon shadow teacher ~~
start
When we write code, the most important thing is to make sure that our code is correct. However, in some cases, the code will work and look right, but it may not be correct
Let’s look at an example
Shuffle algorithm
If you were to implement a shuffling algorithm, how would you do that? It doesn’t take long to figure out that we could just randomly sort an array, shuffle it, like this
function shuffle(cards) {
return [...cards].sort(() = > (Math.random() > 0.5 ? -1 : 1));
}
const cards = [0.1.2.3.4.5.6.7.8.9];
console.log(shuffle(cards)); // [3, 1, 5, 4, 8, 7, 2, 6, 9, 0]
Copy the codeRunning it a few times looks good, but it does mess up the order
Is this algorithm really correct? Or is this algorithm really fair?
Verify correctness
So let’s verify that this shuffling algorithm is correct. How do we verify that?
We repeat the shuffle a million times, and the result array is used to record the sum of the digits in each position. If this were a fair algorithm, the numbers in the result array would all be close.
const result = Array(10).fill(0);
for (let i = 0; i < 1000000; i++) {
const c = shuffle(cards);
for (let j = 0; j < 10; j++) { result[j] += c[j]; }}console.log(result);
Copy the codeSo what I get is this
[3863812.3862770.4544657.4648808.4669379.4364000.4362095.4722847.4852688.5108944]
Copy the codeYou can see that the result is increasing, and that the sum of all the digits in the first and last positions is quite different, which means that the larger the number is, the more likely it is to appear at the end of the array. The probability of each element being placed in each position is different, which is an unfair algorithm.
How to solve this problem?
Solution 1: Wash it more often
twice
const result = Array(10).fill(0);
for (let i = 0; i < 1000000; i++) {
const c = shuffle(shuffle(cards));
for (let j = 0; j < 10; j++) { result[j] += c[j]; }}console.log(result);
Copy the code[4431933.4414334.4501168.4514001.4527342.4493793.4496849.4537253.4540943.4542384]
Copy the codeThree times
const result = Array(10).fill(0);
for (let i = 0; i < 1000000; i++) {
const c = shuffle(shuffle(shuffle(cards)));
for (let j = 0; j < 10; j++) { result[j] += c[j]; }}console.log(result);
Copy the code[4487963.4491386.4495428.4499063.4494726.4505270.4498303.4510195.4508869.4508797]
Copy the codeAs you can see, after a few more washes, the numbers in the result array are basically the same, which means that our algorithm is relatively fair!
Solution 2: Random sampling
Repeated shuffling always fails to solve the problem at the algorithm level. We hope to fundamentally solve the problem by modifying the shuffling algorithm
The reason for the problem of the previous algorithm is that we used the sort method. When the pairs are exchanged, they are all exchanged nearby, so the positions of exchange are not random enough
We use a random sampling method to shuffle cards
- We pick a random number from the array and swap the number at the end of the current array
- Remove the trailing array just swapped and proceed to step 1
- Until all the numbers are swapped
Algorithm implementation
function shuffle(cards) {
const c = [...cards];
// Reverse order traversal number group
for (let i = c.length; i > 0; {I -),// Select a position at random
const pIdx = Math.floor(Math.random() * i);
// Swaps the element at the selected position with the element at the end of the array
[c[pIdx], c[i - 1]] = [c[i - 1], c[pIdx]];
}
return c;
}
Copy the codeIt is equivalent to the non-replacable touch ball model in combinatorial mathematics. Assuming there are n balls, it is easy to prove by mathematical induction that the probability of each ball obtained by this algorithm is 1/n
Verify this algorithm using the above validation method
const result = Array(10).fill(0);
for (let i = 0; i < 1000000; i++) {
const c = shuffle(cards);
for (let j = 0; j < 10; j++) { result[j] += c[j]; }}console.log(result);
Copy the codeThe results obtained
[4498337.4502249.4502001.4498385.4504714.4500172.4498057.4502210.4498232.4495643]
Copy the codeAs you can see, the numbers are very similar, very uniform, so this algorithm is fair, it’s correct
application
Lucky draw
For example, if we want to draw a lottery, we can just pick an element at any position
Math.floor(Math.random() * length)
Copy the codeBut our lottery is a process, such as drawing the first prize, second prize, third prize, lucky prize and so on, need to be encapsulated, using our above shuffle algorithm
Changing a function to a generator and a return to yield can be used as a partial shuffle, or as a lottery
function* shuffle(items) {
items = [...items];
for (let i = items.length; i > 0; i--) {
const idx = Math.floor(Math.random() * i);
[items[idx], items[i - 1]] = [items[i - 1], items[idx]];
yield items[i - 1]; }}Copy the codeI can show you all of them
let items = [1.2.3.4.5.6.7.8.9];
items = shuffle(items);
console.log(... items);// 3
Copy the codeAlso can only select part, the realization of part shuffling, or the function of the lottery
Five out of 100 numbers are chosen at random
let items = [...new Array(100).keys()];
let n = 0;
// 5 of 100 numbers are randomly selected
for (let item of shuffle(items)) {
console.log(item);
if (n++ >= 5) break;
}
// 24 62 60 16 42 21
Copy the codeShare out bonus package
In the function of snatching red packets in the APP, the algorithm of random bonus packets is carried out internally
In order not to appear, after a random point, a red envelope is too big, resulting in the remaining red envelope is not enough, you can use the following method, that is, after each division, choose the largest existing red envelope to continue to divide, so as to ensure that the red envelope can be divided enough
function generate(amount, count){
let ret = [amount];
while(count > 1) {// Select the largest piece to cut
let cake = Math.max(... ret), idx = ret.indexOf(cake), part =1 + Math.floor((cake / 2) * Math.random()),
rest = cake - part;
ret.splice(idx, 1, part, rest);
count--;
}
return ret;
}
Copy the code
Sometimes, to make grabbing red packets more interesting, we don’t want our red packets to be divided equally
For example, if 100 yuan is divided among 10 people, it is equivalent to cutting on a (0,100.00) number line, randomly cutting nine times in different positions,
So it can be converted to our shuffle program, which randomly selects nine of the 10,000 positions between 0 and 100.00 and divides the red packets into ten, so that the red packets are not distributed evenly
function * shuffle(cards){
const c = [...cards];
for(let i = c.length; i > 0; i--) {
const pIdx = Math.floor(Math.random() * i);
[c[pIdx], c[i - 1]] = [c[i - 1], c[pIdx]];
yield c[i - 1]; }}function generate(amount, count){
if(count <= 1) return [amount];
const cards = Array(amount - 1).fill(0).map((_, i) = > i + 1);
const pick = shuffle(cards);
const result = [];
for(let i = 0; i < count; i++) {
result.push(pick.next().value);
}
result.sort((a, b) = > a - b);
for(let i = count - 1; i > 0; i--) {
result[i] = result[i] - result[i - 1];
}
return result;
}
Copy the code
conclusion
We write a good program, must ensure that it is correct!
Using the sort method to randomly shuffle cards may result in an unfair algorithm
More related posts
[Youth Training camp] Teacher Yue Ying told me the three principles of writing good JavaScript — each is responsible for his own work
[Youth Training Camp] Teacher Yue Ying told me the three principles of good JavaScript writing — component encapsulation
[Youth Training Camp] Teacher Yue Ying told me the three principles of good JavaScript – process abstraction
[Youth Training Camp] Teacher Yue Ying told me four skills to write good JavaScript — style first