JavaScript中对循环语句的优化技巧深入探讨
循环是所有编程语言中最为重要的机制之一，几乎任何拥有实际意义的计算机程序（排序、查询等）都里不开循环。而循环也正是程序优化中非常让人头疼的一环，我们往往需要不断去优化程序的复杂度，却因循环而纠结在时间复杂度和空间复杂度之间的抉择。
在javascript中，有3种原生循环，for(){},while(){}和do{}while()，其中最为常用的要数for(){}。
然而for正是javascript工程师们在优化程序时最容易忽略的一种循环。
我们先来回顾一下for的基本知识。
javascript的for语法继承自c语言，for循环的基本语法有两种使用方法。
1.循环数组
for循环的基本语法
for(/*初始化*/2/*判断条件*/2/*循环处理*/){
//...逻辑代码
}
我们以一段实例代码来进行详细说明。
vararray=[1,2,3,4,5];
varsum =0;
for(vari=0,len=array.length;i<len;++i){
sum+=array[i];
}
console.log("Thesumofthearray\"sitemsis%d.",sum);
//=>Thesumofthearray"sitemsis15.
在这段代码中，我们首先定义并初始化了一个用存储待累加项的数组和一个总和整形变量。接下来，我们开始进行循环。在该for循环的初始化代码中，我们也定义并初始化了两个变量：i(计数器)和len(循环数组长度的别名)，当i小於len时，循环条件成立，执行逻辑代码；每次逻辑代码执行完毕以后，i自增1。
在循环的逻辑代码中，我们把当前循环的数组项加到总和变量中。
这个循环用流程图表示为如下:
从这个流程图中我们不难发现，程序中真正的循环体不仅有我们的逻辑代码，还包含了实现循环自身的执行判断和循环处理。
这样，我们的优化思路就清晰了，我们可以从四个方面进行优化。
1.循环体前的初始化代码
2.循环体中的执行判断条件
3.逻辑代码
4.逻辑代码后的处理代码
ps:其中第一点和第二点存在重要关系。
1.1优化初始化代码和执行判断条件
我们先来看看一段大家都非常熟悉的代码。
//wrong!
for(vari=02i<list.length2++i){
//...逻辑代码
}
相信现在大部分写着javascript的工程师依然使用着这段看似狠正常的循环方法，但为什?我在这里说它是错误的呢？
我们把这个循环的所有东西都拆开来看看：
1.初始化代码-这段循环只定义并初始化了一个计数器变量。
2.执行判断条件-当计数器小於list的长度时成立。
3.处理代码-计数器自增1。
我们再回顾一下上面的流程图，发现有什?倪端没？
真正的循环体不仅有我们的逻辑代码，还包含了实现循环自身的执行判断和处理代码。也就是说，i<list.length这个判断条件是每一次循环前都要执行的。而javascript中，对对象的属性或方法进行读取时，需要进行一次查询。
似乎明白了点什?了吧？这个判断条件存在两个操作：1.从list数组中查询length属性；2.比较i与list.length的大小。
假设list数组含有n个元素，则程序需要在这个循环的执行判断中进行2n次操作。
如果我们把代码改成这样：
在这段改进后的代码中，我们在循环体执行前的初始化代码中，增加定义并初始化了一个len变量，用於存储list.length的值（关於变量、表达式、指针和值的相关内容将在第二篇中讨论）。这样，我们在循环体中的执行判断中就无需再次对list数组进行属性查询，操作数为原先的一半。 以上步骤我们完善了算法的时间复杂度，而如果要继续优化空间复杂度的话，要如何做呢？如果你的逻辑代码不受循环顺序限制，那你可以尝试以下优化方式。 这段代码通过把循环顺序倒置，把i计数器从最后一个元素下标（list.length-1）开始，向前循环。以达到把循环所需变量数减到1个，而且在执行判断中，降低了变量查询的次数，减少了执行cpu指令前的耗时。 1.2优化逻辑代码 在循环中，我们得到循环当前的数组元素自然是为了对其或利用其进行一些操作，这不免会出现对该元素数次的调用。 for(vari=array.length-1;i>=0;--i){ console.log("\r\n"); Name:WillWenGunn 这段代码中，程序需要对每个数组元素的name和type属性进行查询。如果数组有n个元素，程序就进行了4n次对象查询。 相信此时你一定想到了解决方法了吧，那就是把当前数组元素的值赋值到一个变量中，然后在逻辑代码中使用它。 for(vari=array.length-1;i>=0&&(person=array[i]);--i){ console.log("\r\n"); 这样看起来的确美观了不少。 有点像emcascript5中的foreach，不过这两者之间差别狠大，这里不多做解释。 ps：感谢大家的指正，经过实验得知，如果数组内的元素是直接传值定义的，则在循环中得到值一定是值，而非指针。所以无论是定义表达式还是变量，都会有额外的内存空间请求。 1.3优化处理代码 实际上，循环体中的处理代码并没有太多东西可以进行优化，i计数器也就是自增1就足够了。 2.循环对象（object） 在javascript中，for还可以对object的属性和方法进行历遍。需要注意的是，for循环无法对对象所属的包装类型或是构造函数中原型属性、方法（prototype）进行历遍。 语法比循环数组还要简单。 我们常常这个方法来进行对对象的操作。 for(varkeyinperson){ //ifthevalueisarray,convertittoastring console.log("%s:%s",key,value); 如果你曾使用过mongodb，那你对它的query机制绝对不会陌生。因为mongodb的query机制就像是它的api的灵魂，灵活的curd操作方式为mongodb赢得了不少人气和发展动力。 而在nanodb的mongoapi实现中，query的实现方式就大面积地使用了循环对象。 var_cursor=myColl.find({ _cursor console.log(rows); 而我们需要优化的，并非循环本身，而是对你需要进行历遍的对象进行优化。 但事实并非如此，曾经使用过underscore的同学应该会知道其中的_.invert方法。这是一个相当有趣的方法，它把所传入的对象的键与值反过来。 var_inverted=_.invert(person); 如果你是需要使用循环对象来对对象的某些属性的值进行查询，那你就可以尝试一下以下方法。 varname="WillWenGunn"; var_inverted=_.invert(person); if(_inverted[name]==="name"){ 然而利用for进行对象查询并没有太大的可优化之处，一切都还需从实际需求出发。:p 接下来我们来看看其他两种循环，while(){}和do{}while()。相信任何接收过计算机科学课程的朋友都这两个循环都不会陌生。他们唯一的区别就在与执行循环体的逻辑顺序。 while(){}的执行顺序与for(){}类似，执行判断在逻辑代码之前，不过省去了初始化和处理代码。 while(sum<10){ console.log(sum); do{}while()则是把执行判断放到了逻辑代码之后，也就是“先斩后奏”。 do{ console.log(sum); while(){}与do{}while()同样不需要计数器，而是通过某些条件来判断是否执行或继续执行逻辑代码。 3.while(){}和do{}while() while(){}和do{}while()主要用於业务逻辑中，为达到某一目的而不断执行一系列操作，如任务队列。 但这两种循环是危险的，因为它们默认只受执行条件的控制，如果一旦逻辑代码内一直没有对执行判断?生任何影响，就会出现死循环。 //warning! 这样的代码无异於while(true){}，所以在使用之前，必须明确执行条件和如何对执行条件?生影响的方法。 4.善用循环控制语句 相信所有javascript工程师都使用过break语句，但continue语句却相对少用。实际上，在不少优秀的javascript开源项目中，都能发现continue的身影。 为了地?解continue语句的作用，我们还是先来看看一段实例代码 varbroadcastServer=net.createServer(); //ClientStore //ClientsBroadcastMethod for(vari=clients.length-1;i>=0;--i){ currClient=clients[i]; if(!currClient.destroyed){ //Anewclientconnected //Welcome //Messagehandle //Disconnecthandle //Bind 这段代码基於node.js的net模块实现了一个broadcastserver，在其中的broadcast方法中，我们使用了continue语句，用以实现将信息向除发?压悴サ目突Ф送獾乃?幸呀?⒘?拥目突Ф恕?/P>
代码内容相当简单，当某一客户端需要向其他客户端发?压悴ナ保?虻饔酶每突Ф怂?杂?lient对象的broadcast方法，在broadcast方法中，程序会先获取当前客户端在以缓存的客户端socket集合中的位置下标，然后对所有客户端socket进行循环发?眩?毖?芳剖?骼吹街?盎竦玫奈恢孟卤辏?蛱??鼻把?诽逯械穆呒??耄?绦?乱桓鲅?贰?/P>
相信学习过c/c++语言的工程师都会从各种地方得到这样一个忠告：“不要使用goto语句。” 而这个“臭名昭著”的goto语句其实就是一个代码流程控制器，关於goto语句的详细内容这里不会详细说明。然而javascript没有明显的goto语句，但从break语句和continue语句中，不难发现javascript中goto的影子。 这是因为break语句和continue语句允许接受由一个定义好的label名称，以进行代码跳转。 我们来看看mdn提供的实例代码。 loop1: //Outputis: 在这段实例代码中，实现了两层循环，而在每层循环外都定义了一个label，用於之后的continue语句进行调用。 第一层循环在loop1的label中，也就是说在后面的程序中，如果在continue语句或break语句选择了loop1label，就会跳出最外层循环。 通过使用循环控制语句，我们可以对原有的循环执行判断进行干涉，以至於可以构建出十分复杂的逻辑系统。说句题外话，linuxkernel中有非常多的goto语句，至於为什?还是能经常听到不要用goto语句之流的言论，就自己google吧。 5.高级循环 5.1展开循环 我们先来看看两段代码，你猜猜哪一个的性能更加。 //Case1 //Case2 这里我们来看看一种更给力的解决方案。如果一个业务环节中需要对大数据集进行迭代处理，而这个数据集从开始迭代起，数据量不会再改变，那?可以考虑?裼靡恢置?duff装置的技术。这项技术是以其的创造者tomduff的名字来命名的，这项技术最先实现於c语言。后来jeffgreenberg将其移植到javascript中，并经过andrewb.king修改并提出了一种更为高效的版本。 if(leftover>0){ 这种技术的工作原理是通过计算values的长度除以8以得到需要迭代的次数，并以math.floor()函数来保证结果为整数，然后再计算不能被8整除时的?数，并对这些元素单独进行处理，其?则8次为单次展开次数来进行迭代。 我将这种装置再加以封装，可以得到一种带有异步味道的api。 vari=0; duff([...],function(item){ 这里是一组对於以上三种迭代解决方案的性能测试及其结果。http://jsperf.com/spreaded-loop 5.2非原生循环 在任何编程语言中，能够实现循环的，不止语言所提供的原生循环语句，还可以通过其他方式来间接实现。 让我们先来温习一下高中数学的一点内容——数列的通项公式。 so then final 看了上面这段简单的演算，估计你也猜到我们将要讨论的内容了吧。是的，我们还可以使用递归来实现循环。 递归是数学和计算机科学中非常重要的一种应用方法，它是指函数在其使用时调用其自身。 在node.js社区中，递归被用来实现一种非常重要的技术：中间件技术。这是一段尚未公?训男掳姹镜webjs中的中间件实现代码。 varmiddlewares=this._usingMiddlewares; //runthenextmiddlewareifitisexists //currentmiddleware if(curr){ //Checktheroute //Thismiddlewarecannotrun //Runthemiddleware //Normalmiddlewarefunction }elseif(utils.isObject(curr.handler)&&utils.isFunc(curr.handler.emit)){ //Serverobject }else{ //Therearesomethingwrongaboutthemiddleware } //ifthemiddlewaredependonothermiddlewares, //firstmiddleware returnthis; 虽然这段代码看上去狠复杂，不过如果我们对其精简之后，就清晰许多了。 varmiddlewares=this._usingMiddlewares; //runthenextmiddlewareifitisexists //currentmiddleware if(curr){ //Checktheroute //firstmiddleware returnthis; 递归之所以可以用於中间件系统的实现，是因为递归是最适合node.js中异步i/o的程序流程响应方式。 在这段中间件实现代码中，this._usingmiddlewares为循环数组，functionnext()是循环体，其中check.test(url)为执行判断条件，而循环处理代码就是循环体中最前面的index计数器自增1和next函数自身的递归调用。
//Well
for(vari=0,len=list.length;i<len;++i){
//...
}
for(vari=list.length-1;i>=0;--i){
//...
}
vararray=[
{name:"WillWenGunn",type:"hentai"},
{name:"VillLin",type:"moegril"}
];
console.log("Name:%s",array[i].name);
console.log("He/Sheisa(n)%s",array[i].type);
}
/*=>
Name:VillLin
He/Sheisa(n)moegril
He/Sheisa(n)hentai
*/
1.array[i]
2.array[i].name
3.array[i]
4.array[i].type
vararray=[
{name:"WillWenGunn",type:"hentai"},
{name:"VillLin",type:"moegril"}
];
varperson=null;
console.log("Name:%s",person.name);
console.log("He/Sheisa(n)%s",person.type);
}
person=null;
1.array[i]=>varperson
2.person.name
3.person.type
ps：如果有什?好的建议或方法，欢迎提供。:）
for(/*初始化*/varkeyinobject){
//...逻辑代码
}
varperson={
"name" :"WillWenGunn",
"type" :"hentai",
"skill":["Programming","Photography","Speaking","etc"]
};
value=person[key];
if(valueinstanceofArray){
value=value.join(",");
}
}
/*=>
name:WillWenGunn
type:hentai
skill:Programming,Photography,Speaking,etc
*/
varmyDB =nano.db("myDB");
varmyColl=myDB.collection("myColl");
type :"repo",
language:"JavaScript"
});
.sort({
star:1
})
.toArray(function(err,rows){
if(err)
returnconsole.error(err);
});
就比如说nanodb中的nanocollection类，虽然表面看上去就是一个数组，存有所有的元素，或是一个对象，用元素的id作为键，然后对元素进行存储。
varperson={
"name":"WillWenGunn",
"type":"hentai"
};
console.log(_inverted);
/*=>
{
"WillWenGunn":"name",
"hentai" :"type"
}
*/
varperson={
"name":"WillWenGunn",
"type":"hentai"
};
console.log("Catched!");
}
//=>Catched!
当给予的条件时，便执行逻辑代码，直到条件不再成立为止。
varsum=0;
sum+=sum+1;
}
//=>15
varsum=0;
sum+=sum+1;
}while(sum<10);
//=>15
varsum=02
while(sum<10){
sum=1+12
}
//Node.jsBroadcastServer
varnet =require("net");
varutil=require("util");
broadcastServer.clients=[];
net.Socket.prototype.broadcast=function(msg){
varclients=broadcastServer.clients;
//获得发?压悴サ目突Ф嗽诩?x中的下标
varindex =clients.indexOf(this);
if(i===index){
//如果为发?压悴サ目突Ф耍?蚪崾?鼻把?诽?BR> continue;
}
currClient.write(
util.format(
"\r[EchoClient%s:%d]%s\nInput:",
currClient.remoteAddress,currClient.remotePort,msg)
);
}
}
};
broadcastServer.on("connection",function(client){
broadcastServer.clients.push(client);
client.write("[BroadcastServer]Welcome!\nInput:");
client.broadcast(client,"Joined!");
client.on("data",function(msg){
client.broadcast(msg);
client.write("\rInput:");
});
client.on("end",function(){
client.broadcast("Left!");
})
});
broadcastServer.listen(8080,function(){
console.log("BroadcastServerbound.");
});
vari,j;
for(i=0;i<3;i++){ //Thefirstforstatementislabeled"loop1"
loop2:
for(j=0;j<3;j++){ //Thesecondforstatementislabeled"loop2"
if(i==1&&j==1){
continueloop1;
}else{
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"
//Noticehowitskipsboth"i=1,j=1"and"i=1,j=2"
第二层循环在顶层循环中的loop2的label中，若在continue语句或break语句中选择了loop2label，就会回到顶层循环的循环体内。
//Setup
vararray=[
["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"]
];
functionprocess(item){
//Dosomethingwithitem
}
for(vari=array.length-1;i>=0;i--){
for(varj=array[i].length-1;j>=0;i--){
process(array[i][j]);
}
}
for(vari=array.length-1;i>=0;i=i-4){
for(varj=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(varj=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(varj=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(varj=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]);
}
}
我需要对array中的所有子数组的元素进行历遍，有两种方案，一种是我们平常所使用的方法，另一种是把循环任务展开。答案是case2性能更好，因为在每6个元素之间的执行判断都全部删除了，自然比往常的都要快。
//credit:SpeedUpUpYourSite(NewRiders,2003)
variterations=Math.floor(values.length/8);
varleftover=values.length%8;
vari=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);
functionduff(array,mapper){
varn=Math.floor(array.length/8);
varl=array.length%8;
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);
}
//...
});
bacause
a[1]=1
a[n]=2*a[n-1]+1
a[n]+1=2*a[n-1]+2
=2*(a[n-1]+1)
(a[n]+1)/(a[n-1]+1)=2
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
a[n]=2^n-1
/**
*Middlewaresrunmethod
*@param {String}urlCurrentrequesturl
*@param {Object}reqtherequestobject
*@param {Object}restheresponseobject
*@param {Function}outCompleteCallback
*@return{Function} theserver
*/
server.runMiddlewares=function(url,req,res,out){
varindex=-1;
functionnext(err){
index++;
varcurr=middlewares[index];
varcheck=newRegExp(curr.route);
if(check.test(url)){
try{
functionlater(){
debug("Amiddlewaresaysitneedtobelateron%s",url);
//Thedependenciesdonotrightnow
if(middlewares.indexOf(curr)!==middlewares.length-1){
_later(curr);
index--;
next();
}else{
debug("Amiddlewaredependencieswrong");
out();
}
}
if(utils.isFunc(curr.handler)){
curr.handler(req,res,next,later);
curr.handler.emit("request",req,res,next,later);
next();
}catch(err){
next();
}
}else{
next();
}
}else{
//Outtonextstepofthepipeline
out();
}
}
//itcanletitlatertorun
function_later(curr){
vari=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;
}
next();
};
server.runMiddlewares=function(url,req,res,out){
varindex=-1;
functionnext(err){
index++;
varcurr=middlewares[index];
varcheck=newRegExp(curr.route);
if(check.test(url)){
//runthecurrentmiddleware
curr.handler(req,res,next);
}else{
next();
}
}else{
//Outtonextstepofthepipeline
out();
}
}
next();
};
相关文章