Algorithm and process control

  • The overall structure of the code is one of the main factors affecting speed.
  • Less code doesn’t mean faster, it just looks cleaner.
  • The organizational structure of the code and the way to solve specific problems are the main factors that affect the performance of the code

cycle

Looping is a common programming pattern and a key focus for improving performance

Type of loop

Four types of loops

  • The for loop
  • While loop The while loop is the simplest pretest loop
  • The do-while loop is the only post-test loop in JavaScript that consists of two parts, the body of the loop and the post-test condition. It will run at least once
var i = 0;
do {
    // Loop body
} while ( i++ < 10 )
Copy the code
  • A for-in loop can enumerate the property names of any object
for (var prop in object) {
    // Loop body
}
Copy the code


Cycle performance

Of the four loops, the for-In loop is significantly slower than the others because each iteration searches for instance or stereotype attributes simultaneously, and for the same number of iterations, the for-In loop ends up being 1/7 of the speed of the other types

Reduce iteration workload

To reduce iteration effort, a good way to increase the overall speed of a loop is to limit the number of time-consuming operations in the loop

Example:

for (var i = 0; i < items.length; i++) {
     process(items[i])
}
Copy the code

In the for loop above, each time the body of the loop is run, the following action is generated:

  1. Find the property once in the control condition (Items.length)
  2. Compare values once in the control condition (I < items.length)
  3. A comparison operation to see if the control condition evaluates to true (I < items.length == true)
  4. An increment operation (i++)
  5. An array lookup (Items [I])
  6. A function call (process(items[I]))

Optimization solution 1: Reduce The Times of querying items. Length

Example:

for (var i = 0, len = items.length; i < len; i++) {
    process(items[i])
}
Copy the code

Optimization scheme 2: reverse order search. In general, the order of the items is independent of the task to be performed, so you can use a reverse loop to evaluate the performance of each control condition by simply comparing it to 0. Is this true? –> a comparison (true?)

Example:

for(var i = items.length; i--;) {
    process(items[i])
}
Copy the code

Operation process:

  1. Comparison in one control condition (I == true)
  2. One subtraction operation (I –)
  3. An array lookup (Items [I])
  4. A function call (process(items[I]))

prompt

When the cycle complexity is O(n), reducing the amount of work per iteration is the most effective method. When the complexity is greater than O(n), the number of iterations is reduced


Reduce the number of iterations — Duff devices

Duff’s Device is a mode that limits the number of iterations of a loop. Whether a Duff Device should be used depends largely on the number of iterations

Template code:

var i = items.length % n;           // Loop the remainder first
while(i){
    process(items[i--]);
}
i = Math.floor(items.length / n);   // The loop body is 8 times the normal loop and can be written as a function call
while(i){
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
}
Copy the code

Efficiency test code:

var arr = [], times = 10000000, times2 = 10000000;
for (var i = 1; i <= times; i++) {
   arr[i] = i ;
}
console.time('pre')
var sum = 0;
for (var i = 1; i <= times; i++) {
   sum += (1 / arr[i]);
}
console.log(sum)
console.timeEnd('pre')
console.log('* * * * * * * * * * * * * * * * * * * * * * * *')
// Duff device
console.time('last')
var all = 0;
var len = times / 8, startAt = times % 8;
do {
    switch(startAt) {
        case 0: all += (1 / arr[times--]);
        case 1: all += (1 / arr[times--]);
        case 2: all += (1 / arr[times--]);
        case 3: all += (1 / arr[times--]);
        case 4: all += (1 / arr[times--]);
        case 5: all += (1 / arr[times--]);
        case 6: all += (1 / arr[times--]);
        case 7: all += (1/ arr[times--]); }}while (--len)
console.log(all)
console.timeEnd('last')
// A normal while loop
console.time('last2')
var sumall = 0;
while(times2) {
    sumall += (1 / arr[times2--]);
} 
console.log(sumall)
console.timeEnd('last2')
Copy the code


prompt

Modern browser engines have actually been optimized several times, and when the efficiency test code above runs around 1000 times, the for loop and the while loop and the Duff device run just as fast

Here’s how many times it was executed:

chrome

In Chrome, the while loop and the Duff device are significantly faster than the for loop, but the while loop and the Duff device are about the same in time, and the Duff device may even be shorter than the while loop

While > Duff device > for loop

Test 1:

Test 2:

Test 3:

IE

In Internet Explorer, the dash device is more efficient, and the for loop is less efficient than the while loop

Duff device > while > for loop

Test 1:

Test 2:

Test 3:

FireFox

It’s also similar to Internet Explorer in Firefox

Duff device > while > for loop

Test 1:

Test 2:

Test 3

Function-based iteration

Function-based iteration: forEach()

ForEach iterates through all the members of an array and executes a function

However, in all cases, loop based iteration is 8 times faster than function based iteration. Loop based iteration takes precedence over function based iteration when speed requirements are strict and function based iteration is not an appropriate choice when performance is strictly required

Conditional statements

In JavaScript, conditional statements are mainly if-else and switch

The larger the number of conditional judgments, the more likely it is to use switch statements, mainly for the sake of legibility of the code

In most cases, switch is faster than if-else. But it’s only obvious if the number of conditions is large

If-else statements can be considered split into nested if-else statements to minimize the number of conditional judgments, such as dichotomy

recursive

Recursion is the ability to make complex algorithms simpler, such as factorial functions:

function factorial(n) {
    if (n == 0) {
        return 1
    } else {
        return n * factorial(n - 1)}}Copy the code

Disadvantages of recursion

① : The potential problem with recursive functions is that unclear or lack of termination conditions will cause the function to run for a long time, that is, may produce infinite recursive calls, the user interface is suspended.

Recursive functions may also encounter browser “call stack size limits”.

Call stack limit

The number of recursions supported by the JavaScript engine is directly related to the size of the JavaScript call stack.

Internet Explorer’s call stack is related to system memory. All other browsers have a fixed number of call stack sizes

If you encounter call stack limitations, the first step should be to examine the recursive instances in your code

Recursive model

There are two types of recursion patterns worth noting. One is the “direct recursion pattern,” the factorial call written above, which is easy to detect when something goes wrong. The other is the “hidden mode”, where two functions call each other in an infinite loop, and errors in this mode are difficult to locate examples:

function first() { second() }
function second() { first() }

first();
Copy the code

The iteration

Any algorithm that can be implemented recursively can also be implemented iteratively.

Iterative algorithms usually consist of several different loops, which can improve performance by replacing long-running functions with optimized loops.

Running a loop is much less expensive than calling a function repeatedly

Iterative implementation of recursive algorithm is one of the ways to avoid stack overflow errors

Memoization

Reducing effort is the best performance optimization technique

Doing the same task more than once is simply a waste of time, and Memoization is a way to avoid redoing it.

For example, the previous common factorial recursion was improved with Memoization and greatly improved efficiency:

function memfactorial(n) {
    // Set the original memfactorial.cache
    if(! memfactorial.cache) { memfactorial.cache = {"0": 1."1": 1}}Memfactorial. Cache [n] = memfactorial. memfactorial.cache[n]
    if(! memfactorial.cache.hasOwnProperty(n)) { memfactorial.cache[n] = n * memfactorial(n -1);
    }
    return memfactorial.cache[n];
}
Copy the code

Test efficiency:

console.time('Ordinary recursion')
var six = factorial(16)
console.timeEnd('Ordinary recursion')
console.time('Memoization')
var one = factorial(16)
console.timeEnd('Memoization')
Copy the code

It is also possible to encapsulate Memoization as a base function memoize() note: This generic Memoization method is less effective than manually updated algorithms and is best implemented manually

function memoize(fundamental, cache) {
    cache = cache || {};
    var shell = function(arg) {
        if(! cache.hasOwnProperty(arg)) { cache[arg] = fundamental(arg); }return cache[arg]
    }
    return shell;
}
Copy the code

Call generic functions:

var memfactorial = memoize(factorial)
memfactorial(16)
Copy the code

section

1. Avoid for-in loops

The number of times to query items. Length can be reduced, and there is no strict order, can use reverse order search, reduce the number of operations

Point 3 to optimize when writing code: Consider Memoization to avoid double-counting when encountering stack overflows