js selector设计及实现（二）――完善及优化 -- JavaScript -- IT技术博客大学习 -- 共学习共进步！

您现在的位置：首页 --> JavaScript --> js selector设计及实现（二）――完善及优化

js selector设计及实现（二）――完善及优化

浏览:1384次出处信息

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的过程中，让我学习到不少知识。

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

建议继续学习：

js selector设计及实现（一）――实现思路 (阅读：1965)

QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习

<< 前一篇：js selector设计及实现（一）――实现思路

后一篇：Javascript预解析相关一则 >>

文章信息

作者：Rank 来源： never-online
标签： selector
发布时间：2010-08-12 23:34:51

建议继续学习

js selector设计及实现（一）――实现思路

近3天十大热文