07月14, 2010

关于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的父元素
    如果不是div,遍历上一层。
    如果已经是顶层,排除此p。
    如果是div,则保存此p元素。

可以证明,这种方案的算法时间复杂度降低到O(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),成为一种更高效率的方法

本文链接:https://www.h5jun.com/post/关于selector选择符解析的方法.html

-- EOF --

Comments