The time complexity of map_Improve the efficiency of code operation – the magic use of Map

Multiple nested for loops are too ugly and inefficient. Is there any way to reduce the number of nested levels? How can I get the data I want concisely and elegantly in the game, and have a good smart prompt effect?

Is there a general solution to improve operational efficiency? That’s right, es6’s Map is customized for you.

Let’s look at a simple example, array deduplication:

let myArray = [1, 2, 3, 4, 5, 2, 1];function getArray(array) {
    let newArray = [];
    for (let i = 0, l = array.length; i < l; i++) {
        for (let j = i + 1; j < l; j++) {
            if (array[i] === array[j]) {
                j = ++i;
            }
        }
        newArray.push(array[i]);
    }
    return newArray;}console.warn(getArray(myArray));

The most basic two-fold for loop is used above to traverse the array to achieve the effect of deduplication. The code runs in low efficiency and the time complexity reaches O(n2). How to optimize it into a one-fold for loop? Give it a try with Map!

Map is a new data structure in es6, which is used to represent key-value pairs. Object is also a key-value pair structure. Map is an enhancement to object. The key of object can only be string, and the key of map can be any value. We use Map to store the value of the intermediate traversal, so as to achieve the purpose of deduplication in one for loop, as follows:

let myArray = [1, 2, 3, 4, 5, 2, 1];function getArray(array) {
    let newArray = [];
    let map = new Map();
    for (let i = 0, l = array.length; i < l; i++) {
        if(typeof map.get(array[i]) == "undefined"){
            map.set(array[i], array[i]);
            newArray.push(array[i]);
        }
    }
    return newArray;}console.warn(getArray(myArray));

Obviously, a layer of for loop is reduced through Map above, which reduces the time complexity to O(n) and improves the running efficiency.

Map, a key-value pair structure (dictionary, hash table), can directly find the corresponding value according to the key name without traversal, which greatly improves the efficiency of the search. Our commonly used object and array structures also have the same effect, but the Map function is more powerful, and the intelligent prompt effect of ts is better.

Theoretical analysis: Why use Map to improve operating efficiency? After careful consideration, we found that this contains an important theoretical knowledge of computer – space for time! In computer theory, for an algorithm, its time responsibility and space complexity are opposite. The simple understanding is that the more space it takes up, the faster it runs, and the less space it takes up, the slower it runs. The above Map is the extra storage space opened up to save some intermediate states, thereby reducing the 2-fold for loop to a 1-fold for loop, reducing the running time.