Loops are one of the most important mechanisms in all programming languages. Almost any computer program with practical significance (sorting, query, etc.) does not contain loops. Loops are also a very troublesome part of program optimization. We often need to constantly optimize the complexity of programs, but we are entangled in the choice between time complexity and space complexity because of loops.
In javascript, there are three kinds of native loops, for () {}, while () {} and do {} while (), among which for () {} is the most commonly used.
However, for is the type of loop that JavaScript engineers most easily ignore when optimizing programs.
Let’s first review the basic knowledge of for.
The for syntax of JavaScript is inherited from the C language. There are two ways to use the basic syntax of for loop.
1. Loop array
Basic syntax of for loop
We use a piece of example code to explain in detail.
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 to store the items to be accumulated and a sum integer variable. Next, we start looping. In the initialization code of the for loop, we also defined and initialized two variables: i (counter) and len (alias for the length of the loop array). When i is less than len, the loop condition is established and the logic code is executed; each time the logic After the code is executed, i is incremented by 1.
In the loop logic code, we add the current loop array item to the sum variable.
This cycle is represented by a flow chart as follows:
From this flow chart, we can easily find that the real loop body in the program not only includes our logic code, but also includes the execution judgment and loop processing to implement the loop itself.
In this way, our optimization ideas are clear, and we can optimize from four aspects.
1. Initialization code before the loop body
2. Execution judgment conditions in the loop body
3. Logic code
4. Processing code after the logic 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 look at a piece of code that everyone is very familiar with.
1. Initialization code - This loop only defines and initializes a counter variable.
2. Execution judgment condition - true when the counter is less than the length of the list.
3. Processing code - the counter increases by 1.
Let’s review the flow chart above again. Do we find anything wrong?
The real loop body not only contains our logic code, but also includes the execution judgment and processing code to implement the loop itself. In other words, the judgment condition i < list.length must be executed before each loop. In JavaScript, when reading the properties or methods of an object, a query is required.
You seem to understand something? There are two operations for 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:
In this improved code, we added a definition and initialized a len variable in the initialization code before the loop body is executed, which is used to store the value of list.length (about variables, expressions, pointers and values The relevant content will be discussed in the second part). In this way, we do not need to query the attributes of the list array again in the execution judgment in the loop body, and the number of operations is half of the original one.
We have improved the time complexity of the algorithm in the above steps, but if we want to continue to optimize the space complexity, what should we do? If your logic code is not restricted by the loop order, you can try the following optimization methods.
This code reverses the order of the loop, starts the i counter from the last element index (list.length - 1), and loops forward. 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-consuming before executing the CPU instruction is reduced.
1.2 Optimize logic code
In the loop, we get the current array element of the loop naturally in order to perform some operations on it or use it, which will inevitably lead to several calls to the element.
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('rn');
}
/*=>
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 performs 4n object lookups.
I believe you must have thought of a solution at this time, which is to assign the value of the current array element to a variable and then use it in the logic code.
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('rn');
}
person = null;
This does look a lot more beautiful.
It’s a bit like foreach in emcascript5, but there is a big difference between the two, so I won’t explain it here.
ps: Thank you for your corrections. After experiments, we learned that if the elements in the array are defined by direct value transfer, the value obtained in the loop must be a value, not a pointer. So whether you are defining an expression or a variable, there will be additional memory space requirements.
1.3 Optimized processing code
Actually, there is not much that can be optimized in the processing code in the loop body. It is enough for the i counter to increase by 1.
ps: If you have any good suggestions or methods, please provide them. :)
2. Loop object (object)
In javascript, for can also traverse the properties and methods of object. It should be noted that the for loop cannot traverse the packaging type to which the object belongs or the prototype properties and methods (prototype) in the constructor.
The syntax is simpler than looping an array.
We often use this method to operate objects.
for (var key in person) {
value = person[key];
// if the value is array, convert it to a string
if (value instanceof Array) {
value = value.join(', ');
}
console.log('%s: %s', key, value);
}
/*=>
name: Will Wen Gunn
type: hentai
skill : Programming, Photography, Speaking, etc
*/
If you have ever 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, the query implementation uses loop objects extensively.
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 traverse.
For example, the nanocollection class in nanodb, although it looks like an array on the surface, stores all the elements, or an object, 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 before should know the _.invert method. This is a rather interesting method that reverses the keys and values of the object passed in.
var _inverted = _.invert(person);
console.log(_inverted);
/*=>
{
'Will Wen Gunn' : 'name',
'hentai' : 'type'
}
*/
If you need to use a loop object to query the value of some properties of the object, then you can try the following method.
var name = 'Will Wen Gunn';
var _inverted = _.invert(person);
if (_inverted[name] === 'name') {
console.log('Catched!');
}
//=> Catched!
However, there is not much that can be optimized using for for object query. Everything needs to be based on actual needs. :p
Next let’s look at the other two loops, while () {} and do {} while (). I believe that anyone who has taken a computer science course will be familiar with these two cycles. The only difference between them is the logical order in which the loop body is executed.
The execution sequence of while () {} is similar to that of for () {}. The execution judgment is before the logic code, but the initialization and processing code is omitted.
When the condition is given, the logic code is executed until the condition is no longer true.
while (sum < 10) {
sum = sum 1;
}
console.log(sum);
//=> 15
do {} while () puts the execution judgment after the logic code, that is, "cut first and play later".
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 the logic code.
3. while () {} and do {} while ()
while () {} and do {} while () are mainly used in business logic to continuously perform a series of operations to achieve a certain purpose, such as task queues.
But these two types of loops are dangerous because they are only controlled by execution conditions by default. If the logic code does not have any impact on the execution judgment, an infinite loop will occur.
// warning!
while (sum < 10) {
sum = 1 12
}
Such code is tantamount to while (true) {}, so before using it, you must 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 the break statement, but the continue statement is relatively rarely used. In fact, continue can be found in many excellent JavaScript open source projects.
In order to better understand the function of the continue statement, let’s take a look at an example code first
var broadcastServer = net.createServer();
// Client Store
broadcastServer.clients = [];
// Clients Broadcast Method
net.Socket.prototype.broadcast = function(msg) {
var clients = broadcastServer.clients;
// Get the client that publishes the broadcast in the collection Standard
var index = clients.indexOf(this);
for (var i = clients.length - 1; i >= 0; --i) {
if (i === index) {
// If it is the client that publishes the broadcast, Then end the current loop
continue;
}
currClient = clients[i];
if (!currClient.destroyed) {
currClient.write(
util.format(
) 'r[Echo Client %s:%d] %snInput: ',
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 net module of node.js. In the broadcast method, we use the continue statement to distribute information to all established connections except the client that publishes the broadcast. client.
The content of the code is quite simple. When a client needs to publish a broadcast to other clients, the broadcast method of the client object corresponding to the client is called. In the broadcast method, the program will first obtain the cache of the current client. position index in the client socket collection, and then publish all client sockets in a loop. When the loop counter reaches the position index obtained previously, the logic code in the current loop body is skipped and the next loop is continued.
I believe that engineers who have studied 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. The details of the goto statement will not be explained in detail here. However, JavaScript does not have an obvious goto statement, but from the break statement and continue statement, it is not difficult to find the shadow of goto in JavaScript.
This is because the break statement and continue statement allow accepting a defined label name for code jump.
Let’s take a look at the example code provided by mdn.
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;
console.log ("i = " i ", j = " j);
}
}
}
// "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"
The first loop is in the label of loop1, which means that in the subsequent program, if the loop1 label is selected in the continue statement or break statement, the outermost loop will be jumped out.
The second-level 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.
5. Advanced loop
5.1 Unroll loop
Let’s take a look at two pieces of code first. Guess which one has better performance.
// 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]);
}
}
这里我们来看看一种更给力的解决方案。 如果一个业务环节中需要对大数据集进行迭代处理，而这个数据集从开始迭代起，数据量不会再改变， 那麼可以考虑採用一种名为 duff 装置的技术。这项技术是以其的创造者 tom duff 的名字来命名的， 这项技术最先实现於 c 语言。后来 jeff greenberg 将其移植到 javascript 中，并经过 andrew b. king 修改并提出了一种更为高效的版本。
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);
这种技术的工作原理是通过计算values的长度除以 8 以得到需要迭代的次数，并以math.floor()函数来保证结果为整数， 然后再计算不能被 8 整除时的餘数，并对这些元素单独进行处理，其餘则 8 次为单次展开次数来进行迭代。
我将这种装置再加以封装，可以得到一种带有异步味道的 api。
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 through the native loop statements provided by the language, but also indirectly through other methods.
Let us first review some content in high school mathematics - the general formula of a sequence.
so
a[n] 1 = 2 * a[n - 1] 2 [n - 1] 1) = 2
then
a[n] 1 = 2 * 2 * ... * 2 * 2
a[n] 1 = 2^n
a[n] = 2^n - 1
final
Recursion is a very important application method in mathematics and computer science. It means that a function calls itself when it is used.
In the node.js community, recursion is used to implement a very important technology: middleware technology. This is a piece of middleware implementation code in a new version of webjs that has not yet been released.
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 depend 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;
};
虽然这段代码看上去狠复杂，不过如果我们对其精简之后，就清晰许多了。
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 systems is that recursion is the most suitable program flow response method for asynchronous I/O in node.js.
In this middleware implementation code, this._usingmiddlewares is the loop array, function next() is the loop body, check.test(url) is the execution judgment condition, and the loop processing code is the front of the loop body. The index counter is incremented by 1 and the next function itself is called recursively.
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
