您现在的位置:首页 --> JavaScript --> js selector设计及实现(二)――完善及优化
js selector设计及实现(二)――完善及优化
浏览:1362次 出处信息
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> |
如果除重,会有很大的性能损失。约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。
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(偶)等。
2. 表达式。 a*n+b。这个等式的结果等于当前元素在父元素下的索引。a,b变量都由用户写,也是自然数。例如2n+1(奇),2n(偶)等。
例如最常见的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可以直接用由前往后查找的策略来处理。而且还不用除重。
写个selector或许很容易,但优化确实不易。
如果你要测试一个selector的性能,用这个selector就好了。">div div~div"这个速度上是很费时的。不过一般人也没有人这么写selector,呵呵
只看别人的代码,没人解答,不写注释,也不告诉你查找策略的优先级,让你来看性能优化后的代码将是十分痛苦的事情。
而selector的好坏,很大程度上是取决于性能,而不是结构。
之所以jquery的代码(sizzle)快,据jingpu同学说是jquery作者收集了使用者最常用哪种写法,从而进行了针对性的优化,也就是上面所说的特殊优化。
这样的80/20策略是很好的一个优化方向。
也没有人敢说自己的代码绝对一定比别人的快,只能相对比较。
比如,你最后不求并集,不对结合集排序,这样肯定相对会快一些。
最后,感觉国家,感谢JK,在一起讨论selector的过程中,让我学习到不少知识。
代码可以点这里下载,测试,呵呵点此下载
此份代码已经注释,比较简单,我没去写优化的代码,之所以代码里面不写,是因为写了解释起来很绕,熟悉思路先吧,以后详细优化的文章及代码可以抽空再写。
建议继续学习:
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:js selector设计及实现(一)――实现思路
后一篇:Javascript预解析相关一则 >>
文章信息
- 作者:Rank 来源: never-online
- 标签: selector
- 发布时间:2010-08-12 23:34:51
建议继续学习
近3天十大热文
- [66] Oracle MTS模式下 进程地址与会话信
- [64] Go Reflect 性能
- [64] 如何拿下简短的域名
- [58] 【社会化设计】自我(self)部分――欢迎区
- [58] 图书馆的世界纪录
- [58] android 开发入门
- [57] IOS安全–浅谈关于IOS加固的几种方法
- [53] 视觉调整-设计师 vs. 逻辑
- [47] 界面设计速成
- [46] 读书笔记-壹百度:百度十年千倍的29条法则