Loops are one of the most important mechanisms in all programming languages, and loops are not open in almost any computer program with practical significance (sorting, querying, etc.). Looping is also a very troublesome part of program optimization. We often need to constantly optimize the complexity of the program, but we are entangled in the choice between time complexity and space complexity due to looping.
In javascript, there are 3 native loops, for () {}, while () {} and do {} while (), and the most commonly used ones are for () {}.
However, for is the most likely loop that javascript engineers ignore when optimizing programs.
Let’s first review the basic knowledge of for.
The for syntax of javascript is inherited from the C language, and there are two ways to use the basic syntax of for loops.
1. Looping array
Basic syntax of for loop
The code copy is as follows:
for ( /* Initialization */2 /* Judgment Condition */2 /* Loop Processing */ ) {
//... Logical code
}
We will explain in detail with a piece of instance code.
The code copy is as follows:
var array = [1, 2, 3, 4, 5];
var sum = 0;
for (var i = 0, len = array.length; i < len; ++i) {
sum += array[i];
}
console.log('The sum of the array/'s items is %d.', sum);
//=> The sum of the array's items is 15.
In this code, we first define and initialize an array that stores the items to be accumulated and a sum shaping variable. Next, we start the loop. In the initialization code of this for loop, we also define and initialize two variables: i (counter) and len (alias of loop array length). When i is less than len, the loop condition is established and the logical code is executed; after each logical code is executed, i will be incremented by 1.
In the logical code of the loop, we add the array terms of the current loop to the sum variable.
This cycle is represented by the flowchart as follows:
From this flow chart, it is not difficult to find that the real loop body in the program not only contains our logical code, but also includes the execution judgment and loop processing that implements the loop itself.
In this way, our optimization ideas will be clear and we can optimize from four aspects.
1. Initialization code before the loop body
2. Execution judgment conditions in the loop body
3. Logical code
4. Processing code after logical code
ps: There is an important relationship between the first point and the second point.
1.1 Optimize initialization code and execution judgment conditions
Let's first take a look at a piece of code that everyone is very familiar with.
The code copy is as follows:
// wrong!
for (var i = 02 i < list.length2 ++i) {
//... Logical code
}
I believe that most engineers who write javascript are still using this seemingly normal loop method, but why do I say it is wrong here?
Let's take apart everything in this loop and take a look:
1. Initialize Code - This loop only defines and initializes a counter variable.
2. Execution judgment condition - It is true when the counter is less than the length of the list.
3. Processing code - The counter is incremented by 1.
Let’s review the flowchart above and find out if there is anything wrong with it?
The real loop body not only has our logical code, but also includes the execution judgment and processing code that implements the loop itself. In other words, the judgment condition i < list.length must be executed before each loop. In javascript, a query is required when reading an object's properties or methods.
You seem to understand something, right? There are two operations in this judgment condition: 1. Query the length attribute from the list array; 2. Compare the sizes of i and list.length.
Assuming that the list array contains n elements, the program needs to perform 2n operations in the execution judgment of this loop.
If we change the code to this:
The code copy is as follows:
// Well
for (var i = 0, len = list.length; i < len; ++i) {
//...
}
In this improved code, we added a definition and initialized an len variable to store the value of list.length in the initialization code before the loop body execution (the relevant content about variables, expressions, pointers and values will be discussed in the second article). In this way, we do not need to query the list array again in the execution judgment in the loop body, and the operand is half of the original one.
In the above steps, we have improved the time complexity of the algorithm, and how should we do it if we want to continue to optimize the space complexity? If your logic code is not limited by loop order, you can try the following optimization method.
The code copy is as follows:
for (var i = list.length - 1; i >= 0; --i) {
//...
}
This code loops forward by inverting the loop order, starting with the last element subscript (list.length - 1). In order to reduce the number of variables required for the loop to 1, and in the execution judgment, the number of variable queries is reduced and the time spent before executing the CPU instruction is reduced.
1.2 Optimizing logic code
In a loop, we get the current array element of the loop, naturally to do some operations on it or using it, which inevitably leads to several calls to the element.
The code copy is as follows:
var array = [
{ name: 'Will Wen Gunn', type: 'hentai' },
{ name: 'Vill Lin', type: 'moegril' }
];
for (var i = array.length - 1; i >= 0; --i) {
console.log('Name: %s', array[i].name);
console.log('He/She is a(n) %s', array[i].type);
console.log('/r/n');
}
/*=>
Name: Vill Lin
He/She is a(n) moegril
Name: Will Wen Gunn
He/She is a(n) hentai
*/
In this code, the program needs to query the name and type attributes of each array element. If the array has n elements, the program will perform 4n object queries.
The code copy is as follows:
1. array[i]
2. array[i].name
3. array[i]
4. array[i].type
I believe you must have thought of a solution at this time, that is, assign the value of the current array element to a variable, and then use it in the logical code.
The code copy is as follows:
var array = [
{ name: 'Will Wen Gunn', type: 'hentai' },
{ name: 'Vill Lin', type: 'moegril' }
];
var person = null;
for (var i = array.length - 1; i >= 0 && (person = array[i]); --i) {
console.log('Name: %s', person.name);
console.log('He/She is a(n) %s', person.type);
console.log('/r/n');
}
person = null;
This looks a lot more beautiful.
The code copy is as follows:
1. array[i] => var person
2. person.name
3. person.type
It's a bit like the foreach in emcascript5, but the difference between the two is huge, so I won't explain it here.
ps: Thank you for your correction. After experiments, I found that if the elements in the array are defined by passing values directly, the value obtained in the loop must be a value, not a pointer. So whether you define expressions or variables, there will be additional memory space requests.
1.3 Optimize the processing code
In fact, there is not much to optimize the processing code in the loop body, and the i counter is enough to increase the 1 by itself.
ps: If you have any good suggestions or methods, please provide them. :)
2. Circular object (object)
In JavaScript, for can also traverse the properties and methods of the object. It should be noted that the for loop cannot go through the wrapping type to which the object belongs or the prototype properties and methods in the constructor.
The syntax is simpler than looping arrays.
The code copy is as follows:
for (/* Initialize*/ var key in object) {
//... Logical code
}
We often use this method to operate on objects.
The code copy is as follows:
var person = {
'name' : 'Will Wen Gunn',
'type' : 'hentai',
'skill' : ['Programming', 'Photography', 'Speaking', 'etc']
};
for (var key in person) {
value = person[key];
// if the value is array, convert it to a string
if (value instance of Array) {
value = value.join(', ');
}
console.log('%s: %s', key, value);
}
/*=>
name: Will Wen Gunn
type: hentai
skill: Programming, Photography, Speaking, etc
*/
If you have used mongodb, you will definitely be familiar with its query mechanism. Because mongodb's query mechanism is like the soul of its API, the flexible curd operation method has won mongodb a lot of popularity and development momentum.
In the mongo API implementation of nanodb, query implementation uses loop objects on a large scale.
The code copy is as follows:
var myDB = nano.db('myDB');
var myColl = myDB.collection('myColl');
var _cursor = myColl.find({
type: 'repo',
language: 'JavaScript'
});
_cursor
.sort({
star: 1
})
.toArray(function(err, rows) {
if (err)
return console.error(err);
console.log(rows);
});
What we need to optimize is not the loop itself, but the optimization of the objects you need to go through.
For example, the nanocollection class in nanodb looks like an array, which contains all elements or objects, and uses the id of the element as the key and then stores the elements.
But this is not the case. Students who have used underscore should know the _.invert method. This is a pretty interesting way to reverse the keys and values of the object being passed in.
The code copy is as follows:
var person = {
'name' : 'Will Wen Gunn',
'type' : 'hentai'
};
var _inverted = _.invert(person);
console.log(_inverted);
/*=>
{
'Will Wen Gunn' : 'name',
'hentai' : 'type'
}
*/
If you need to use a loop object to query the values of certain properties of the object, you can try the following method.
The code copy is as follows:
var person = {
'name' : 'Will Wen Gunn',
'type' : 'hentai'
};
var name = 'Will Wen Gunn';
var _inverted = _.invert(person);
if (_inverted[name] === 'name') {
console.log('Catched!');
}
//=> Catched!
However, there is not much optimization to use for object query, and everything needs to be based on actual needs. : p
Next we look at the other two loops, while () {} and do {} while (). I believe that any friend who has received a computer science course will be familiar with these two cycles. The only difference between them is the logical order of execution of the loop body.
The execution order of while () {} is similar to that of for () {}. Execution judgments are performed before logical code, but the initialization and processing code are omitted.
When a condition is given, the logical code is executed until the condition no longer holds.
The code copy is as follows:
var sum = 0;
while (sum < 10) {
sum += sum + 1;
}
console.log(sum);
//=> 15
do {} while () puts the execution judgment after the logical code, which means "dead first and then play".
The code copy is as follows:
var sum = 0;
do {
sum += sum + 1;
} while (sum < 10);
console.log(sum);
//=> 15
While () {} and do {} while () also do not require a counter, but use certain conditions to determine whether to execute or continue to execute logical code.
3. while () {} and do {} while ()
while () {} and do {} while () are mainly used in business logic, and a series of operations are continuously executed to achieve a certain purpose, such as task queues.
But these two loops are dangerous because they are only controlled by execution conditions by default. If there is no impact on execution judgment in the logical code, a dead loop will occur.
The code copy is as follows:
var sum = 02
// warning!
while (sum < 10) {
sum = 1 + 12
}
Such code is no different from while (true) {}, so before use, it is necessary to clarify the execution conditions and how to affect the execution conditions.
4. Make good use of loop control statements
I believe that all javascript engineers have used break statements, but continue statements are relatively rarely used. In fact, there are many excellent JavaScript open source projects that can be found.
In order to solve the function of the continue statement, let's take a look at the example code first
The code copy is as follows:
// Node.js Broadcast Server
var net = require('net');
var util = require('util');
var broadcastServer = net.createServer();
// Client Store
broadcastServer.clients = [];
// Clients Broadcast Method
net.Socket.prototype.broadcast = function(msg) {
var clients = broadcastServer.clients;
// Get the subscript of the broadcast client in the centralized
var index = clients.indexOf(this);
for (var i = clients.length - 1; i >= 0; --i) {
if (i === index) {
// If it is a broadcast client, the current loop body will be terminated
continue;
}
currClient = clients[i];
if (!currClient.destroyed) {
currClient.write(
util.format(
'/r[Echo Client %s:%d] %s/nInput: ',
currClient.remoteAddress, currClient.remotePort, msg)
);
}
}
};
// A new client connected
broadcastServer.on('connection', function(client) {
broadcastServer.clients.push(client);
// Welcome
client.write('[Broadcast Server] Welcome!/nInput:');
client.broadcast(client, 'Joined!');
// Message handle
client.on('data', function(msg) {
client.broadcast(msg);
client.write('/rInput:');
});
// Disconnect handle
client.on('end', function() {
client.broadcast('Left!');
})
});
// Bind
broadcastServer.listen(8080, function() {
console.log('Broadcast Server bound.');
});
This code implements a broadcast server based on the node.js net module. In the broadcast method, we use the continue statement to implement all connected clients that have established connections except for the broadcast client.
The code content is quite simple. When a client needs to broadcast to other clients, the broadcast method of the corresponding client object is called. In the broadcast method, the program will first obtain the position subscript of the current client in the cached client socket collection, and then loop through all client sockets. When the loop counter reaches the position subscript obtained before, the logical code in the current loop body will be skipped and the next loop will continue.
I believe that engineers who have learned the C/C++ language will get this advice from various places: "Don't use goto statements."
This "notorious" goto statement is actually a code flow controller, and the details of the goto statement will not be explained in detail here. However, there is no obvious goto statement in javascript, but from break statements and continue statements, it is not difficult to find the shadow of goto in javascript.
This is because break statements and continue statements allow the acceptance of a defined label name for code redirection.
Let's take a look at the example code provided by mdn.
The code copy is as follows:
var i, j;
loop1:
for (i = 0; i < 3; i++) { //The first for statement is labeled "loop1"
loop2:
for (j = 0; j < 3; j++) { //The second for statement is labeled "loop2"
if (i == 1 && j == 1) {
continue loop1;
} else {
console.log("i = " + i + ", j = " + j);
}
}
}
// Output is:
// "i = 0, j = 0"
// "i = 0, j = 1"
// "i = 0, j = 2"
// "i = 1, j = 0"
// "i = 2, j = 0"
// "i = 2, j = 1"
// "i = 2, j = 2"
// Notice how it skips both "i = 1, j = 1" and "i = 1, j = 2"
In this example code, two-layer loops are implemented, and a label is defined outside each loop, which is used for calling the subsequent continue statement.
The first layer of loop is in the label of loop1, that is, in the subsequent program, if loop1 label is selected in the continue statement or break statement, the outermost loop will break.
The second layer loop is in the label of loop2 in the top-level loop. If the loop2 label is selected in the continue statement or break statement, it will return to the loop body of the top-level loop.
By using loop control statements, we can interfere with the original loop execution judgment, so that a very complex logic system can be built. To put it bluntly, there are a lot of goto statements in Linux kernel. As for why you still often hear remarks like goto statements, just google them yourself.
5. Advanced loop
5.1 Expand the loop
Let's first look at the two pieces of code, and guess which one has better performance.
The code copy is as follows:
// Setup
var array = [
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"]
];
function process(item) {
// Do something with item
}
// Case 1
for (var i = array.length - 1; i >= 0; i--) {
for (var j = array[i].length - 1; j >= 0; i--) {
process(array[i][j]);
}
}
// Case 2
for (var i = array.length - 1; i >= 0; i = i - 4) {
for (var j = array[i].length - 1; j >= 0; j = j - 6) {
process(array[i][j]);
process(array[i][j - 1]);
process(array[i][j - 2]);
process(array[i][j - 3]);
process(array[i][j - 4]);
process(array[i][j - 5]);
}
for (var j = array[i - 1].length - 1; j >= 0; j = j - 6) {
process(array[i][j]);
process(array[i][j - 1]);
process(array[i][j - 2]);
process(array[i][j - 3]);
process(array[i][j - 4]);
process(array[i][j - 5]);
}
for (var j = array[i - 2].length - 1; j >= 0; j = j - 6) {
process(array[i][j]);
process(array[i][j - 1]);
process(array[i][j - 2]);
process(array[i][j - 3]);
process(array[i][j - 4]);
process(array[i][j - 5]);
}
for (var j = array[i - 3].length - 1; j >= 0; j = j - 6) {
process(array[i][j]);
process(array[i][j - 1]);
process(array[i][j - 2]);
process(array[i][j - 3]);
process(array[i][j - 4]);
process(array[i][j - 5]);
}
}
I need to go through all the elements of the subarray in the array. There are two solutions, one is the method we usually use, and the other is to expand the loop task. The answer is that case 2 performs better, because all execution judgments between every 6 elements are deleted, which is naturally faster than usual.
Here we take a look at a more powerful solution. If a business link needs to be iteratively processed on a large data set, and the data volume will not change from the beginning of iteration, then you can consider using a technology called a duff device. This technology is named after its creator tom duff, which was first implemented in the C language. Later, jeff greenberg ported it to javascript, and modified it through andrew b. king and proposed a more efficient version.
The code copy is as follows:
//credit: Speed Up Up Your Site (New Riders, 2003)
var iterations = Math.floor(values.length / 8);
var leftover = values.length % 8;
var i = 0;
if (leftover > 0) {
do {
process(values[i++]);
} while (--leftover > 0);
}
do {
process(values[i++]);
process(values[i++]);
process(values[i++]);
process(values[i++]);
process(values[i++]);
process(values[i++]);
process(values[i++]);
process(values[i++]);
} while (--iterations > 0);
The working principle of this technique is to calculate the length of values divided by 8 to get the number of iterations that need to be iterated, and use the math.floor() function to ensure that the result is an integer, and then calculate the number that cannot be divisible by 8, and process these elements separately, and then 8 are a single expansion to iterate.
I packaged this device and got an API with an asynchronous flavor.
The code copy is as follows:
function duff(array, mapper) {
var n = Math.floor(array.length / 8);
var l = array.length % 8;
var i = 0;
if (l > 0) {
do {
mapper(array[i++]);
} while (--i > 0);
}
do {
mapper(array[i++]);
mapper(array[i++]);
mapper(array[i++]);
mapper(array[i++]);
mapper(array[i++]);
mapper(array[i++]);
mapper(array[i++]);
mapper(array[i++]);
} while (--n > 0);
}
duff([...], function(item) {
//...
});
Here is a set of performance tests and results for the above three iterative solutions. http://jsperf.com/spreaded-loop
5.2 Non-native loop
In any programming language, loops can be implemented not only indirectly in other ways, but also in other ways.
Let’s first review some content of high school mathematics - the general formula of sequences.
The code copy is as follows:
Basic
a[1] = 1
a[n] = 2 * a[n - 1] + 1
so
a[n] + 1 = 2 * a[n - 1] + 2
= 2 * (a[n - 1] + 1)
(a[n] + 1) / (a[n - 1] + 1) = 2
Then
a[n] + 1 = (a[n] + 1) / (a[n - 1] + 1) * (a[n - 1] + 1) / (a[n - 2] + 1) * ... * (a[2] + 1) / (a[1] + 1) * (a[i] + 1)
a[n] + 1 = 2 * 2 * ... * 2 * 2
a[n] + 1 = 2^n
a[n] = 2^n - 1
Final
a[n] = 2^n - 1
After reading the simple calculation above, you probably guess what we are going to discuss. Yes, we can also implement loops using recursion.
Recursion is a very important application method in mathematics and computer science, which refers to a function calling itself when it is used.
In the node.js community, recursion is used to implement a very important technology: middleware technology. This is a new version of middleware implementation code in webjs that has not yet been published.
The code copy is as follows:
/**
* Middlewares run method
* @param {String} url Current request url
* @param {Object} req the request object
* @param {Object} res the response object
* @param {Function} out Complete Callback
* @return {Function} the server
*/
server.runMiddlewares = function(url, req, res, out) {
var index = -1;
var middlewares = this._usingMiddlewares;
// run the next middleware if it is exists
function next(err) {
index++;
// current middleware
var curr = middlewares[index];
if (curr) {
var check = new RegExp(curr.route);
// Check the route
if (check.test(url)) {
try {
function later() {
debug('A middleware says it need to be later on %s', url);
// The dependencies do not right now
if (middlewares.indexOf(curr) !== middlewares.length - 1) {
_later(curr);
index--;
next();
} else {
debug('A middleware dependencies wrong');
// This middleware can not run
out();
}
}
// Run the middleware
if (utils.isFunc(curr.handler)) {
// Normal middleware function
curr.handler(req, res, next, later);
} else if (utils.isObject(curr.handler) && utils.isFunc(curr.handler.emit)) {
// Server object
curr.handler.emit('request', req, res, next, later);
} else {
// There are something wrong about the middleware
next();
}
} catch(err) {
next();
}
} else {
next();
}
} else {
// Out to next step of the pipeline
out();
}
}
// if the middleware depends on other middlewares,
// it can let it later to run
function _later(curr) {
var i = middlewares.indexOf(curr);
var _tmp1 = middlewares.slice(0, i);
_tmp1.push(middlewares[i + 1], curr);
var _tmp2 = middlewares.slice(i + 2);
[].push.apply(_tmp1, _tmp2);
middlewares = _tmp1;
}
// first middleware
next();
return this;
};
Although this code looks harsh and complicated, it will be much clearer if we simplify it.
The code copy is as follows:
server.runMiddlewares = function(url, req, res, out) {
var index = -1;
var middlewares = this._usingMiddlewares;
// run the next middleware if it is exists
function next(err) {
index++;
// current middleware
var curr = middlewares[index];
if (curr) {
var check = new RegExp(curr.route);
// Check the route
if (check.test(url)) {
// run the current middleware
curr.handler(req, res, next);
} else {
next();
}
} else {
// Out to next step of the pipeline
out();
}
}
// first middleware
next();
return this;
};
The reason why recursion can be used in the implementation of middleware system is that recursion is the most suitable method of program flow response in node.js.
In this middleware implementation code, this._usingmiddlewares is a loop array, function next() is a loop body, where check.test(url) is the execution judgment condition, and the loop processing code is the first index counter in the loop body to increment by 1 and the next function itself.