JavaScript ノードのソート 2_JavaScript スキル

コードをコピー コードは次のとおりです:

//Inspired by
//http:/ /www.cnblogs.com/jkisjk/archive/2011/01/28/array_quickly_sortby.html
var hasDuplicate = false;
var sortBy = function(nodes){
var result = [], array = [], n = ノード.長さ, i = n, ノード;
while(node = ノード[--n]){
(array[n] = new Number(~~node.sourceIndex) )._ = ノード ;
}
array.sort(function(a,b){
if(a === b) hasDuplicate = true;
return a - b ;
});
while( i )
result[--i] = array[i]._;
return result;

ただし、標準のブラウザではIE では、XML ドキュメントにはこの属性がありません。この場合、ノードのparentNodeとnextSiblingをたどる必要がありますが、2つずつ比較するだけでは高速化できません。そこで私たちは、最も最近の共通祖先の子の順序を比較することにしました。このとき、アルゴリズムの力が反映されます。これは友人から提供された LCA に基づいた最初のバージョンです。もちろん、一般的なアイデアは依然として JK によるものです。しかし、実際の効果は満足のいくものではなく、jQuery の sortOrder よりも遅いです。問題は LCA にあると推定されます。

コードをコピー コードは次のとおりです:

//JK が提供したアイデアによるとここ
/ /http://www.cnblogs.com/rubylouvre/archive/2011/01/28/1947286.html#2020900
vartic = 0, hasDuplicate = false;
var Rage = {
// フォーム http://www.cnblogs.com/GrayZhang/archive/2010/12/29/find-closest-common-parent.html
getLCA:function(nodes){
var hash = {}、i = 0、
attr = "data-find" (ティック)、
length = nodes.length、
node、
parent、
counter = 0、
uuid;
while(node = ノード[i ]){
parent = ノード;
while(parent){
if(parent.nodeType === 1){
ブレーク;
}
uuid =parent.getAttribute(attr);
if(!uuid){
uuid = "_" ( counter); ;
hash[uuid] = {node:parent,count:1};
hash[uuid].count ;
parent =parent.parentNode; >}
}
for(ハッシュの変数 i){
if(hash[i].count === length){
return hash[i].node;
}
}
} ,
getList: function(nodes,parent){// 現在の要素から最も近い共通の祖先までのすべての祖先を取得します。これには、それ自体も含まれます。
var list = []
while (ノード){
if (ノード === 親){
ブレーク
}
リスト.unshift(ノード);
戻りリスト;
} ,
getLists : function(){
var lists = [], getList = Rage.getList, i=0,
while(node ; = ノード[i ]){
リスト = getList(node,parent);
if(list.length){
リスト[ lists.length ] = リスト;
リストを返します;
},
sortList : function(a,b){
var n = Math.min(a.length,b.length),ap,bp; (var i=0; i ap = a[i],bp = b[i]
if(ap !== bp){
while(ap = ap .nextSibling){
if(ap == = bp){
return -1
}
}
return 1
}
}
return a.length -b.length;
},
uniqueSort : function(nodes){
var length = nodes.length;
var lists = Rage .getLists(nodes,LCA);
リスト .sort(Rage.sortList);
var list, i = 0, result = []
while(list = lists[i ]); >result[result.length] list.pop() ;
}
if(result.length !== length){
result.unshift(LAC);
if(result.length ! = length){
hasDuplicate = true;
}
}
return result;
}
以下は 2 番目のバージョンです。改良により、最終的に jQuery よりも 3 倍高速になりました (テスト オブジェクトは 260 ノードを超えるドキュメントです)




コードをコピー


コードは次のとおりです:

var hasDuplicate = false;
var Rage = {
getList : function(node){
var list = [];
while(node){
if(node.nodeType === 9){
break;
}
list.unshift(node);
node = node.parentNode;
}
return list;
},
getLists : function(nodes){
var lists = [], getList = Rage.getList, i=0, node;
while(node = nodes[i ]){
lists[ lists.length ] = getList(node);
}
return lists;
},
sliceList : function(lists,num){
var result = [], i = 0, list;
while(list = lists[i ]){
list = list.slice(num);
if(list.length){
result[ result.length ] = list;
}
}
return result;
},
sortList : function(a,b){
var n = Math.min(a.length,b.length),ap,bp;
for(var i=0; i < n; i ){
ap = a[i],bp = b[i]
if(ap !== bp){
while(ap = ap.nextSibling){
if(ap === bp){
return -1
}
}
return 1
}
}
return a.length-b.length;
},
uniqueSort : function(nodes){
var length = nodes.length;
var lists = Rage.getLists(nodes);
lists.sort(function(a,b){
return a.length - b.length;
});
var depth = lists[0].length, length = lists.length, parent, cut, ii = 0;
for(var i =0; i < depth; i ){
parent = lists[0][i];
cut = true;
for(var j = 1;j < length; j ){
if(parent !== lists[j][i]){
cut = false;
break;
}
}
if(cut){
ii
}else{
break;
}
}
var LCA = lists[0][ii-1];
lists = Rage.sliceList(lists,ii);
lists.sort(Rage.sortList);
var list, i = 0, result = [];
while(list = lists[i ]){
result[result.length] = list.pop();
}
if(result.length !== length){
result.unshift(LCA);
if(result.length != length){
hasDuplicate = true;
}
}
return result;
}
}