关于selector选择符解析的方法
先推荐关于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)的子孙
所以，除重算法如下：
- var divs = document.documentElement.getElementsByTagName('div');
- divs = makeArray(divs);
- for (var i=1; i<divs.length; i++) {
- if (dom_contains(divs[i-1], divs[i])) {
- //除重，复杂度N。
- //如果dom里前者包含后者，则移者后者
- //当前循环标记-1
- //结果将是
- //第一轮：[1,3,4,5,6], i=1
- //第二轮：[1,4,5,6] i=1
- //第三轮：[1,5,6] i=1
- //第四轮：[1,6] i=1
- //第五轮：[1] i=1
- divs.splice(i,1);
- i--;
- }
- }
可以看出这是一个O(N)复杂度的除重算法
进行完这个除重之后，只需要将除重后的div的子孙p合并起来即可
这样整个算法就简化为O(N)，成为一种更高效率的方法
反复看过，还是有点疑惑……
博主在讨论的selector应该是div p而不是div > p吧？不然从p的集合开始遍历，找parentNode是不是div就好了
如果是div p，我觉得在确定时间代价的时候，好像忽略了dom_contains的代价考量，似乎对于任何两个element，这里假设他们的dom_contains时间代价都是相同的。如果把它的步骤也分解开，我直观的感觉还是从右到左的查找更快……
呃，时间有点晚了，我明天抽空把大O算一算
sorry，写错了那么明显的一处，多谢指出
改了，div p而不是div > p
这里确实是忽略了dom_contains的代价
不过dom_contains有原生的contains和compareDocumentPosition实现，所以不计这部分开销
哦，原来如此。
我又看了看htmldom的资料，contains这个原生函数确实存在，不过似乎querySelector和querySelectorAll也都有原生方法了，我可以确定的是W3C里有规定，Webkit/IE8也有实现，Gecko和低版本的IE还不确定。这样我们是不是也不用操心那个代价了呢 - -
当然getElementsByTagName的深度优先特性我也很喜欢，我在确定Web收藏夹中的每个文件夹可否再展开时用到了类似的循环方式，一次循环搞定所有文件夹！非常快：）
是的，有原生的尽量用原生的，主要还是IE6、7的兼容