更高效的JavaScript Array Unique函数

JavaScript没有Python中set这样的数据类型,也没有提供类似于PHP的array_unique方法来去除数组中的重复元素。如此情形在“玩具语言”JavaScript中倒也常见,每天都需要自已动手丰衣足食。

最基本的数组去重方法就是遍历数组,看看取到的元素是否已经出现过,如果出现过,就扔掉这个元素。该算法非常类似于插入排序算法。最好的情况下,即数组中所有元素都相同时,复杂度是线性的。最坏的情况下,即所有元素都不重复,复杂度则为O(n^2)

function slowUnique(ary) {
  var ret = [],i,j,l = ary.length;
  outer:
  for(i=0; i<l; i++) {
    j=ret.length;
    p=ary[i];
    while(j--) {
      if (ret[j]===p) continue outer;
    }
    ret.push(p);
  }
  return ret;
}

有人认为可以先使用Array#sort方法排序,再去除重复元素,毕竟使用Native方法性能更好,并且一般Sort实现都会选择一个Θ(n log n)算法:

function naiveSortUnique(ary) {
  ary=ary.slice().sort();
  var i=0,j,p,l = ary.length;
  for(; i<l; i++) {
    j=i;
    p=ary[i];
    while (j+1 < l  && ary[j+1]===p) j++;
    if (j-i) {
      j-=i;
      ary.splice(i+1,j);
      l-=j;
    }
  }
  return ary;
}

先不急着谈更取巧的实现,上面的代码其实有三个问题:

  1. 该方法复杂度仍然是O(n^2),因为通常Array#splice实现的复杂度为Θ(n)
  2. 该方法仅适用于同质原始类型的Array,即数组中所有值都是同一PrimitiveType。因为Array#sort方法默认是将两个值都转换成字符串再比较:
    If compareFunction is not supplied, elements are sorted by converting them to strings and comparing strings in lexicographic ("dictionary" or "telephone book", not numerical) order. For example, "80" comes before "9" in lexicographic order, but in a numeric sort 9 comes before 80.

    如对于下面的异质数组,排序前后结果都是一样的:
    var a=["1",1,"1",1];
    a.sort();
    console.log(a); // => 仍然原样输出:["1", 1, "1", 1]
    console.log(naiveSortUnique(a)); // => 还是原样输出:["1", 1, "1", 1]
    
  3. Native方法并不总是性能最好的,如上所说,原生排序方法会将所有值转换成字符串再比较,这样显然过于低效。并且原生Sort函数还需要特殊处理SparseArray中的undefined值,如[undefined,"undefined"]排序后的结果是["undefined",undefined]

下面是一个改进的版本,使用了ShellSort(因为又短又快),仍然只支持同质原始类型Array:

function sortUnique(a) {
  var n=a.length;
  if (n<=1) return a;
  //do a shell sort
  var k=1,hi=n/3|0,i,j,tmp;
  while (k < hi) k=k*3+1;
  while (k > 0) {
    for (i=k;i<n;i++) {
      for (j=i;j>=k && a[j]<a[j-k];j-=k) {
        tmp=a[j]; a[j]=a[j-k]; a[j-k]=tmp;
      }
    }
    k=k/3|0;
  }
  var last=a[0],x;
  var ret=[last];
  for (i=1;i<n;i++) {
    x=a[i];
    if (x===last) continue;
    ret.push(last=a[i]);
  }
  return ret;
}

接着再解决剩下的问题:异质数组。尽管通常我们都只使用同质数组,但对于JavaScript这样的动态类型语言,刚好它又没提供Python中Tuple那样的类型,所以有必要考虑下数组中有不同类型值的情况。这也就引出了另一种实现方式:Unique函数的实现想要效率更高的话,可以在“查看元素是否已经出现”这一步骤使用Hash查找,也就是JS中的Object属性查找,可以认为该操作复杂度为Θ(1)。创建一个Object作为HashTable,将数组中的值作为Key,那么查看一个元素是否重复,只需要看HashTable中有没有该键就行了。但要注意的是,不同的类型需要使用不同的注册表。因为只有String才可以作为属性名,true in o"true" in o返回值是一样的。其实考虑到这一步还不够,只有PrimitiveType可以直接转换成字符串作Hash Key,非原始值则不行,因为Object的toString默认都是相同的"[object Object]",不能直接拿来作Hash Key;而JS对象又没有类似于Ruby中的object_id或Java中的hashCode这样的方法,所以非原始值必须使用另外一种方法,真正的Trick也在这里:每次unique函数执行时生成一个GUID,给遍历过的对象加上这个GUID标识,如果再遍历到已有此GUID标识的元素,就是重复元素了。这种方法的缺陷就是会修改原来的对象,并且对于被Object.freeze过了的对象,就无法添加GUID标识了。这种特殊情形就暂不考虑了。与前面几种方法相比,显然Hash Unique实现是最完善的,覆盖了其它几种实现都无法处理的引用类型和异质数组。但它并不总是最高效的,虽然其复杂度可以看成Θ(n),但对于Int数组,实践上Sort Unique方法更为高效(当然我知道现实中JS程序员是不需要关心这种性能差异的;)。最终实现如下:

/**
 * Array unique,该函数会同时过滤掉null与undefined
 * @param {Array} ary 需要进行unique的数组.
 * @return {Array} 返回没有重复元素的新的数组,
 */
function unique(ary) {
  var i=0,l=ary.length,
      type,p,ret=[],
      guid=(Math.random()*1E18).toString(32)+(+new Date).toString(32),
      objects=[],
      reg={ //Primitive类型值Register
          'string': {},
          'boolean': {},
          'number': {}
      };
  for (;i<l;i++) {
    p = ary[i];
    if (p==null) continue;
    type = typeof p;
    if (reg[type]) {//PrimitiveType
      if (!reg[type].hasOwnProperty(p)) {
        reg[type][p] = 1;
        ret.push(p);
      }
    } else {//RefType
      if (p[guid]) continue;
      p[guid]=1;
      objects.push(p);
      ret.push(p);
    }
  }
  i=objects.length;
  while (i--) {//再将对象上的guid清理掉
    p=objects[i];
    delete p[guid];
  }
  return ret;
}