This is the 10th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

This series is not what flower head, is to adjust the usual interview of some handwriting functions, test these simple implementation of the benefit is to see the basic coding level, and take a short time, more comprehensive to see how your code strength. Generally will not have a lot of boundary conditions, so the interview time is not enough, not comprehensive investigation.

If you do not know or do not know the API, ask the interviewer directly, how to use the API under Google who can immediately understand the knowledge also can not see the level. The key is in the implementation process, and your code state, habits, clarity, etc.

Note that it is simple implementation, not complete implementation, the important thing is clear concept and clear idea of implementation. It is recommended to explain clear concept first => write use cases => write pseudo code => implement specific functions, and then optimize step by step.

25. Randomly shuffling arrays

What is the problem

The problem is clear. I give you an array, and I ask you to randomly shuffle the order.

Analysis of the

A common way to write this is using math.random and array.prototype.sort ()

let arr = [1.2.3.4.5.6.7.8.9.10]

arr.sort(() = > Math.random() - 0.5);

console.log(arr)
Copy the code

The main thing is the use of these two apis

Math.random

The math.random () function returns a floating point number with pseudo-random numbers in the range 0 to less than 1, that is, up from 0 (including 0) but not including 1 (excluding 1), which you can then scale to the desired range. To achieve the initial seed selection to random number generation algorithm; It cannot be selected or reset by the user.

Math.random() does not provide random numbers as secure as passwords. Don’t use them for security matters. Web Crypto API can be used instead, and the more accurate the window. The Crypto. GetRandomValues () method.

Array.prototype.sort()

The sort() method sorts the elements of an array using an in-place algorithm and returns the array. The default sort order is built when you convert elements to strings and then compare them to a sequence of UTF-16 code unit values

  • grammar
arr.sort([compareFunction])
Copy the code
  • parameter

CompareFunction Optional – Used to specify functions in some order. If omitted, the elements are sorted by the Unicode loci of each character in the string to which they are converted. – firstEl – The first element for comparison. – secondEl – The second element for comparison.

  • The return value

Sorted array. Note that the array is sorted in place and is not copied.

  • describe

If compareFunction is specified, the array is sorted by the return value of the call to that function. That is, a and B are two elements to be compared:

  • ifcompareFunction(a, b)Less than0 ，So A will be arranged before B;
  • ifcompareFunction(a, b)Is equal to the0 ， The relative positions of A and B remain the same. Note: The ECMAScript standard does not guarantee this behavior, and not all browsers comply (e.g., Mozilla versions prior to 2003);
  • If compareFunction (a, b)Is greater than0 ， B will be lined up before A.
  • compareFunction(a, b)The same comparison must always be returned for the same input, otherwise the sorted result will be uncertain.

So we use math.random () -0.5 to return an unknown plus or minus number to get out of order.

Limitations of this approach

Moreover, through experimental verification, this method is not random with the same probability, and it can be found that each element still has a high probability to appear near its original position. This can be problematic for some raffles and other real needs.

And because V8 handles sort for performance reasons, it uses both insert sort and quicksort. Insertion sort is used when the target array is less than 10 in length. Otherwise, use quicksort.

So that’s going to create the dividing line of 10, and the probability distribution is going to be different on both sides.

So here’s a better way to do it

Fisher — Yates Shuffle

This algorithm was first proposed by Ronald Fisher and Frank Yates.

The general idea is this:

The pointer I starts at the last position, starts from the beginning and picks a random position from the current pointer I position j, I and J positions are replaced, and then the I pointer is moved forward to the head. As shown in figure

  • The pointer starts at the tail, because index starts at 0, soI - 1 first, j is randomly generated from [0-4] 5 numbers of positions, the same as the I pointer (index=4) exchange
[1.2.3.4.5]
             |
             i
Copy the code
  • Let’s say it’s randomly generatedj = 1
[1.2.3.4.5]
    |        |
    j        i
Copy the code
  • Swap can be assigned by deconstruction, notice that isThe value exchange pointer does not move
[1.5.3.4.2]
    |        |
    j        i
Copy the code
  • The next cycle I —
[1.5.3.4.2]
    |     |  
    j     i
Copy the code
  • J is random from the rest [0-3], for examplej = 2
[1.5.3.4.2]
       |  |  
       j  i
Copy the code
  • Second exchange
[1.5.4.3.2]
       |  |  
       j  i
Copy the code

  • I forward again

  • .

  • All the way to I equals equals equals zero

Handwritten implementation

function shuffle(arr) {
    let i = arr.length;
    while (i) {
        let j = Math.floor(Math.random() * i--); [arr[j], arr[i]] = [arr[i], arr[j]]; }}let arr = [1.2.3.4.5.6.7.8.9.10]
shuffle(arr)
console.log(arr)
Copy the code

Practical use

Of course, this algorithm can also be developed directly using various libraries, of course, the introduction of the way can be more elegant and more volume saving

I recommend babel-plugin-lodash

import { shuffle } from 'lodash'

shuffle([1.2.3.4])
// => [4, 1, 3, 2]
Copy the code

In addition, I would like to recommend another series of articles, very deep in simple, for the front of the advanced students are very effective, wall crack recommended!! The core concept and algorithm disassembly series remember to click like ha

That’s all for today, if you want to brush the questions with me, you can add my wechat oh, click here to make a friend Or search my wechat id, infinity_9368, you can chat and add my password “Tianwang Gai Tihu” in English. Please send me the verification message presious Tower Shock the Rever Monster, I read it and I will pass it, I will do my best to help you after I add it, but pay attention to the way you ask, I suggest you read this article first: The Wisdom of Asking questions

reference

  • www.lodashjs.com/docs/lodash…