关于selector选择符解析的方法

July 14th, 2010
5 comments

先推荐关于js selector的好文章
http://www.never-online.net/blog/article.asp?id=295
http://www.never-online.net/blog/article.asp?id=296

这里只讨论没有特殊位置关系的情况，第一种方案是常规的从左往右查
例如对于 div p
采用普通的查找过程如下：

1.先查找页面上所有的div
2.循环所有的div，查找每个div下的p
3.合并结果

由于dom节点的数据结构是一棵树，对于这种查找方法，算法的时间复杂度为O(N^2)，N为节点总数

另一种方案是从右往左查，这也是一些浏览器引擎采用的方法

这种方法的查找过程如下：

1.先查找页面上所有的p
2.循环所有的p，查找每个p的父元素
　1.如果不是div，遍历上一层。
　2.如果已经是顶层，排除此p。
　3.如果是div，则保存此p元素。

可以证明，这种方案的算法时间复杂度降低到Ｏ(N*logN)

但是有没有别的的方法呢？
答案是有——

还是按照从左到右的方法查，但是，先对 div div进行一次除重，即只保留最外层的div
理由是，命题div div a => div a为真

所以：

1.先找出所有的div元素，对这些div元素进行遍历，删掉那些祖先元素为div的div

这个算法看起来是O(N^2)的，但是实际上不是，因为——

document.getElementsByTagName(’div’) 获得的节点不是完全无序的，而一定是祖先在前子孙在后，并且是深度优先遍历的
所以有如下定理：
集合[div1, div2, div3... div(n)] 是 document.getElementsByTagName(’div’)的查询结果
若 div(k) 不是div1的子孙，则div(k+1) div(k+2)… div(n) 都不是div(k)的子孙
所以，除重算法如下：

  1. var divs = document.documentElement.getElementsByTagName('div');
  2. divs = makeArray(divs);
  3.  
  4. for (var i=1; i<divs.length; i++) {
  5.   if (dom_contains(divs[i-1], divs[i])) {
  6.   //除重，复杂度N。
  7.   //如果dom里前者包含后者，则移者后者
  8.   //当前循环标记-1
  9.   //结果将是
  10.   //第一轮：[1,3,4,5,6], i=1
  11.   //第二轮：[1,4,5,6] i=1
  12.   //第三轮：[1,5,6] i=1
  13.   //第四轮：[1,6] i=1
  14.   //第五轮：[1] i=1
  15.     divs.splice(i,1);
  16.     i--;
  17.   }
  18. }

可以看出这是一个O(N)复杂度的除重算法
进行完这个除重之后，只需要将除重后的div的子孙p合并起来即可
这样整个算法就简化为O(N)，成为一种更高效率的方法

月影 Uncategorized

Church计数和Lambda演算——不用“数”的自然数运算

July 6th, 2010
No comments

参考：http://shellex.info/church-nurmal-and-lambda-calculus/

  1. var zero = function(f){
  2.     return function(x){return x};
  3. }
  4.  
  5. var one = function(f){
  6.     return function(x){return f(x)};
  7. }
  8.  
  9. var two = function(f){
  10.     return function(x){return f(f(x))};
  11. }
  12.  
  13. var add = function(n, m){
  14.     return function(f){
  15.         return function(x){
  16.             return n(f)(m(f)(x));
  17.         }
  18.     }
  19. }

如果要翻译回普通“自然数”，可以用下面的

  1. var inc = function(x){
  2.     return x?++x:1;
  3. }
  4. alert(add(two,add(two,one))(inc)());

这个加法是没有用迭代和效率问题的（当然“翻译”的时候需要），另外把inc的++改成 –，就翻译成“减法”了

月影 Uncategorized

关于知识积累与知识管理——谈第九期Web标准化交流会

June 28th, 2010
4 comments

　　不知不觉，已经到第九期了，Web标准化交流会已经走过了十个月，很快即将迎来她的一岁生日吧，在这里还是要先感谢国家，然后感谢为标准化交流会默默付出的组织者们。
　　知识管理，是一个我思考了很久的问题，其实这个问题包括两个层面，一个是自我的知识收集和整理，另一个是团队的知识管理和发布，联系这两个层面之间的那个词，叫做“分享”。
　　自我知识整理和收集的目的是为了个人能力的提升，实际上学习的过程本身也就是知识在大脑中整理的过程，所以从广义上来说，一个人从出生开始，就在对自我的知识进行着管理。Web前端是一个快速发展，知识更新速度非常快的领域，它的这个特点让个人的自我知识管理变得重要，在这里，除了普通的学习、理解和记忆之外，合适的工具和合适的手段能够更好地帮助前端开发者获得知识和提升能力。每个人的方法是不一样的，有些人善于使用搜索引擎，有些人很好地利用GReader，也有些人借助于evernote和onenote等工具，不管怎么样，对于个人来说，适合自己的方法是最好的方法，寻找对自己来说最高效率的工具，帮助自己养成习惯，是快速提高自身能力的好办法。
　　讨论过程中大家还是在自我知识整理和收集这一块谈得比较多，有人说依靠工具订阅，有人说依靠搜索引擎，也有人说依靠大脑的记忆就够了。这一块我个人觉得适合自己的就是最好的，但是不能因此放弃提高要求，拒绝挖掘自己的潜力。
　　对团队来说，知识管理和团队成长息息相关。几年前在学校里带着一支技术团队的时候，就已经思考过积累与发展的问题，一个团队要成长，绝对不能每年重复前一年做的事情，要不断提高层次，而提高层次的方法，除了每个组员的经验积累之外，平台的知识积累和分享也一定会起到重要的作用。对于团队的知识管理来说，很重要的一个关键词在于”执行力“，只有推动执行，帮助大家养成习惯，一个团队才能形成收集整理发布和分享知识再继续整理发布的良性氛围，从而让知识平台成为团队成长的助推器。
　　
　　

月影 Uncategorized

忍受痛苦与坚守快乐

June 27th, 2010
1 comment

阅读蔡同学的分手的时刻，很有感触
http://jerrylovesrebol.blogspot.com/2010/06/blog-post_24.html

　　记得在交流会上，曾经不止一次讨论起这种问题：什么是专业的前端开发工程师？我认为具有专业精神的任何职业除了必须精通该职业需要的基本技能之外，首要的一点是必须很清楚地知道这个职业要做什么，以及自己想做什么。真正优秀的人，在规划他或她的职业发展道路的时候，永远是努力把自己想做的事情和职业目标相匹配，让追求职业的过程变成追求满足与快乐的过程。
　　身边有很多人，他们对技术的追求和热爱超过我，他们是天生的专家，是值得学习和尊敬的榜样，也有另一些人，他们最终发现自己并不适合软件工程师这个职位，所以选择了转行，其中也不乏有成功者。真正碌碌无为的那些人，要么是痛苦忍受，一点也不喜欢软件开发这个行业，要么是安于现状，得过且过，这两种人，向环境屈服，被环境改造，失去了自己的目标，所以也就远离的成功之路。
　　有的人以适应艰难的环境为荣，但事实上我的观点是，只有让自己快乐的环境才是最有可能让自己成功的环境，人在职场，对外界压力要有足够的韧性，但是对周围环境，不能太逆来顺受，该有的原则一定要有，如果一个环境，不适合自己，果断放弃，重新选择，对自己才是最好的。
　　迎接挑战的时候，一定要问自己内心是否快乐，自己内心的快乐，才是最适合自己发展的状态，真正的成功者，在克服别人看来很痛苦的困难时，实际上他或她的内心深处，依然坚守一份快乐。
　　造就成功的，不是忍受痛苦，而是坚守快乐。

月影 Uncategorized

模拟摇号测试

June 4th, 2010
No comments

for 刘洪波：“五连号”不是数学问题

  1. function init(n,m){
  2.     var ret = new Array(m);
  3.     var i = 0;
  4.     while(i < n){
  5.         var r = Math.floor(Math.random() * m);
  6.         if(ret[r]) continue;
  7.         ret[r] = ++i;
  8.     }
  9.     return ret;
  10. }
  11.  
  12. //alert(init(218, 786));
  13.  
  14. function testK(arr,k){
  15.     var t = 0;
  16.     for(var i = 0; i < arr.length; i++){
  17.         if(!arr[i]) t=0;
  18.         else t++;
  19.         if(t == k) return true;
  20.     }
  21.     return false;
  22. }
  23.  
  24. function test(k, n){
  25.     var r = 0;
  26.     for(var i = 0; i < n; i++){
  27.         if(testK(init(208, 786), k)) r++;
  28.     }
  29.     return [n,k,r];
  30. }
  31. var r = test(5,1000);
  32. document.write(["测试次数"+r[0],"连号长度>="+r[1],"出现连号数"+r[2]]+"<br/>")
  33. var r = test(6,1000);
  34. document.write(["测试次数"+r[0],"连号长度>="+r[1],"出现连号数"+r[2]]+"<br/>")
  35. var r = test(7,1000);
  36. document.write(["测试次数"+r[0],"连号长度>="+r[1],"出现连号数"+r[2]]+"<br/>")
  37. var r = test(8,1000);
  38. document.write(["测试次数"+r[0],"连号长度>="+r[1],"出现连号数"+r[2]]+"<br/>")
  39. var r = test(9,1000);
  40. document.write(["测试次数"+r[0],"连号长度>="+r[1],"出现连号数"+r[2]]+"<br/>")

月影 Uncategorized

漫谈抽象本质　——　从框架与库设计实战展开

April 25th, 2010
2 comments

　　四月份的Web标准化交流会昨天在北航举行，两位嘉宾给我们奉献了精彩的演讲。Giorgio关于IE9的精彩演讲给我们展望了web标准的未来以及Microsoft在这方面的决心，而爱民兄关于架构实战的演讲更让我收获良多。下面我就想接着这个话题展开谈谈我的一些体会。
　　在演讲中，爱民通过SSDownloader的例子来展示了一个框架的分析、设计到最终产出的基本过程，解释了在最终产出的结果中什么层面上属于框架、什么层面上属于库，什么层面上属于具体应用设计。这个分解比较精妙，也很容易理解，实际上一个框架的最终产出是一个完整的抽象过程，框架代表规则的限定范围，库代表构成规则基本元素的部件集合，而应用则代表具体规则下实现某类需求的具体过程。一个成熟的框架以一个稳定的规则去解决一类能解决的问题，而解决的过程则交给应用设计去通过库来实现，更关键的是，框架能让一类问题在被解决前可解决性就已经得到验证，因为框架的存在本身就是规则的存在，它具备了验证完备性的可能。这里拿房子做一个比喻，一个人购买一套商品房的时候不用等到装修完毕再去验证房子住不住得了人，因为“居住”这个基问题是框架得以解决和验证的问题，装修决定了怎么住舒服的问题，但不影响基本框架，当你入住房子时，你可以改变装修，但是不用把框架推倒重来。事先验证可用性能把产出风险降低，而这就是框架的价值体现以及架构师的作用之一。
　　从根本上讲，框架的实现是抽象的过程，在演讲中爱民提到抽象有共性抽象和本质抽象两种，但实际上我认为在现实生活中，这两种抽象的界限并没有那么清晰。什么才是本质，这个是没有定论的，从古到今，哲学家和自然科学家们都在寻找“本质”，然而至今还没有人能很有力的回答“本质”是什么。而数学家是善于抽象的一群人，他们更多地寻求共性而非本质，也许共性抽取的越多，就接近于“本质”，但谁知道呢，又有谁真正理解本质的涵义。道格拉斯的科幻小说《银河系漫游指南》中说到关于生命、宇宙的终极问题的答案是42——可没人知道42究竟意味着什么。所以，我认为现阶段抽象更多的是指共性抽象，本质抽象可能仅指接近某个状态，那个状态是什么，我不知道。
　　数学的符号抽象和计算机语言有异曲同工之妙，在数学领域，简单的加、减、乘、除、乘方、开方，是由符号表示的过程抽象，有理数、实数、向量、矩阵则是数据抽象，它们之间的预算则是规则的演变，并不耦合特定的数和符号，所以从这个意义上说，一组特定符号就能构成一个完美的框架。记得还在大学的时候，学信息论的时候，我自己把熵的定义从实数扩展到向量和矩阵，结果发现整个课本上从第一章到最后一章的所有习题几乎都能用两个公式来完美表达，现在想来这就是一个框架的魅力。在51js上曾经跟人争吵过一个问题，其实那个问题背后的原因就是在一个设计上，我把“mul”作为一个抽象符号，而对方则作为一个函数标识，所以最终导致不同的实现。这个问题本身没有绝对的对和错，两个设计者站在不同的层次和角度上看问题而已。
　　抽象本身是一个过程，数学符号或者语言表达是实现抽象的工具，计算机语言是一种非常受限的语言，然而只要这个语言是“图灵完全“的，他们在最根本的表达能力上都是没有区别的，比计算机语言更复杂的自然语言是显然能容纳图灵机的，因此不论是中国人、英国人、还是法国人、意大利人，大家在最基本的表达能力上是没有什么区别的，但是语言特性会影响思维习惯，不过这不是我想谈论的重点。
　　最后回到问题的出发点，再次强调最初的问题，不管框架还是库，软件设计本身就是一个抽象的过程，框架和库是抽象的具体产出物，用抽象思维表达问题必然会导向这样的结果，因此架构师要做的事情是寻找规律和表达问题，在这里经验很重要，另外就是要避免陷入演算细节。
　　前面说了那么多，其实只谈了实践层面上的设计抽象问题，这只是架构师工作的一小部分内容，关于系统架构师的工作范围，我同意爱民的观点，我觉得要成为一名优秀的系统架构师，我的路还很遥远……

月影 Uncategorized

浅谈数据抽象、过程抽象与泛型（一）

April 6th, 2010
2 comments

　　现代计算机语言很关注问题的数据层面，高级语言提供了很强大的数据抽象能力。例如面向过程的语言提供了对数据操作流程的抽象，而面向对象的语言则更进一步提供了构造对象、封装以及继承等能力。对于JavaScript而言，原型机制也是一种相当灵活的抽象数据的工具。
　　如果说数据抽象是与现代程序设计发展相匹配的语言能力的扩充，那么对过程的抽象或许是被现代程序设计所忽略的一种能力。范型成为一种模式，而不是一个根本的语言核心上的本质特征，至少主流语言从语法层面上对过程抽象的支持很少，这一点不得不说是一种遗憾。
　　我们说数学是定义问题和赋予符号，而计算是描述过程，过程抽象既是将过程用符号来表示，它是将数学和计算统一起来的工具。
　　举一个简单的例子，我们说乘方“pow”是一个过程，事实上它可以用一组乘法“mul”过程来描述。在数学表达层面上，我们并不关心pow和mul的数据对象是什么类型，而这在计算机语言中，通常被弱化为某种基本数据类型（例如浮点数）的基本运算操作。
　　在JavaScript中，Math.pow函数提供了计算浮点数乘方的功能，但是如果我们需要计算向量或矩阵的乘方，那么就需要另外去实现一个pow方法，或者说，Math.pow在过程上的抽象程度是很低的。
　　在表达数学问题上，我们可能会用一种超越数据类型的符号表示方法，比如我们定义乘方这个操作——

  1. define D pow E ->
  2.     E < 0 and normalize D div (D pow -E),
  3.     E = 0 and normalize D,
  4.     E > 0 and
  5.         E rem 2 and D mul (D pow (E-1)),
  6.         or (D mul D) pow (E div 2).

　　这种描述一气呵成，我们在这个问题领域内并没有深究and、 div、rem、 mul、 normalize等计算的实现，而仅仅是用符号来描述。当然并不影响过程定义本身的完备性，只是，这些符号还不能被解释成具体的可操作的步骤。下面我们来规定它——

  1. defind A and B ->
  2.     A && B.
  3. define A div B ->
  4.     (A - (A rem B)) / B.
  5. define A rem B ->
  6.     A % B.
  7. define A mul B ->
  8.     A * B.
  9. define normalize A ->
  10.     1.

　　好，现在我们分别赋予了计算符号本身的意思，但是说到这里也没有什么特别之处，因为我们只是描述了过程而没有去描述数据模型的结构。例如普通来说，A mul B等同于A * B，这几乎是废话，但是如果A、B是二阶矩阵的时候，一切就有了变化：

  1. define [[X11,X12],[X21,X22]] mul [[Y11,Y12],[Y21,Y22]] ->
  2.          [[X11 * Y11 + X12 * Y21, X11 * Y12 + X12 * Y22],
  3.           [X21 * Y11 + X22 * Y21, X21 * Y12 + X22 * Y22]].
  4. define normalize [[X11,X12],[X21,X22]] ->
  5.         [[1,0],[0,1]].

　　在这里我特别定义了一个二阶矩阵的mul和normalize方法，一个二阶矩阵是一个具有形如[[X11,X12],[X21,X22]]结构的二维数组。这个定义完成之后，你会发现pow对于矩阵来说几乎完全适用（可能还要额外定义一下div），而这是过程抽象的好处所带来的。
　　如果语言支持，实际上多定义一层mul是完全没必要的，可以直接

  1. define [[X11,X12],[X21,X22]] * [[Y11,Y12],[Y21,Y22]] ->
  2.          [[X11 * Y11 + X12 * Y21, X11 * Y12 + X12 * Y22],
  3.           [X21 * Y11 + X22 * Y21, X21 * Y12 + X22 * Y22]].

　　如果这样的话，语言就具有了同数据类型抽象相匹配的过程抽象能力，但很遗憾，目前大多数语言并不从语法层面上具备这种抽象能力（也许erlang比较接近，这篇文章里的伪代码也是类似erlang语法的），所以前面描述的这些东西，是不能够这样被直接实现的，但是，这只是一个开始，我们将在后续的文章里逐步深入介绍怎样改造程序的模式甚至怎样设计一种新的语言，以达到数据和过程抽象相匹配的符号表达能力。
最后，用一个简单实例结束这篇文章，下面的过程直接调用pow计算菲波纳契数列，具体的原理留待下一篇文章解释——

  1. define fib N ->
  2.          [[X11,X12],[Y11,Y12]] = pow([[1,1],[1,0]], N - 1), X11;

月影 Uncategorized

数据抽象和过程抽象

April 2nd, 2010
No comments

越来越觉得erlang是个好工具，天生的符号抽象能力，几乎和scheme不相上下

  1. pow(D, N) ->
  2.         pow_iter(normalize(D), D, N).
  3.  
  4. pow_iter(R, _, 0) ->
  5.         R;
  6. pow_iter(R, D, N) ->
  7.         case N rem 2 of
  8.             1 ->
  9.                 pow_iter(mul(R, D), D, N - 1);
  10.             0 ->
  11.                 pow_iter(R, mul(D, D), N div 2)
  12.         end.
  1. normalize([[_X11, _X12],[_X21, _X22]]) ->
  2.         [[1,0],[0,1]];
  3. normalize([_X,_Y]) ->
  4.         [1,1];
  5. normalize(_) ->
  6.         1.
  1. mul([[X11, X12],[X21, X22]],[[Y11,Y12],[Y21, Y22]]) ->
  2.         [[X11 * Y11 + X12 * Y21, X11 * Y12 + X12 * Y22],
  3.          [X21 * Y11 + X22 * Y21, X21 * Y12 + X22 * Y22]];
  4. mul([X1,Y1], [X2,Y2]) ->
  5.         X1 * Y2 - X2 * Y1;
  6. mul(A, B) ->
  7.         A * B.
  1. fib(N) when N > 0 ->
  2.         [[F,_],[_,_]] = pow([[1,1],[1,0]], N - 1),F;
  3. fib(_) ->
  4.         0.

月影 Uncategorized

提升javascript程序字符串操作的性能

April 1st, 2010
5 comments

脚本对字符串的操作方法不同，有时候能很大程度上影响性能
最新研究的结果表明，在脚本引擎中，拼接有意义的单词的性能要远高于无意义的字符串
因此，下面的方法能大大改善性能

  1. var s = "abdesafer";  //要拼接复制的无意义字符串
  2. var times = 500; //拼接500份
  3.  
  4. function copyStr(s, t){
  5.     var tok = "fool"; //用有意义的字符串进行拼接
  6.     var r = ""; //拼接后的字符串
  7.     for(var i = 0; i < t; i++){
  8.         r += tok;
  9.     }
  10.     r = r.replace(/fool/g, s); //替换
  11.     return r;
  12. }
  13.  
  14. var d = new Date();
  15. copyStr(s, times);
  16. alert(new Date() - d);

月影 前端技术

协作与沟通

March 28th, 2010
9 comments

　　三月份的web标准化交流会圆满结束。包括这期在内，我也参加过好几期交流会了，每期交流会都有很多的收获，在这里先赞一下所有为交流会付出了努力的组织者和积极参与交流会的同学们，大家真的为了咱web前端做了很有意义的事情。这一期北京141人报名的“盛况”也是对标准化交流会的充分肯定。
　　本人一直比较懒，所以以前也很少写什么文字，这一次还是写一点东西吧，不然也太说不过去了，哈哈。
　　本期交流会主要谈协作和提高效率的问题，这是个蛮实在的主题，也是个蛮大的话题，对于咱们来说也毫无疑问是非常重要的，毕竟我们自己在工作中离不开与人协作和沟通，而我们的工作效率，也是体现自身价值的一个重要部分。
　　在这里我大致整理一些自己有感触的内容吧
　　说到沟通技巧，具体大家都谈了很多，我觉得大部分都有道理，崔同学的吃饭理论也给我留下了很深刻的印象。而其实吃饭理论并不仅仅是吃吃饭，谈谈感情，最主要的是建立信任和培养默契。我想起曾经还在学校的时候，参加过一次企业管理的培训，那个老师并不是照搬西方的管理学经验，而是说了东方特色的管理，强调“人”的关系。当然这里并不是说只谈感情拉关系，而是说在基于做事情的规范和原则的基础上，如何建立起人与人乃至团队与团队的信任关系，从而达到目标一致，沟通顺畅，提升工作效率，而又能够让大家更快乐的工作。在沟通上，我自己的经验是充分理解对方，学会转换立场，求同存异，彼此理解，还要充分认同对方的专业领域，更重要的是发自内心的信任对方，而信任必须建立在彼此充分了解的基础上。
　　不同的团队有不同的特点，工程师相对来说大部分是具有比较谨慎的特质的，很多时候，他们不是不愿意信任你，而是本能的有一种防范心理，在这种时候，沟通方面要尽量站在他们的立场上，这样才可以得到事半功倍的效果。举一个简单的例子，当你要和后端开发人员沟通并让他们接受一个新的模板约定的时候，试着主要从节省他们工作量的角度去说，而不是从你自己对于模板管理、前后端技术分离或其他技术的角度去说。当然，这是在最初不熟悉的情况下，当他们慢慢发现你说的东西很有道理，也确实能对他们的工作产生价值的时候，信任感在不知不觉之间就已经建立起来了，下来你会发现很多事情就容易得多，你和你的团队也越来越被认同。大多数设计师则是另一种类型，他们不一定像研发那么谨慎，但是对自己的专业领域是非常自信的，在这样的情况下，和设计师沟通最好不要去质疑他们的专业领域，如果你真的对他们的设计结果有疑问，试着用不同的态度去应对，但绝对不要一上来就怀疑他们的设计思路。总的来说，和不同的人沟通有不同的技巧，在会上腾讯的leader也提到了情商问题，这确实是值得关注的。
　　在两个团队沟通的时候，如果彼此抱有完全不同的观点甚至目标，应该要把自己的东西先暂时抛在一边，共同来“求同”，而不是尝试彼此说服，那样往往很难有效果。目标要一致，就像两个杯子叠起来盛水，要先把自己杯中的水倒掉。当然这些事情，团队的leader必须要去做，而且要认真去做。沟通是方法是过程，不是目的也不是结果，结果是目标一致，一个大的团队，只有每个小团队乃至每个成员的目标一致，任务清晰，才有成功的可能。
　　上面说的其实更多是我自己在团队管理方面的想法，而个人方面，我一直觉得一个人最重要的是有远大的目标。克军总结了专业化，我觉得很有道理，但专业化有一个大前提，就是有目标、有理想。职业和业余不同，业余爱好者可以做他喜欢的，避开他不喜欢的，但职业，有时候就不得不去面对那些业余爱好者可以回避的东西。这和下棋一样，有人问职业棋手和业余棋手最大的区别是什么，我觉得两者最大的区别不在于能力高低，而在于业余棋手可以只下喜欢的棋，而职业棋手在不论多困难的时候都必须独自面对胜负，因为这是职业的代价。如果我们不喜欢一个行业，可以选择转行，但是如果我们决定在把这个行业作为“职业”走下去的话，那么，就必须面对有勇气许多东西，而勇气，应该来源于理想和追求。也许有的同学已经在追求自己的理想，而也许有些同学目前只是在一个暂时的环境里提高自己，但在任何环境里，我觉得都不能丢掉自己的理想和事业心。希望各位同学都工作开心，事业有成~

月影 Uncategorized