【经验】一道面试：点击排序（要求最优性能）
post by:天之骄子 2013-7-20 23:00
题目如下：
页面有N个BOX（每个BOX都有各自ID），初始时点击量count都为0，点击后，页面的BOX按照点击量，从大到小重新排序，要求：性能损耗小，浏览器重排和重绘次数最少。
（对于初始时是否给有数据，这个不必纠结，如果没有数据，可遍历DOM获得这个数据[只获取ID即可，count初始都为0]）
下面给出自己的答案（当然也肯定有最优解法，正在寻求）：
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>点击排序</title>
<style type="text/css">
body{width:960px;margin:0px auto}
#boxContainer{list-style:none;}
#boxContainer li{position:relative;float:left;width:100px;height:100px;font:bold 28px/100px "Times New Roman", Times, serif;text-align:center;border:solid 1px #ccc;margin:5px;cursor:pointer}
#boxContainer li font{position:absolute;top:4px;right:2px;line-height:4px;font-size:14px;}
</style>
</head>
<body>
<ul id="boxContainer"></ul>
</body>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript">
/*
解决思路：
1.在初始生成页面时候，利用 sortObj对象存储排序信息，利用countObj存储点击量
2.每次点击时更新countObj，然后从sortObj中找出需置换的两个元素信息(id、count、index)
3.对页面进行元素置换，对sortObj进行元素置换(保持sortObj一直是一个点击量从大到小的顺序序列)
注:
1.为缩短开发时间，本程序利用Jquery库
2.从for(i=0;i<50;i++)开始初始页面，可通过更改数字更改初始时元素多少
3.程序中注释有其它解法，可去掉注释测试
*/
//查找elem在sortObj中的序号，及需与之交换的elem的Id
function findSwapElem(elemId){
var elemCount=countObj[elemId],
swapId=null,
swapIndex=null;
swapCount=null;
for(var m in sortObj){
var idNow=sortObj[m],
countNow=countObj[idNow];
if((countNow<=elemCount)&&(swapId==null)){
if((idNow!=elemId)&&(countNow==elemCount)){ //若count相同、id不同，则跳出本次循环
continue;
}
swapId=idNow;
swapIndex=m;
swapCount=countNow;
}
if(idNow==elemId){ //同时获取当前elem的排序index(减少一次对sortObj的重复遍历)
var elemIndex=m;
}
}
return {"elemId":elemId, //返回需互换元素相关信息，供后续处理
"elemIndex":elemIndex,
"elemCount":elemCount,
"swapId":swapId,
"swapIndex":swapIndex,
"swapCount":swapCount
};
}
//重新排序文档页面中的elem
function resortElem(swapObj){
var elemId=swapObj["elemId"],
swapId=swapObj["swapId"],
elemBox=$("#"+elemId),
swapBox=$("#"+swapId);
//法一：两个box相关属性互换（也可内容组合后一次性替换以减少浏览器重排次数[由六次降为四次]，但如果box中内容较多则一次性替换的方法就比较繁琐）
//elemBox.attr("id",swapId).find("font").text("Id:"+swapId).end().find("b").text(swapObj['swapCount']);
//swapBox.attr("id",elemId).find("font").text("Id:"+elemId).end().find("b").text(swapObj['elemCount']);
//法二：克隆副本替换 （理论上这个效率应该较高，浏览器进行两次重排操作，法一属性改变频繁重排次数较多）
var elemClone=elemBox.clone(),
swapClone=swapBox.clone();
elemBox.replaceWith(swapClone);
swapBox.replaceWith(elemClone);
}
//重新排序sortObj (需置换元素互换)
function resortObj(swapObj){
var elemIndex=swapObj["elemIndex"],
swapIndex=swapObj["swapIndex"];
sortObj[elemIndex]=[sortObj[swapIndex], sortObj[swapIndex]=sortObj[elemIndex]][0];
}
//字符串化sortObj (非必要函数，仅供查看排序结果时打印数据使用)
function stringObj(sortObj){
var strArr=[];
for(var m in sortObj){
strArr.push(m+" id:"+sortObj[m]+" count:"+countObj[sortObj[m]]+"\n");
}
return strArr.join("");
}
//绑定点击事件
$("#boxContainer>li").live("click",function(){
var _this=$(this);
elemId=_this.attr("id");
count=countObj[elemId]+1;
countObj[elemId]=count;
_this.find("b").text(count);
var swapObj=findSwapElem(elemId),
swapId=swapObj['swapId'];
if(swapId==null||swapId==elemId){ //已是最大或顺序正确，无需交换
return false;
}else{
resortElem(swapObj);
resortObj(swapObj); //重新排序(置换)sortObj
}
})
//初始化N个点击量count为0的元素，每个元素独有一个id,countObj存储点击量,sortObj存储排序
var strArr=[],countObj={},sortObj={};
for(i=0;i<50;i++){
var elemId='elem'+i;
sortObj[i]=elemId;
countObj[elemId]=0;
strArr.push('<li id="'+elemId+'"><font>ID:'+elemId+'</font><b>'+0+'</b></li>');
}
$("#boxContainer").html(strArr.join(""));
</script>
</html>
经过测试，法二的确比法一性能要好35%左右，50个BOX，法二点击一次，耗时约为71ms，法一耗时109ms.
对于重排和重绘，不同浏览器处理方式可能稍有区别，但性能损耗测试还是相对比较一致的。
【参考】
前端优化总结 http://blogread.cn/it/article/2184?f=wb
http://varnow.org/?p=232 http://blog.csdn.net/baiduforum/article/details/5415527
浏览器的重绘与重排 http://kb.cnblogs.com/page/169820/
页面重绘与重排版的性能影响http://blog.csdn.net/hhq163/article/details/6965895
评论：
发表评论：