Close Advertisement
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后还需要除掉重复的节点（除重）。（除重代码较简单略过。）<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>
<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>
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>
<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>
//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>
论证"~"选择符由后向前找是错误结果：<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略过了。
- 调用内置的selector处理器。——因为selector我们都会解析成格式化好的数组，在解析时判断每段的selector是否符合调用内置选择器查找策略。 例如document.querySelectorAll("div.link")直接调内置的处理器来处理即可（注：ie8-不支持）。
- 加入特殊的策略，例如：这样的规则div>ul>li可以直接用由前往后查找的策略来处理。而且还不用除重。
2.如果有的话，可以回朔到最开始的selector进行确认；
3.如果关系正确则返回ID为abc元素，否则返回空。
写个selector或许很容易，但优化确实不易。
如果你要测试一个selector的性能，用这个selector就好了。">div div~div"这个速度上是很费时的。不过一般人也没有人这么写selector，呵呵
只看别人的代码，没人解答，不写注释，也不告诉你查找策略的优先级，让你来看性能优化后的代码将是十分痛苦的事情。
而selector的好坏，很大程度上是取决于性能，而不是结构。
之所以jquery的代码(sizzle)快，据jingpu同学说是jquery作者收集了使用者最常用哪种写法，从而进行了针对性的优化，也就是上面所说的特殊优化。
这样的80/20策略是很好的一个优化方向。
也没有人敢说自己的代码绝对一定比别人的快，只能相对比较。
比如，你最后不求并集，不对结合集排序，这样肯定相对会快一些。
最后，感觉国家，感谢JK，在一起讨论selector的过程中，让我学习到不少知识。
代码可以点这里下载，测试，呵呵点此下载
此份代码已经注释，比较简单，我没去写优化的代码，之所以代码里面不写，是因为写了解释起来很绕，熟悉思路先吧，以后详细优化的文章及代码可以抽空再写。
see also js selector设计及实现（一）
[最后修改由 Rank, 于 2010-07-05 19:29:56]
评论Feed: http://www.never-online.net/blog/feed.asp?q=comment&id=296
这篇日志没有评论.
