阅读 76

算法-数组去重

关键词: 去重 unique

这是一篇考古文,2013玉伯在优化SeaJs性能时提出的一个问题,原文出处在这里从js数组去重谈性能优化, 以数组去重为切入点,比较辩证的谈了解决问题的方法论。 核心观点可以看下原文,本文只讲数组去重的最优方法以及其他几种方法。

最优方法

利用对象的属性不会重复这一特性,首先创建一个空对象,然后用 for 循环遍历,来校验数组元素是否重复。

let a = [0,1,1,2,3,4,4,4];
let result = [];
let obj = {};

for(let i of a){
    if (!obj[i]){
      result.push(i);
      obj[i] = 1;
  }
}
Object.keys(obj)
复制代码

上面这种方法,无论从代码量和执行的时间复杂度上讲都是不错的。

最优方法2

高版本的运行环境,使用ES6的Set结构来去重,使用起来更方便:

let set = new Set([1,2,3,3,3,3]); // 数组转成set
console.log(set ); // set结构{1,2,3}
console.log([...set]) // set转成数组 [1,2,3]
复制代码

这两种方法对于多少场景已经够用了,但需求往往都不是那么“纯粹的”,实际工作中要求数组去重算法可以和不同的算法逻辑组合实现一个复合的需求。

个人理解代码优化就是一个对内优化,对外兼容的过程,不管是向内还是向外,坚持去做我理解是可以收获到以下几点:

  1. 训练自己的代码优化思路,并且对优化过程复盘
  2. 将最优结果实现思路写成一条流程线
  3. 将多个最优结果的流程线横向对齐比较,总结出处理问题的公共节点
  4. 形成一套自己的方法论,该套用时就套用(没研究过八股文,就不要去批判,有套路的东西是有可取之处的),套用模板可以节约时间,用节约出来的时间再去创造才是最高效的。
  • 这是必须要养成的一个能力,这个能力可以帮助自己去看懂别人写的代码。
  • 看好的框架的代码比零碎的学习更能学到东西,就像好的老师让学习更容易。

最优方法3 - underscore中的uniq函数

提供一个完整的兼容方案,也可以理解成内聚,对外只提供一个函数。 例如 underscore中的uniq函数_.uniq(array, [isSorted], [iteratee]),不仅可以对数据去重,也可以对object类型去重呀。

  1. 能有多少种思路去实现数组去重算法
  2. 识别问题,并且能合理的去优化
  3. 这一个问题有多少知识点呢?例如:IE8下不支持indexOf(知识点只有结合实际才能清晰记得和灵活使用), indexOf的时间复杂度或webkit中indexOf实现方法 webkit

欣赏一下underscore中的uniq函数的实现

   _.uniq = _.unique = function(array, isSorted, iteratee, context) {
    if (array == null) return [];
    if (!_.isBoolean(isSorted)) {
      //如果没有排序
      context = iteratee;
      iteratee = isSorted;
      isSorted = false;
    }
    /**
    ** 此处_.iteratee
    **  function (key){
    *      return function(obj){
    *        return obj[key];
    *      }
    **  }
    **  key就是这里的iteratee(对象的属性),这里使用了闭包
    **/
    if (iteratee != null) iteratee = _.iteratee(iteratee, context); 
    var result = [];//返回去重后的数组(副本)
    var seen = [];
    for (var i = 0, length = array.length; i < length; i++) {
      var value = array[i];//当前比较值
      if (isSorted) {
        //如果i=0时,或者seen(上一个值)不等于当前值,放入去重数组中
        if (!i || seen !== value) result.push(value); 
        seen = value;//保存当前值,用于下一次比较
      } else if (iteratee) {
        var computed = iteratee(value, i, array);
        if (_.indexOf(seen, computed) < 0) {
          seen.push(computed);
          result.push(value);
        }
      } else if (_.indexOf(result, value) < 0) {
        result.push(value);
      }
    }
    return result;
  };
复制代码

深入研究

进一步的性能优化就要看看C++是怎么做的了,毕竟webkit是用C++写的。

也有人开始给c++写一个underscore库, 这是个有意思的想法, c++的STL就相当于js的underscore库,或者有人写了一个TypeScript版的STL tstl,很有趣!

c++实现string类型的indexOf参考示例:

#include <iostream>
using namespace std;
int indexOf( char *source, char *what );

int main()
{
	int ret = indexOf( "123456", "23" );
	cout << ret; // 1
	return(0);
}

int indexOf( char *source, char *what )
{
	int ret = 0;
	if ( *source )
	{
		int i = 0;
		for ( i = 0; i < what[i]; i++ )
		{
			if ( source[i] != what[i] )
				break;
		}
		if ( what[i] == '\0' )
			return(0);
		if ( source[i] == what[0] )
			i -= 1;      /* 解决BUG */
		ret = indexOf( source + i + 1, what );
		if ( ret >= 0 )
			return(i + ret + 1);
		return(-1);
	}else
		return(-1);
}
复制代码

作为前端捡一捡C++这里有个不错的公开课公开课

关注下面的标签,发现更多相似文章
评论