关于selector选择符解析的方法

标签： Uncategorized | 发表时间：2010-07-14 11:30 | 作者：月影 winners
出处：http://www.silverna.org/blog

先推荐关于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的父元素
　1.如果不是div，遍历上一层。
　2.如果已经是顶层，排除此p。
　3.如果是div，则保存此p元素。

可以证明，这种方案的算法时间复杂度降低到Ｏ(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)的子孙
所以，除重算法如下：

  1. var divs = document.documentElement.getElementsByTagName('div');
  2. divs = makeArray(divs);
  3.  
  4. for (var i=1; i<divs.length; i++) {
  5.   if (dom_contains(divs[i-1], divs[i])) {
  6.   //除重，复杂度N。
  7.   //如果dom里前者包含后者，则移者后者
  8.   //当前循环标记-1
  9.   //结果将是
  10.   //第一轮：[1,3,4,5,6], i=1
  11.   //第二轮：[1,4,5,6] i=1
  12.   //第三轮：[1,5,6] i=1
  13.   //第四轮：[1,6] i=1
  14.   //第五轮：[1] i=1
  15.     divs.splice(i,1);
  16.     i--;
  17.   }
  18. }

可以看出这是一个O(N)复杂度的除重算法
进行完这个除重之后，只需要将除重后的div的子孙p合并起来即可
这样整个算法就简化为O(N)，成为一种更高效率的方法

相关 [selector 选择 解析] 推荐：

关于selector选择符解析的方法

- winners - 十年踪迹
先推荐关于js selector的好文章. 这里只讨论没有特殊位置关系的情况，第一种方案是常规的从左往右查. 1.先查找页面上所有的div. 2.循环所有的div，查找每个div下的p. 由于dom节点的数据结构是一棵树，对于这种查找方法，算法的时间复杂度为O(N^2)，N为节点总数. 另一种方案是从右往左查，这也是一些浏览器引擎采用的方法.

30个最常用css选择器解析

- We_Get - 博客园-首页原创精华区
你也许已经掌握了id、class、后台选择器这些基本的css选择器. 下面向大家系统的解析css中30个最常用的选择器，包括我们最头痛的浏览器兼容性问题. 掌握了它们，才能真正领略css的巨大灵活性. 星状选择符会在页面上的每一个元素上起作用. web设计者经常用它将页面中所有元素的margin和padding设置为0.

利用选择题进行信息关注度研究案例解析

- - 所有文章 - UCD大社区
如果我们想知道浏览某个页面的用户到底在看些什么. 一般往有如下几种方法：1.查看点击流数据，如CTR（Click through rate，点击转化率/点选率）、点击热图（Heat Map，可用于测试不同的布局方式、配色方案等对整体效果造成的影响）；2.眼动测试，可得到用户的注视轨迹、某一区块的注视时间、注视点个数、回扫次数，及注视热图等.

转载 选择

- bravusliu - caowumao的博客

CSS4 选择器

- iVane - 幸福收藏夹
CSS3 还没完全用上，CSS4 已经提上日程. 官方发布了 update to the working Selectors Level 4 spec，对选择器做了一些升级. 前端最大的优点就是技术更新快，可以经常学到新东西；最大的缺点也是技术更新快，要跟上潮流还真不是那么简单. 不过，这次更新有像“父选择器”这样让人兴奋的内容，让我们先睹为快，了解一下吧：.

JQuery 选择器

- - CSDN博客Web前端推荐文章
}

点击我

.    像上面这样把JavaSript代码和HTML代码混杂在一起的做法同样也非常不妥，因为它并没有将网页内容和行为分离，所以才有JQuery选择器的学习.

点击我

. //给class为demo的元素添加行为.

选择性闭嘴

- 蓓 - 土摩托日记
除了熟人之外，文青博客我追看的不多，总数不会超过10个，因为大多数这类博客的营养都欠奉. 一个是连岳，他的感情QA还是挺好看的，某些政论文字也还不错. 但这厮喜欢掺和科学的事儿，不止一次误导过读者. 就拿地震预报来说吧，他哪有资格评论. 看看这个报道，今天距离这则报道正好过去了两个月，可预报的地震仍然没有发生.

mysql选择索引

- - CSDN博客数据库推荐文章
1、尽量为用来搜索、分类或分组的数据列编制索引，不要为作为输出显示的数据列编制索引. 最适合有索引的数据列是那些在where子句中数据列，在联结子句中出现的数据列，或者是在Group by 、Order by子句中出现的数据列. select 后的数据列最好不要用索引. 2、综合考虑各数据列的维度.

jsoup select 选择器

- - 编程语言 - ITeye博客
采用CSS或类似jquery 选择器（selector）语法来处理HTML文档中的数据. 利用方法： Element.select(String selector)和 Elements.select(String selector). Jsoup的元素支持类似CSS或（jquery）的选择器语法的查找匹配的元素，可实现功能强大且鲁棒性好的查询.