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 code

Running 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 code

So what I get is this

[3863812.3862770.4544657.4648808.4669379.4364000.4362095.4722847.4852688.5108944]
Copy the code

You 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 code

Three 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 code

As 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

  1. We pick a random number from the array and swap the number at the end of the current array
  2. Remove the trailing array just swapped and proceed to step 1
  3. 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 code

It 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 code

The results obtained

[4498337.4502249.4502001.4498385.4504714.4500172.4498057.4502210.4498232.4495643]
Copy the code

As 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 code

But 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 code

I 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 code

Also 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 code

Share 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

The above method will result in a very even red envelope each time

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