Although algorithms are rarely used in front-end development, understanding the common algorithms and being familiar with their performance and pros and cons will take you further down the road.

preface

All of the code in this article is located in this code repository, which you can download to study, refine, and improve. On the other hand, if you think these carefully thought-out code is helpful to you, welcome to star code repository, the little star of crowdfunding bloggers.

In addition, this article uses the following functions to test the performance of the code:

module.exports = async function getFnRunTime(fn) {
    let startTime = Date.now(), endTime;
    let result = await fn();
    endTime = Date.now();
    console.log(`total time:${endTime-startTime}ms`,
                'test array\'length:' + len, result.length ); }Copy the code

To measure performance, we introduce the concept of code time complexity and use capital O() to express the algorithm time complexity notation, which we call the big O notation. In general, as n increases, the algorithm whose T(n) grows the slowest is the optimal algorithm.

1. Double for loop deweighting

If they are the same, they are skipped, if they are different, they are pushed into the array

function distinct1(arr = testArr) {
    let result = [],
           len = arr && arr.length;
    for (let i=0; i< len; i++) {
        for (let j=i+1; j< len; j++) {
            if (arr[i] === arr[j]) {
                j = ++i;
            }
        }
        result.push(arr[i])
    }
    return result
}
Copy the code

Due to the use of double-layer for loop, according to the code, the time complexity is O(n^2), and the deduplication time of 19815 pieces of data measured by the test function is 7-8ms;

2. Use indexOf and forEach/for loops to deduplicate

function distinct2(arr = testArr) {
    let result = [];
    arr.forEach((v, i, array) => {
        array.indexOf(v, i+1) === -1 && result.push(v)
    });
    return result
}
Copy the code

As you can see, the code for this method is clean and the time complexity is O(n), but there is an additional performance cost to indexOf, testing the same data: 4-5ms

3. The method of object

By using the uniqueness of the object name is eliminated

function distinct3(arr = testArr) {
    let result = [], resultObj = {}, len = arr.length;
    for(let i=0; i< len; i++) {
        let val = arr[i],
           type = typeof val;
        if(! resultObj[val]) { result.push(val); resultObj[val] = [type];
        } else if(! resultObj[val].indexOf(type) < 0) {
            result.push(val);
            resultObj[val] = [type]; }}return result
}
Copy the code

This method is fast and the time complexity is O(n), but because one more object will be created, it will bring additional memory overhead, especially in the case of large amount of data, the test time of the same data is 5ms

4. Filter method 1

Use filter and indexOf to query

function distinct4(arr = testArr) {
    return arr.filter((v, i, array) => array.indexOf(v, i+1) < 0)
}
Copy the code

The method is also simple, testing the same data takes 4-5ms, and the key optimization is to use the second parameter of indexOf to avoid unnecessary queries.

5. Filter method 2

The difference with method 4 is that the uniqueness of the array index is used to remove weight

function distinct5(arr = testArr) {
    return arr.filter((v, i, array) => array.indexOf(v) === i)
}
Copy the code

This method is the same as method 4, but the performance is much less than method 4, because every time an array is called indexOf, the entire array is looked up again, but this must be done otherwise the uniqueness of the array index cannot be taken advantage of. Time: 16ms

6. Use the SET method of ES6

function distinct6(arr = testArr) {
    return [...new Set(arr)]
}
Copy the code

This method takes 1ms, but it has great limitations. It is fast for the same type of data, but very slow for the deduplication of different types of data. This involves the underlying knowledge related to JS, which will not be introduced here, and can be introduced in the last article if needed later

Well, in fact, there are many methods to array to redo, only you can’t think of, there is no implementation, if you have a better and faster method, welcome to exchange discussion oh ~

Our vue-React-miniprogram-Node communication learning group has been joined by hundreds of front-end partners of various enterprises. Welcome to pay attention to the public account of Interesting Talk front-end, join the front-end family, and explore the boundary of front-end together