jQuery.unique()的实现方式
jQuery 中的 unique()
jQuery中 的 unique() 函数实现了对 DOM ELement按出现位置进行排序并去除重复元素的功能。使用方法如下:
<html>
<head></head>
<body onload="test()">
<div id="div_1">
<div id="div_2" />
</div>
<div id="div_3" />
<script type='text/javascript' src='jquery.js'></script>
<script type='text/javascript'>
function test() {
var divs = [
document.getElementById('div_3'),
document.getElementById('div_1'),
document.getElementById('div_2'),
document.getElementById('div_2'),
document.getElementById('div_1')
];
var html = show('before uinque', divs);
$.unique(divs);
html += show('after uinque', divs);
document.write(html);
}
function show(name, divs) {
var html = '';
for (var i = 0; i < divs.length; ++i) {
html += divs[i].getAttribute('id') + '<br />';
}
return name + ':<br />' + html + '<br />';
}
</script>
</body>
</html>
显示结果为:
before uinque:
div_3
div_1
div_2
div_2
div_1
after uinque:
div_1
div_2
div_3
从函数名来看,应该主要是用于去除重复元素的,为什么同时又先对 DOM Element 进行排序?为了解释这个问题,先让我们试一下不事先进行排序的情况下需要如何去除重复。
不排序的去除重复元素的实现
这里给出两种实现:
$ = function() {
return {
unique: function(elems) {
for (var i = 0; i < elems.length; ++i) {
for (var j = i + 1; j < elems.length; ++j) {
if (elems[i] === elems[j]) {
elems.splice(i--, 1);
break;
}
}
}
return elems;
},
unique2: function(elemsWithId) {
var obj = {};
for (var i = 0; i < elemsWithId.length; ++i) {
var elem = elemsWithId[i];
obj[elem.getAttribute('id')] = elem;
}
elemsWithId.length = 0;
for (var id in obj) {
elemsWithId.push(obj[id])
}
return elemsWithId;
}
}
}();
实现一使用了两重循环,算法复杂度为O(n^2);实现思路比较直观,即遍历数组,看每个元素是否与后面的元素重复,有重复则移除;但当DOM Element数量较多时性能较差,而jQuery中对大量元素进行去除重复的操作是很普遍的。
实现二将 Object 当做 HashMap/HashSet 来使用,算法复杂度为O(n);遗憾的是JavaScript中无法直接用 DOM ELement 作为 Object 的 key ,因此只能将 id 作为 key ,然而并非所有的 DOM Element 都是有 id 的,所以这种方法并不通用。而自己实现一个高性能的 HashSet(还需要自己动手计算 DOM Element 的 Hash Code ),工作量又比较大。
我们知道,基于比较的排序算法最多可以将算法复杂度降到O(nlgn),(比如结合使用快速排序和插入排序),之后遍历数组时只要比较相邻元素就可以了:
unique3: function(sortedElems) {
for ( var i = 1; i < sortedElems.length; i++ ) {
if ( sortedElems[i] === sortedElems[ i - 1 ] ) {
sortedElems.splice( i--, 1 );
}
}
return sortedElems;
}
JavaScript中又有内置的排序算法。因此,在JavaScript中,先排序后去除重复是较好的做法。
先排序后去除重复
先排序后去除重复的实现方式如下:
$ = function() {
var sort = function(a, b){
var aParents = getParents(a),
bParents = getParents(b),
al = aParents.length,
bl = bParents.length,
i, ap, bp;
for (i = 0; i < al && i < bl; i++) {
ap = aParents[i];
bp = bParents[i];
if (ap !== bp) {
return siblingCheck(ap, bp);
}
}
return i === al ?
siblingCheck(a, bp, -1) :
siblingCheck(ap, b, 1);
};
var getParents = function(elem) {
var ret = [], cur;
for (cur = elem; cur; cur = cur.parentNode) {
ret.unshift(cur);
}
return ret;
}
var siblingCheck = function(a, b, ret) {
if (a === b) { return ret; }
var cur = a;
while (cur && (cur = cur.nextSibling)) {
if (cur === b) {
return -1;
}
}
return 1;
};
return {
unique : function(elems) {
elems.sort(sort);
for ( var i = 1; i < elems.length; i++ ) {
if ( elems[i] === elems[ i - 1 ] ) {
elems.splice( i--, 1 );
}
}
return elems;
}
}
}();
这里使用了 Array 的 sort(...) 方法,并传入自定义的排序函数(sort函数)。
sort函数的做法是获取两个被比较元素的所有“直系祖宗”,从而确定了两个元素在 DOM 树中的位置;一般来说,两个元素有共同的根,那么就从根元素开始依次向下遍历,直到“分叉点”,再对分叉点的元素进行比较。如果直到遍历结束,仍未能达到分叉点(如元素a先遍历完,那么 i 就与 al 相等了),则直接将 a 与 b 当前遍历到的“祖宗”进行比较。
排序时检查重复
接下来,我们针对这样的情况进行优化:假设元素中不存在重复,那么我们就可以不执行后面的遍历并去除重复的操作了。实现如下:
$ = function() {
var hasDuplicate = true;
[0, 0].sort(function() {
hasDuplicate = false;
return 0;
});
var sort = function(a, b){
if (a === b) {
hasDuplicate = true;
return 0;
}
// Other Codes ...
};
var getParents = function(elem) {
// Other Codes ...
}
var siblingCheck = function(a, b, ret) {
// Other Codes ...
};
return {
unique : function(elems) {
elems.sort(sort);
if (hasDuplicate) {
for ( var i = 1; i < elems.length; i++ ) {
if ( elems[i] === elems[ i - 1 ] ) {
elems.splice( i--, 1 );
}
}
}
return elems;
}
}
}();
一个特殊的例外是某些浏览器可能进行了特殊的优化,那么在元素相等时可能就没有调用我们的排序函数了;这种情况下,排序时检查重复的方案就不可行。因此,如果浏览器在元素相等的情况下会调用我们的排序函数,那么就将 hasDuplicate 置为 false,并在排序过程中检查重复;否则,无论如何都视为存在重复,仍然进行遍历去除重复的操作。
使用compareDocumentPosition()进行优化
事实上,除 IE 之外浏览器都有内置的 compareDocumentPosition() 方法,用于比较两个 DOM Element 的位置,因此我们可以引入 compareDocumentPosition() 进行优化:
if (document.documentElement.compareDocumentPosition) {
var sort = function(a, b) {
if (a === b) {
hasDuplicate = true;
return 0;
}
if (!a.compareDocumentPosition || !b.compareDocumentPosition) {
return a.compareDocumentPosition ? -1 : 1;
}
return a.compareDocumentPosition(b) & 4 ? -1 : 1;
}
} else {
var sort = function(a, b) {
// Original implemention ...
}
}
a.compareDocumentPosition(b) & 4 表示取返回值的二进制表示的倒数第三位;compareDocumentPosition() 的返回值的每个二进制位表示不同的含义,其中倒数第三位表示元素 a 是否在元素 b 的 “前面”,这正是我们需要的。
最后的优化
最后,在sort的原始实现前插入一些代码,使得该函数有机会提前退出:
var sort = function(a, b){
var aParents = getParents(a),
bParents = getParents(b),
al = aParents.length,
bl = bParents.length,
ap = a.parentNode,
bp = b.parentNode,
i;
if (a === b) {
hasDuplicate = true;
return 0;
// If the nodes are siblings (or identical) we can do a quick check
} else if (ap === bp) {
return siblingCheck( a, b );
// If no parents were found then the nodes are disconnected
} else if (!ap) {
return -1;
} else if (!bp) {
return 1;
}
for (i = 0; i < al && i < bl; i++) {
ap = aParents[i];
bp = bParents[i];
if (ap !== bp) {
return siblingCheck(ap, bp);
}
}
return i === al ?
siblingCheck(a, bp, -1) :
siblingCheck(ap, b, 1);
};
以上就是 jQuery.unique() 的实现过程了。jQuery 的 unique() 在去除重复前先进行了排序,并使用了多种优化手段,实现了性能较好并且比较通用的去除重复的 DOM Element 的功能。
附件是本文中用到的一些代码。
分享到:
相关推荐
jquery.json2xml.js&&jquery.xml2json.js在jQuery的基础上实现json与xml的相互转换
这个是使用jquery.pagination.js实现分页的三种实例,包括使用jquery.pagination.js实现简单的分页,使用ajax实现无刷新分页,还有设置分页属性就行分页。。。
在官网上一直下载不下来 然后共享在这 jquery.json-2.3.min.js和jquery.json-2.3.js
jquery.pagination.js 下载,优秀的jquery分页插件,使用IP代理国外网站下载而来
jquery.form.js jquery.form.js
ztree实现模糊查询需要的依赖包:jquery.ztree.exhide.js
jquery.cookie.js下载 jquery.cookie.js下载
jquery.qrcode.min.js 二维码的jquery插件
jquery.cxselect.min.js实现Bootstrap多级下拉框联动功能的实现
jquery.min.map is a good
jquery.i18n.properties-min-1.0.9.js前端国际化文件 jquery插件,实现国际化
jquery.marquee.js demo及源文件
页面滚动监听插件,配合jquery.countup.min.js数字动画插件实现数字滚动动画
jquery.easings.min.js
ie9浏览器上不支持placeholder属性,所以必须借助插件来实现placeholder,而jquery.placeholder.js则可以实现
jquery.easing.1.3.min.js 动画效果js
jquery.i18n.properties-1.0.9.js 下载
文件压缩包里有jquery.form.js和使用说明文档 jquery表单验证插件_jquery.form.js
jquery的打印jqprint.js文件,使用jquery.jqprint.js 实现的打印功能