技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> JavaScript --> js selector设计及实现(二)――完善及优化

js selector设计及实现(二)――完善及优化

浏览:1362次  出处信息
5. 除掉重复的节点

5.1 考虑selector: "div div"

上面的步骤看下来还比较容易接受,那下面有头疼的问题了。

HTML代码还是上面的代码,但换个selector来考虑,假设selector是:“div div”,如果仅是用documentElement.getElementsByTagName('div'),再循环该集合获取'div'而没有形成上述的NodeFilter函数进行过滤,再合并的时候获取的节点集合就会有重复了。
为说明问题,看下面的代码:
 
以下是代码片段:
<html>
<body>
<div id="1">
  <div id="2">
    <div id="3"></div>
  </div>
  <div id="4">
    <div id="5"></div>
  </div>
</div>
</body>
</html>
<script type="text/javascript">
/**
HTMLElement Collection转化成Array
*/
var makeArray = (function(arr) {
  if (!!window.ActiveXObject) {
    return function(arr) {
      var result = [], len=arr.length;
      for (var i=0; i<len; i++) result.push(arr[i]);
      return result;
    }
  } else {
    return function(arr) {
      return Array.prototype.slice.call(arr,0); 
    }
  }
})(),

isie = !!window.ActiveXObject;

(function () {
  var divs = document.documentElement.getElementsByTagName(’div’);
  var result = [];
  for (var i=0; i<divs.length; i++) {
    result = result.concat(makeArray(divs[i].getElementsByTagName(’div’)));
  }
  alert(result.length);
  return result; //这里的result是对的吗?
})();

!isie ? alert(’正确答案是’ +document.querySelectorAll(’div div’).length) : ’’;
</script>
 
如上面所说,我们还不能单纯的concat,如果concat后还需要除掉重复的节点(除重)。(除重代码较简单略过。)
如果除重,会有很大的性能损失。约N^2的算法。

那么考虑下怎么优化下这个性能。
从DOM的树结构入手,如果说我们第一次能拿到DOM树的第一层div节点,用第一层的div节点分别调用getElementsByTagName('div'),再合并,这就是正确的结果。
问题是没有一个方法能够获取某个tagName第一层的节点集合的方法。
但是根据树的有序原理做一个优化。
用document.documentElement.getElementByTagName('div')得到的节点集合肯定是id为[1,2,3,4,5,6]的节点集合。
树节点是一个有序的结点集合,父节点肯定是在前,子节点是在后。
如果要找到"div div"的第一层的节点就可以利用这一特性来处理,看代码吧:
 
以下是代码片段:
<html>
<body>
<div id="1">
  <div id="2">
    <div id="3"></div>
  </div>
  <div id="4">
    <div id="5"></div>
  </div>
</div>
</body>
</html>
<script type="text/javascript">//<![CDATA[
/**
快速判断contains方法
*/
var dom_contains = document.compareDocumentPosition ? function(a, b) {
  return !!(a.compareDocumentPosition(b) & 16);
} : function(a, b){
  return a !== b && (a.contains ? a.contains(b) : true);
};
/**
HTMLElement Collection转化成Array
*/
var makeArray = (function(arr) {
  if (!!window.ActiveXObject) {
    return function(arr) {
      var result = [], len=arr.length;
      for (var i=0; i<len; i++) result.push(arr[i]);
      return result;
    }
  } else {
    return function(arr) {
      return Array.prototype.slice.call(arr,0); 
    }
  }
})();

(function() {

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--;
  }
}

alert(divs);

}());
//]]></script>

5.2 上述去重的缺陷
虽然上述的去重策略的性能不错,但也不是万能。上述的selector是个特例。(selector为"div div")
上述的除重策略只能用在前一个关系符是空格,随后的一个关系符也是空格的情况下使用。
例如说selector不是包含选择符的情况下,就会有问题。例如selector为"div~div div"的情况。这时用上述的策略就会有问题。(此部分不再多述,有兴趣的同学可以试一下,画个简单树图就能明白了)
那这个时候就要用传统的除重方法――即求并集。
 
以下是代码片段:
<script type="text/javascript">//<![CDATA[
Array.prototype.indexOf = function(obj,fromIdx){
  var arr = this, len = arr.length;
  fromIdx=fromIdx|0;//取整
  if(fromIdx<0) fromIdx+=len;
  if(fromIdx<0) fromIdx=0;
  for(; fromIdx < len; fromIdx ++){
    if(fromIdx in arr && arr[fromIdx] === obj) return fromIdx;
  }
  return -1;
}
Array.prototype.contains = function(a) {
  return this.indexOf(a)>-1;
};
Array.prototype.uniquelize = function(){
 var ra = [];
 for(var i = 0; i < this.length; i ++){
 if(!ra.contains(this[i])){
 ra.push(this[i]);
 }
 }
 return ra;
};
Array.prototype.union = function(b){
 return this.concat(b).uniquelize();
};
alert([1,2,3].union([2,3,4]));
//]]></script>

5.3 伪类。

关系符我们没有疑问了;属性选择符我们没有疑问了;标签元素我们也没有疑问了。
最后还有伪类。上面提到我们的总体思路都是得到HTMLElements然后通过过滤函数进行筛选,伪类这里也不另外。

伪类做的时候需要注意的也就是两个较麻烦点:
  • nth伪类。――用来做斑马线很管用。div.grid:nth-child(2n),div.grid:nth-child(2n+1),下面会详细说。
  • not伪类。――要了解not伪类。not伪类可以这么写"div div:not([className~='test'])",意味着not里可以递归selector。
5.3.1 nth

nth最常见的应用是用在制作斑马线。选择奇数行或偶数列。
没用过的同学先扫下盲,如nth-child伪类,在css selector里对nth-child的定义是:
引用
nth-child(N): matches elements on the basis of their positions within a parent element's list of child elements.
使用方法如:
#table tr:nth-child(2n+1)义为:选中id为table中tr元素的奇数行。

nth值的格式有两种:
引用
1. odd或even,非奇则偶
2. 表达式。 a*n+b。这个等式的结果等于当前元素在父元素下的索引。a,b变量都由用户写,也是自然数。例如2n+1(奇),2n(偶)等。
5.3.1.1 nth实现过程

例如最常见的query("#table tr:nth-child(2n+1)");选中table中tr元素的奇数行。

在这里过滤函数 = ((父元素里的索引值 - 1)是 % 2) 是否等于0。
那如何得到当前元素在父元素下的索引?――初始化时可以循环父元素的childNodes,添加自定义属性。过滤函数直接读这个HTMLElement的自定义属性当索引值。并为父元素置上标记,以免下次nth时再建一次索引。
 
以下是代码片段:
<table cellpadding="0" cellspacing="0" border="0" width="100%">
<tr>
  <td>test</td>
  <td>tet</td>
  <td>test</td>
</tr>
<tr id="trtest">
  <td>test nth</td>
  <td>test nth</td>
  <td>test nth</td>
</tr>
<tr>
  <td>test</td>
  <td>test</td>
  <td>test</td>
</tr>
</table>
<script>
var timestamp = new Date*1;

function buildIndex(el) {
  var p = el.parentNode;
  var c = p.childNodes;
  var index = 1;
  for (var i=0, l=c.length; i<l; i++) {
    if (c[i].tagName) c[i]._index = index++; //建索引
  }
  p._timestamp = timestamp;//时间戳
  p._length = index;//总长度
};

function getIndex(el) {
  //如果时间戳变了,则重建索引
  if (el.parentNode._timestamp!=timestamp) buildIndex(el);
  return el._index;
};

alert(getIndex(document.getElementById(’trtest’)));
</script>

6. selector的内部代码结构大致设计
selector也要考虑扩展,例如标准里伪类以后增加了怎么办?使用者要为自己加个几伪类怎么办?
最好的方式是将上面的selector实现抽象一下,将所有的过滤函数封装成配置一样的JSON对象,使得以后灵活的控制。

原来本来还画了个图的,后来一想算了,就几个方法,大致看下代码结构就好:
文后会给出详细的selector实现代码。
 
以下是代码片段:
<script type="text/javascript">
//Fox为主要命名空间
var Fox = {

  /**
  * 程序入口点,即浏览器里的document.querySelectorAll函数
  */
  query: function(selector, context) {},

  /** 
  * 通用抛异常函数
  */
  exception: function(expr) {},

  /** 
  * 跨浏览器兼容的contains函数,即一个元素是否是包含另一个节点
  */
  contains: function(a,b) {},

  /** 
  * 跨浏览器兼容的children函数,返回一个元素下的所有子节点
  */
  children: function(el) {},

  /** 
  * 得到一个树集合中第一层级的节点,即所谓的快速去重
  */
  getFirstLevelNodes: function(nodes) {},

  /**
  * 创建nth索引,方便nth查找
  */
  buildIndex: function(el) {},

  /**
  * 找到当前节点的索引值位置。
  */
  position: function(el) {},

};

//selector表达式相关的命名空间
var Expr = {

  /**
  * 表达式配置字符串方法,可以通过Util.substitute({})来替换
  */
  operators: {},

  /**
  伪类配置
  */
  pseudos: {},
  
  /**
  * 关系selector配置查找函数
  */
  relations: {},
  
  /**
  * 快捷选择符配置替换函数
  */
  shortcuts: {},

  /** 
  * 通过一个attribute来判断是用内置还是getAttribute方法来获得相应的属性值。
  */
  getAttriHandle: function(attri) {},

  /**
  * 快捷选择符解析函数,将快捷选符符解析成普通选择符
  */
  parseShortcuts: function(selector) {},

  /**
  * 将一个格式化好的attribute selector数组解析成过滤函数
  */
  parseAttributesToFilter: function(attris) {},

  /**
  * 将一个格式化好的pseudos selector数组解析成过滤函数
  */
  parsePseudosToFilter: function(pseudos) {},

  /** 
  * 除去字符串两边的空白字符
  */
  parseToFilter: function(selector) {}
};

//一些扩展函数的命名空间
var Util = {
  //这里略过,一些基础函数
};
</script>

7.解析优化

7.1
效率问题主要出现在除掉重复节点上。那反过来考虑,是否可以从右向左找来解决重复节点的问题呢?

7.2 反向查找

反向查找也就是从表达式的右往左找。

反向查找的优点:
如果由后向前查找,就可以解决查找出来节点重复的问题。不用去重。(据duoyi同学研究webkit的源码来看,webkit里css selector的解析顺序是由后往前找的。我想webkit查找策略也与此有一定关系。)
注:反向查找与正向相似,但是所有的过滤函数也得反着写。

反向查找的缺点:
假设要找的selector表达式为:"div ul~li"(ID为test结点下所有儿子为div下所有ul里所有nextSibling为li的结点集合)
而HTML的结构为
<html>
<body>
<div id="test">
  <div>
    <ol>
      <li>test</li>
      <li>test</li>
      <li>test</li>
      <li>test</li>
      <li>test</li>
    </ol>
  </div>
</div>
</body>
</html>
这里的结构是不符合上述的selector的,在这时也就可以发现从右往左找节点的不足――这个时候,所有回溯都必须查找到documentElement这一级,这也是个费时间的操作。
总结:由后向前回溯树,最坏情况会回溯到树的根结点。

7.3 正反查找两者结合?
  • 顺序解析最大的问题在除重,优势是确定性(确定性是指,层层往下找,如果找不到下个selector表达式的节点,则直接可以返回;后面的表达式就不需再找)。
  • 反向解析的最大问题则是在回溯不确定性,有可能回溯到根结点,优势则是不用除重。
如果这两者结合起来互补的话,那么肯定是效率较高的了。

分析下如何结合两者优势考虑查找策略:

正向查找的问题是重复,而重复节点的问题则是出现在关系选择符上。
只要selector出现集合都有可能出现重复节点,所以这包括:
  • 包含选择符" "。
  • 子对象选择符">"。
  • 所有的siblings选择符“~”。
而剩下的兄弟选择符“+”只有一个节点,不存在集合情况,因此不可能出现重复节点。

再思考下去,结合正向与反向的特性,这三者关系更适合 从右往左查找 有包含选择符与子对象选择符。
因为除掉包含选择符与子对象选择符,所有siblings的选择符集合,回溯节点后的结果是错误的。
举例:
selector为:#a~div div,在下列选择中正确结果应是e节点。
 
以下是代码片段:
<html>
<body>
<div id="a">
  <div id="b"></div>
  <div id="c"></div>
</div>
<div id="d"><div id="e"></div></div>
</body>
</html>

论证"~"选择符由后向前找是错误结果:
如果遇到包含选择符空格,子对象选择符">",或所有的siblings选择符“~”都反向查找,则。

1. 先查到id为a的元素;
2. a.getElementsByTagName('div'),即是b,c
3. b,c回溯“~”关系符,c符合规则。
4. c回溯,回到a。
5. 再回溯,到body,再到html,不符合规则,抛弃。这时退出。

这里出现错误是因为关系已经复杂化,上面的selector要选的是#a的侄子,而不是子孙。
所以,"~"关系符适合正向查找。

总结:直接的线性关系从后往前查找才能保证查找的确定性,正确性,否则就从前往后查找。

把整个策略可以结合总结,并理清解析思路:

引用
由前往后查找,如遇包含选择符或子对象选择符,则开始反向查找,找到的元素集合回溯之前的关系是否正确。
举例:
selector为:"#a div li~li",查找步骤为:
  • 找到id为a的元素。
  • 接下来发现第一个是包含关系符,由后往前找;
  • 分离出关系" div li~"和确定要要找的节点li
  • 找到所有的li节点。
  • 检查所有查到的li节点与关系"div li~"是否对应。
  • 回溯"~" previousSibling关系是否符合li,符合再回溯parentNode最近一级为div的节点。
  • 只有一级的包含选择符中,用contains判断。即#a.contains(div)返回是否为true。为true返回li,否则去除该li。
需要注意的是由后往前虽然不用除重,但需要查找路径,不管用什么算法,最坏的情况仍然是遍历所有与当前结点为开始的路径,这会非常费时。
举个例,selector为:>div div~div。
这需要遍历所有div的previousSibling往前回溯,最坏会直至documentElement节点,最好也会到documentElement的子节点。
想想就会非常庞大了,要是你拿新浪的页面来玩一下,浏览器肯定运算不过来。
但这如果从左往右找,或许就会好很多。

所以,我们还要用不同的策略来进行优化,例如:如果没有包含siblings的选择符("~"与"+")直接从左往右找。

7.4 其他优化。

优化上面太多太多了,我列举几条吧:
  • ID查找优化。――例如"div.a span #abc。1.这时可以先找ID为abc的元素,如果没有该元素,可以将该selector略过了。
    2.如果有的话,可以回朔到最开始的selector进行确认;
    3.如果关系正确则返回ID为abc元素,否则返回空。
  • 调用内置的selector处理器。――因为selector我们都会解析成格式化好的数组,在解析时判断每段的selector是否符合调用内置选择器查找策略。例如document.querySelectorAll("div.link")直接调内置的处理器来处理即可(注:ie8-不支持)。
  • 加入特殊的策略,例如:这样的规则div>ul>li可以直接用由前往后查找的策略来处理。而且还不用除重。
8.写完代码之后的总结

写个selector或许很容易,但优化确实不易。
如果你要测试一个selector的性能,用这个selector就好了。">div div~div"这个速度上是很费时的。不过一般人也没有人这么写selector,呵呵

只看别人的代码,没人解答,不写注释,也不告诉你查找策略的优先级,让你来看性能优化后的代码将是十分痛苦的事情。
而selector的好坏,很大程度上是取决于性能,而不是结构。
之所以jquery的代码(sizzle)快,据jingpu同学说是jquery作者收集了使用者最常用哪种写法,从而进行了针对性的优化,也就是上面所说的特殊优化。
这样的80/20策略是很好的一个优化方向。
也没有人敢说自己的代码绝对一定比别人的快,只能相对比较。
比如,你最后不求并集,不对结合集排序,这样肯定相对会快一些。

最后,感觉国家,感谢JK,在一起讨论selector的过程中,让我学习到不少知识。

代码可以点这里下载,测试,呵呵点此下载
此份代码已经注释,比较简单,我没去写优化的代码,之所以代码里面不写,是因为写了解释起来很绕,熟悉思路先吧,以后详细优化的文章及代码可以抽空再写。

建议继续学习:

  1. js selector设计及实现(一)――实现思路    (阅读:1942)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1