Web 技术研究所

我一直坚信着,Web 将会成为未来应用程序的主流

关于数组去重的算法

  数组去重的问题看似简单,但要实现好它确实不太容易。如果只是普通的纯字符串或纯数字数组那好说,直接利用对象的字典性质就可以转换。但JavaScript是弱类型的,数组元素的类型也未必固定,一个数组可能有多个类型的元素,那处理起来就有点麻烦了。
  数组去重的算法有很多,主要分类三类:
  直接去重:时间复杂度 O(n²)
  这个方法没啥好介绍的,就是遍历到元素时候再遍历检测是否是重复,由于有两层嵌套的遍历,所以它的性能不高,不过它对数据本身的影响是最小的。
  排序去重:时间复杂度 O(nlogn)
  先对数组做一次排序,然后遍历数组时相同元素都在邻近的位置,一次遍历就可以搞定。但是需要考虑一个问题,对象是可能无法比较大小的。这个算法那也许在C++之类的语言中可以很容易使用,但由于JavaScript无法直接取到对象的地址,所以排序就没有依据了。要让对象变得可排序就需要为每个不同的对象都添加一个唯一ID。另外,即使可以排序,最后得到的结果中元素的顺序也是被排序后的。如果需要得到元素的初始顺序还需要额外的维护部分,所以这个算法非常不适合JavaScript。
  字典去重:时间复杂度 O(n)
  JavaScript对象本身就是个字典,所以字典去重的方式对于统一的原始类型数组非常容易使用。但和排序去重遇上了一样的问题,至少需要个唯一ID才可以作为字典的索引。所以我们不得不给对象加上唯一ID。当然这个ID可以是临时的,算法结束时销毁。但这就意味着这个算法需要操作对象本身,虽然大多数情况下并不会造成什么影响,但无法保证意外不发生。
  下面是直接去重和字典去重的测试代码,既麻烦又不科学的排序去重的我就不写了。
<input type="button" value="直接去重" id="unique1" />
<input type="button" value="字典去重" id="unique2" />
<script>
//直接去重
function unique1(a){
  //遍历所有元素,如果元素已存在就不保存它
  for(var i=0,j,k=0;i<a.length;i==j&&(a[k++]=a[i]),i++)
    for(j=0;j<i;j++)if(a[i]===a[j])break; //遍历判断元素是否已存在
  a.splice(k); //删除多余项
};

//字典去重
function unique2(a){
  var i,j=0,c=0,n,v,e,s={},Hash=function(o,e){
    e&&(this.x=o.ID),this.id=c++,o.ID=this; //如果ID属性名冲突则保存旧ID
  };
  //为每个对象一个唯一ID
  for(i=0;v=a[i],i<a.length;i++)if(v instanceof Object) //针对对象处理
    e=v.hasOwnProperty("ID"), //判断元素上是否存在临时ID属性
    //为元素分配唯一ID,如果已分配则使用已有的
    e=e&&v.ID instanceof Hash?v.ID:new Hash(v,e),
    s["object"+e.id]=v; //前面加上类型前缀作为key放入字典中
  else s[typeof v+v]=v; //普通类型直接使用类型前缀和值作为key放入字典中
  //遍历字典中的对象并移回原始数组,如果临时ID存在则删除临时ID或还原原有的ID属性
  for(i in s)if(typeof(v=a[j++]=s[i])=="object"&&v)
    "x" in v.ID?(v.ID=v.ID.x):delete v.ID;
  a.splice(j); //删除多余项
};
//免冲突优化
eval((unique2+"").replace(/ID/g,"__"+Math.random()*1E20+"__"));

//生成测试数据
var data=function(){
  var a=[],s=[],i,l=1E4
  //随机产生数字、字符串、对象,三种类型的测试数据
  for(i=0;i<l;i++)s.push([i,i+"",{value:i}][Math.random()*3|0]);
  for(i=0;i<l;i++)a.push(s[Math.random()*l|0]); //随机组合数据
  return a;
}();

document.onclick=function(e){
  if(!(e=e.target).id)return;
  var test=data.slice(0); //复制出一份测试数据
  console.time(e.value); //开始计时
  window[e.id](test); //运行测试
  console.timeEnd(e.value); //结束计时
  console.log(test.length); //输出去重后的元素数量
};
</script>

  才上万个元素的数组就差了这么多了,O(n²)的算法就是这么蛋疼。另外,这个测试代码中还有一句eval,它用来把unique2函数内的“ID”这个临时属性名称替换成一个随机生成的很长的属性名,这样就可以有效降低这个临时属性与对象自带的属性冲突的概率了。
网名:
3.80.32.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^