preface

Today, let’s continue to talk about JS algorithm. Through the following explanation, we can understand the basic implementation of search algorithm and the performance of various implementation methods, and then find the performance difference of for loop, forEach, While. We will also learn how to do algorithm sharding through Web worker, which greatly improves the performance of the algorithm.

At the same time, I will briefly introduce the classical binary algorithm, the hash table lookup algorithm, but these are not the focus of this chapter, I will introduce the corresponding article about these advanced algorithms, interested friends can follow my column, or discuss together.

For algorithm performance, we’re going to use the getFnRunTime function from the previous chapter in the Front End Algorithm Series on how to make front end code 60 times faster. If you’re interested, you can check it out, but I’m not going to go into much detail here.

In the previous chapter, how to make front-end code 60 times faster, we simulated 19,000 pieces of data. In this chapter, I’m going to fake 1.7 million pieces of data to make the effect even more obvious, but trust me, it doesn’t matter to JS…

1. For loop search

The basic idea: Through the for loop through the array, find the index in the array for the value to be searched, and push it into the new array

Code implementation is as follows:

const getFnRunTime = require('./getRuntime'); /** * common algorithm -for loop version * @param {*} arr *function searchBy(arr, value) {
     let result = [];
    for(let i = 0, len = arr.length; i < len; i++) {
        if(arr[i] === value) { result.push(i); }}return result
 }
 getFnRunTime(searchBy, 6)
Copy the code

The results after n tests are stabilized are as follows:

2. The forEach loop

The basic idea is similar to the for loop:

@param {*} arr * @param {*} arr */function searchByForEach(arr, value) {
    let result = [];
    arr.forEach((item,i) => {
        if(item === value) { result.push(i); }})return result
}
Copy the code

It takes 21-24 milliseconds, which is not as good as a for loop (which is essentially what it is).

3. The while loop

The code is as follows:

@param {*} arr * @param {*} arr *function searchByWhile(arr, value) {
     let i = arr.length,
     result = [];
    while(i) {
        if(arr[i] === value) {
            result.push(i);
        }
        i--;
    }
    
   return result
}
Copy the code

You can see that while and for loops perform equally well, but that doesn’t mean forEach’s performance is bad and you shouldn’t use it. Foreach has less code than a for loop, but foreach relies on IEnumerable. Less efficient at run time than a for loop. However, foreach is more convenient in cases where the number of loops is uncertain, or where the number of loops needs to be counted. Moreover, the foreach code is optimized by the compiler system code, similar to the for loop.

4. Binary search

The more common application of binary search is in arrays with unique and ordered values, and we won’t compare its performance with for/while/forEach.

Basic idea: start the comparison from the middle position of the sequence. If the value of the current position is equal to the value to be searched, the search is successful. If the value to be searched is less than the value at the current position, look in the first half of the sequence; If the value to be searched is greater than the current position value, the search continues in the second half of the sequence until it is found

The code is as follows:

/** * Binary algorithm * @param {*} arr * @param {*} value */function binarySearch(arr, value) {
    let min = 0;
    let max = arr.length - 1;
    
    while (min <= max) {
      const mid = Math.floor((min + max) / 2);
  
      if (arr[mid] === value) {
        return mid;
      } else if (arr[mid] > value) {
        max = mid - 1;
      } else{ min = mid + 1; }}return 'Not Found';
  }
Copy the code

In the case of a large amount of data, dichotomy is highly efficient but unstable, which is also its small disadvantage in big data query.

5. Hash table lookup

Hash table lookup, also known as hash table lookup, can obtain the storage location of records by searching keywords without comparison. It is by establishing a definite correspondence f between the storage location of records and its keywords, so that each key key corresponds to a storage location F (key).

Hash table lookups use scenarios:

  • The best solution problem for a hash table is to find records that are equal to a given value
  • The hash lookup does not fit multiple records for the same keyword
  • Not suitable for scope search, such as looking for 18 to 22 years old students

Here’s a simplified version of hashTable to make it easier for you to understand the hash:

/** * Hash table * the following methods can cause data overwrite problems */function HashTable() { var table = []; Var loseloseHashCode =function(key) {
    var hash = 0;
    for(var i=0; i<key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash% 37}; // put this.put =function(key, value) {
    var position = loseloseHashCode(key);
    table[position] = value;
  }

  // get
  this.get = function(key) {
    return table[loseloseHashCode(key)]
  }

  // remove
  this.remove = function(key) { table[loseloseHashCode(key)] = undefined; }}Copy the code

Data conflict may occur in this method, but there are also solutions. Since there are many knowledge points involved here, I will introduce a special article in the later period:

  • Open addressing
  • Secondary detection method
  • Random detection method

Optimize using Web Worker

Through the above methods, we have known the performance and application scenarios of various algorithms. When we use the algorithm, we can also optimize it by Web worker and let the program process in parallel. For example, we can split a large array into multiple blocks, let the Web worker thread help us to process the calculation results, and finally merge the results. Through the event mechanism of the worker to the browser, the effect is very significant.

conclusion

  1. For complex array queries, for/while performs better than array methods such as forEach
  2. Order logn of binary search is a very efficient algorithm. But the downside is obvious: it has to be ordered, and it’s hard to make sure that all of our arrays are ordered. Of course you can sort the array when you build it, but you fall into the second bottleneck: it has to be an array. An array is O(1) efficient for reading, but it is O(n) efficient for inserting and deleting an element. As a result, building ordered arrays is inefficient.
  3. Basic usage and usage scenarios of hash table lookup.
  4. If possible, we can use A Web worker to optimize the algorithm and run it in parallel in the background.

Ok, this article is relatively simple, but very important, hope you have a more intuitive understanding of the search algorithm, also hope you have a better method, discuss and communicate together.

More excellent algorithms are coming, so stay tuned

Finally, welcome to join the front end technology group to discuss the charm of front end

More recommended

  • Front End Algorithm series array deweighting

  • Vue Advanced Advanced series – Play with Vue and vuex in typescript

  • In the first three years, talk about the top five books worth reading

  • With a single/multiple pages webpack4.0 lu scaffolding tools (support for jquery, react, vue, typescript)