prowyh's space

JavaScript（JScript，ECMAScript）主要作为Web的客户端编程语言，以浏览器为宿主运行环境，通过DOM（Document Object Model，文档对象模型）和BOM（Browser Object Model，浏览器对象模型）接口所呈现（expose）的对象和方法，来操纵页面的HTML元素。

早期的JavaScript代码主要完成两方面的工作，一是在客户端进行输入验证（以避免由服务器进行验证而产生的网络传输）；二是使页面产生一定的动态效果（如下拉菜单的动态显示，颜色与字体的变化等）。

随着Web 2.0以及Ajax概念的提出及相关技术的流行，Web页面应用程序化的趋势越来越明显，人们要求Web页面能够更多地体现传统桌面应用程序的风格与使用体验，而不再是传统Web页面的导航与刷新。在这种应用需求的推动下，原本只是在客户端起到补充与点缀作用的JavaScript代码，越来越成为Web程序设计的主角。而这就使得JavaScript的代码越来越庞大与复杂。此时，JavaScript代码的优化就越发显得重要。

所谓代码优化，主要是指代码所占空间（代码运行时所占的内存空间）和运行时间两个方面，早期由于机器内存资源的限制，算法研究者对空间和时间的优化给予同样的重视，空间上节省一个字节和时间上减少一次循环同样重要。现在，由于机器内存资源相对充裕（当然，只是相对而言），算法（代码）的优化，更多地集中于运行时间上，特别对JavaScript代码而言，更是如此。关于JavaScript的运行效率，Syracuse大学的Geoffrery Fox给出了一个比较结果^[1]：

 JavaScript与其它语言相比较：

 

// 功能权限及对象列表
var functorListEx = new StringBuilder();
var objectListEx = new StringBuilder();

 

// 所有INPUT元素的集合
var coll = document.getElementsByTagName("INPUT");

 

// 用于模式匹配的正则表达式
var fnRE = /functor_[0-9A-Za-z]{8}-[0-9A-Za-z]{4}-[0-9A-Za-z]{4}-[0-9A-Za-z]{4}-[0-9A-Za-z]{12}/i;
var objRE = /object_[0-9A-Za-z]{8}-[0-9A-Za-z]{4}-[0-9A-Za-z]{4}-[0-9A-Za-z]{4}-[0-9A-Za-z]{12}$/i;
var objRE_r = /radio_[0-9A-Za-z]{8}-[0-9A-Za-z]{4}-[0-9A-Za-z]{4}-[0-9A-Za-z]{4}-[0-9A-Za-z]{12}_r/i;
var objRE_a = /object_[0-9A-Za-z]{8}-[0-9A-Za-z]{4}-[0-9A-Za-z]{4}-[0-9A-Za-z]{4}-[0-9A-Za-z]{12}_a/i;
var objRE_m = /radio_[0-9A-Za-z]{8}-[0-9A-Za-z]{4}-[0-9A-Za-z]{4}-[0-9A-Za-z]{4}-[0-9A-Za-z]{12}_m/i;
var objRE_d = /radio_[0-9A-Za-z]{8}-[0-9A-Za-z]{4}-[0-9A-Za-z]{4}-[0-9A-Za-z]{4}-[0-9A-Za-z]{12}_d/i;

 

// 中间数据结构
var aryObjList = new Array();
var aryRList = new Array();
var aryAList = new Array();
var aryMList = new Array();
var aryDList = new Array();

 

for (var i = 0; i < coll.length; i++)
{
 // 通过一次遍历所有元素，填充几个中间数据结构
}

 

// 对中间数据结构的后续处理
for (var i = 0; i < aryObjList.length; i++)
{
 var _id = aryObjList[i];
 var _r = aryRList[_id] == null ? "" : aryRList[_id];
 var _a = aryAList[_id] == null ? "" : aryAList[_id];
 var _m = aryMList[_id] == null ? "" : aryMList[_id];
 var _d = aryDList[_id] == null ? "" : aryDList[_id];
 objectListEx.append(_id + ":" + _r + ":" + _a + ":" + _m + ":" + _d + ";");
}

从结果显示的运行时间上来看，未优化的代码耗时1281毫秒（例中的coll.length == 318），而优化后的代码耗时47毫秒。可见，优化的效果是明显的。

本例的优化主要是消除了代码的内循环，通过一次遍历就完成了functorListEx以及objectListEx所需要的几个中间数据结构（数组）的构建，后续的处理是由中间数据结构构建objectListEx，而aryObjList.length远远小于coll.length。所以，优化后的代码效率远远高于原来的代码。

效率分析

下面来简单分析一下优化前后的代码效率。

令代码的数据规模（即coll.length）为n。优化前，构建functorList的运行时间为O(n)，而构建objectList的运行时间为O(n³)，所以，整个代码的运行时间

T_nopt = O(n) + O(n³) = O(n³)

优化后，构建functorListEx及中间数据结构的运行时间为O(n)，构建objectListEx的运行时间为O(m)，此处m < n。所以，整个代码的运行时间

T_opt = O(n) + O(m) = O(n)

优化前，代码的运行时间为指数幂时间（这是最糟糕的！），优化后的运行时间为线性时间（这是相当好的结果！），由此可以看出，代码优化与否，差别是相当大的。

当然，代码优化是以一个能够正确工作的代码基（code base）为前提的。所以，先让程序正确地工作，然后再努力使其快速地正确工作 ^[3] 。

 

注：
1、 上述代码中的StringBuilder对象录自文献^[1]，就像C#一样，这个StringBuilder对象也是构造字符串的高效对象。

2、 由于篇幅的限制，文中省略了具体的代码实现，有兴趣者可以在笔者的blog（prowyh.spaces.live.com）中找到完整的代码实现。

参考文献
1. JavaScript高级程序设计，Nicholas C. Zaks著，曹力 张欣等译，人民邮电出版社
2. JavaScript: The Definitive Guide, 5th Edition，David Flanagan，O’Reilly
3. C++ Coding Standards, Herb Sutter, Andrei Alexandrescu, 人民邮电出版社

 

【补注】 

 

此文发于《程序员》杂志2007年第8期，并改正了杂志上几处小的排印错误。

 

今天看到aimingoo的blog 再议《JavaScript代码优化一例》，对拙文的JavaScript代码优化进行了再探讨，从多个方面进行了更细致的优化，非常感谢！

 

以前曾写过一文《JavaScript学习笔记（之一）》，是从阅读spaces.live.com以及gmail.com的JavaScript代码有感而发，谓之：现在的JavaScript代码让人看不懂。JavaScript是一个很小巧的语言，但由于兼有函数式和过程式语言的特点而使得Coding非常灵活，这也就使得代码优化大有可为的空间。

 

正好今天读完Scott Meyers的Effective系列的最后一本《Effective STL》，Item 47: Avoid producing write-only code，读来深有感触。代码如何写得既correct，又effective，同时又不失readable，确实not easy，这样的代码才可以称得上beautiful code!