手机浏览 RSS 2.0 订阅 膘叔的简单人生 , 腾讯云RDS购买 | 超便宜的Vultr , 注册 | 登陆
浏览模式: 标准 | 列表2009年08月10日的文章

JavaScript中的memoization(memoizing) 技术介绍.

膘叔写在前面的话,关于memoization好象在jquery里被应用到了。但应该是1.2.6的事情了,最初的ajax是没有缓存的。后来增加了Data缓存。(记不清了,希望没有记错)
对于memoization的记忆大约是在07年,好象有一个red开头的国内的某个网站,把菲伯拉契数列用memoization实现了一遍,当时记得的测试结果,一个是3000多ms,一个是1000多ms,这已经不是一个量级的了。
于是后来,我看了一下,根据这个原理,写了一个gdata的cache,缓存一些我经常使用的函数和数据。现在当然是不用了。呵呵

以下是原文内容,它来自playgoogle的http://www.cssrain.cn/default.asp?id=1392:

最近在读《JavaScript 设计模式》一书,其中工厂模式中提到了memoizing技术,今天仔细整理了一下memoization 相关的资料,与大家共享。

memoization 一词是Donald Michie 根据拉丁语memorandum杜撰的一个词。相应的动词、过去分词、ing形式有memoiz、memoized、memoizing.

Memoization 是 一种将函数返回值缓存起来的方法,Memoization 原理非常简单,就是把函数的每次执行结果都放入一个键值对(数组也可以,视情况而定)中,在接下来的执行中,在键值对中查找是否已经有相应执行过的值,如 果有,直接返回该值,没有才 真正执行函数体的求值部分。很明显,找值,尤其是在键值对中找值,比执行函数快多了。现代 JavaScript 的开发也已经大量使用这种技术。

  •  一个简单的使用memoization的例子

我们知道,在不同的浏览器中,xmlHttpRequest对象的具体实现都不同。需要判断何种浏览器以执行具体的方法。这里就有一个使用memoization来实现的例子。

  1. function createXHRObject = function(){
  2.     //先把三个匿名函数缓存起来。
  3.     var methods = [
  4.         function(){return new XMLHttpRequest();},
  5.         function(){return new ActiveXObject("Msxml2.XMLHTTP");},
  6.         function(){return new ActiveXObject("Microsoft.XMLHTTP");}
  7.     ];
  8.     for(var i=0,len=methods.length;i<len;i++){
  9.         try{//这里用try catch来代替了条件判断,通常我不赞成这种写法
  10.             methods[i]();
  11.         }
  12.         catch(e){
  13.             continue;//如果报异常,则执行下一次循环
  14.         }
  15.         // 把createXHRObject 与能正常执行的匿名函数对应起来,再调用createXHRObject不用再检测浏览器了
  16.         createXHRObject = method[i];
  17.         return method[i];
  18.     }
  19. }

以上是一个简单的例子,第一次执 行createXHRObject()的时候,会循环判断methods 中的方法,获取一个能正确执行的,并将createXHRObject的引用指向这个方法。以后再使用这个方法的时候,不用去判断,直接自动获取正确的方 法。这省去了频繁的ajax调用中浏览器的检测。

当然,这个方法看上去效率的提升不是特别明显,我之所以写上来,是因为能比较清晰的理解memoization是如何实现的。在递归调用的时候,memoization的威力才能更好的显现。

一个递归的例子

  1. function fib(n) {
  2. if (n < 2) {
  3. return n;
  4. }
  5. return fib(n - 1) + fib(n - 2);
  6. }

 这是一个经典的斐波纳契序列,fib(20) 会把fib这个方法执行21891次,如果是fib(40),这会执行331160281次。

再看看如何使用memoization来实现,

  1.  var iterMemoFib = (function() {
  2.     var cache = [1, 1];
  3.     var fib = function(n) {
  4.         if (n >= cache.length) {
  5.             //将一个递归转换成了一个
  6.             for (var i = cache.length; i <= n; i++) {
  7.                 cache[i] = cache[i - 2] + cache[i - 1];
  8.             }
  9.         }
  10.         return cache[n-1];
  11.     }
  12.     return fib;
  13. })();

将Function的原型扩展memoize unmemoize 方法,这样你可以对任何函数实现memoize和解除memoize,当然,这个方法要慎,对一些不是频繁执行的函数,没必要缓存:

  1. Function.prototype.memoize = function() {
  2.     var pad  = {};
  3.     var self = this;
  4.     var obj  = arguments.length > 0 ? arguments[i] : null;
  5.  
  6.     var memoizedFn = function() {
  7.         // 把参数作为数组保存,作为键,把函数执行的结果作为值缓存起来
  8.         var args = [];
  9.         for (var i = 0; i < arguments.length; i++) {
  10.             args[i] = arguments[i];
  11.         }
  12.         if (!(args in pad)) {
  13.             pad[args] = self.apply(obj, arguments);
  14.         }
  15.         return pad[args];
  16.     }
  17.     memoizedFn.unmemoize = function() {
  18.         return self;
  19.     }
  20.     return memoizedFn;
  21. }
  22. Function.prototype.unmemoize = function() {
  23.     alert("Attempt to unmemoize an unmemoized function.");
  24.     return null;
  25. }
  26.  

使用方法:

fib.memoize();

参考文档:

  1. Memoizing functions in JavaScript
  2. JavaScript Memoization
  3. 提升JS性能:将递归转换为迭代
  4. MemoizationFrom Wikipedia, the free encyclopedia

项目过程中的教训总结

taobaoQA的葵儿之作,任何一个项目都会有总结,善于总结才能抓住事物的本质,否则永远浑浑噩噩的。当然,在不同的职位上,所做出的总结也会不一样,但总有可以借鉴的地方。了解团队中其他人员的问题,结合自己的问题,相信,取精华去糟粕,总可以得到一个相对来说比较适合的方案,给下次开发打下良好基础。

原文如下:

一、项目中如何正确投入测试资源?
         五彩石之后,我参与收费线,一度进入了修整期,主要工作是日常。前一阵子有个比较大的项目成立,但是由于人员不够,便决定安排日常与项目兼顾。当时我凭以 往经验认为,在项目前期阶段,我们是可以做到将两者兼顾的。但事实是,那段期间并没有按我的计划进行,由于种种原因,也可能是我的时间管理出了差错,我们 把多数时间投入到了日常,剧减了前期去理解项目需求的时间。而这一决定直接导致了在UC评审时没能很好的明确把控住,致使现阶段我们的测试成员还在为确认 项目中某些功能需求而犯愁。

        当这个风险暴露出来后,我曾反思:日常与项目兼顾,以前我可以,为什么现在做不到?是业务复杂度的问题!是时间管理的问题!是团队 合作的问题……原因可能还有很多,而我作为项目的测试负责人,前期没将这些风险完全评估出来。即使有一万个理由,也还是一个不称职的测试负责人。

总结:在项目启动时,最好能将资源完整投入,特别是业务比较复杂的项目。若确实出现资源不足,应该及时且坚决地反馈出来。

二、对UC评审的把控。
        对UC质量的把控,本该是开发人员的事。但UC写出来,看得最多的则是测试人员。所以测试人员对UC的质量是最关心的。那么从测试的角 度,什么样的UC才是可以通过评审的呢?我们现在的流程中还没有完全的标准,这就需要测试人员靠前期对需求的理解来把控。要是前期投入时间不够,自己的工 作没做足,在评审时找不出有效的问题。或是由于项目进度,虽然评审出问题,但之后马上进入下个阶段,那么将会导致后期过程中问题多、反复问,此时开发修复 完善的积极性又不高。最终致使测试理解需求准备阶段进展较累。这也是前一个问题带来的直接后果。

总结:虽然我们的流程,对特殊的项目可以适当灵活运用,但无论是什么项目,UC对测试人员的指导参考价值是第一位的。这回的教训再次告诉我,在UC评审阶段一定要把握好这个度,那么前期一定要有足够的时间去做准备。

三、项目中的沟通、协调。
          一个项目比较大,投入的开发、测试资源肯定也就增多。这期间,成员中出现了沟通上的问题,也曾为之愤愤过,也曾努力协调过……

总结:在测试团队中收集上来的问题,理应站在测试者的角度考虑,但对这类问题也要学会过滤整理。我们每个人的性 格不一样,看待问题的态度也不同,作为测试负责人,要综合平时对队友的了解,具体对待。项目组是一个整体,我们的目标是一致的。而且从产品线的角度,大家 将是长期合作的伙伴。虽然我们对事不对人,但可以寻找更好的沟通方式,不该因小问题上大和气。

        我们的项目业务比较复杂,繁多,所以周期比较长,现在发现了,还可以从某些方面做些弥补措施。但对多数项目来说还是短期的,可能问题发现了要到下个项目中才有机会去弥补。

        本来想项目结束后再来好好总结的,不过现在这些教训等到项目结束后,感觉可能就不太一样了,所以想先写出来,以督促自己,也供大家借鉴。