search

lessfish / underscore-analysis

【NO LONGER UPDATE】underscore-1.8.3.js 源码解读 & 系列文章（完）
MIT License
3.96k stars 642 forks source link

JavaScript 数组去重 #9

Open lessfish opened 8 years ago

lessfish commented 8 years ago

Why underscore

（觉得这部分眼熟的可以直接跳到下一段了...）

最近开始看 underscore.js 源码，并将 underscore.js 源码解读 放在了我的 2016 计划中。

阅读一些著名框架类库的源码，就好像和一个个大师对话，你会学到很多。为什么是 underscore？最主要的原因是 underscore 简短精悍（约 1.5k 行），封装了 100 多个有用的方法，耦合度低，非常适合逐个方法阅读，适合楼主这样的 JavaScript 初学者。从中，你不仅可以学到用 void 0 代替 undefined 避免 undefined 被重写等一些小技巧 ，也可以学到变量类型判断、函数节流&函数去抖等常用的方法，还可以学到很多浏览器兼容的 hack，更可以学到作者的整体设计思路以及 API 设计的原理（向后兼容）。

之后楼主会写一系列的文章跟大家分享在源码阅读中学习到的知识。

欢迎围观~ （如果有兴趣，欢迎 star & watch~）您的关注是楼主继续写作的动力

数组去重

今天要聊的，也是我以前笔试时碰到过的一个问题，数组去重，不知道现在的笔试题还考不考这个？

数组去重，一般需求是给你一个数组，调用去重方法，返回数值副本，副本中没有重复元素。一般来说，两个元素通过 === 比较返回 true 的视为相同元素，需要去重，所以，1 和 "1" 是不同的元素，1 和 new Number(1) 是不同的元素，{} 和 {} 是不同的元素（引用不同）。（当然如果需求认为 {} 和 {} 算作相同的元素，那么解法就不一样了）

方法一

无需思考，我们可以得到 O(n^2) 复杂度的解法。定义一个变量数组 res 保存结果，遍历需要去重的数组，如果该元素已经存在在 res 中了，则说明是重复的元素，如果没有，则放入 res 中。

function unique(a) {
  var res = [];

  for (var i = 0, len = a.length; i < len; i++) {
    var item = a[i];

    for (var j = 0, jLen = res.length; j < jLen; j++) {
      if (res[j] === item)
        break;
    }

    if (j === jLen)
      res.push(item);
  }

  return res;
}

var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]

代码非常简单，那么是否能更简洁些？如果不考虑浏览器兼容，我们可以用 ES5 提供的 Array.prototype.indexOf 方法来简化代码。

function unique(a) {
  var res = [];

  for (var i = 0, len = a.length; i < len; i++) {
    var item = a[i];

    (res.indexOf(item) === -1) && res.push(item);
  }

  return res;
}

var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]

既然用了 indexOf，那么不妨再加上 filter。

function unique(a) {

  var res = a.filter(function(item, index, array) {
    return array.indexOf(item) === index;
  });

  return res;
}

var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]

方法二

法一是将原数组中的元素和结果数组中的元素一一比较，我们可以换个思路，将原数组中重复元素的最后一个元素放入结果数组中。

function unique(a) {
  var res = [];

  for (var i = 0, len = a.length; i < len; i++) {
    for (var j = i + 1; j < len; j++) {
      // 这一步十分巧妙
      // 如果发现相同元素
      // 则 i 自增进入下一个循环比较
      if (a[i] === a[j])
        j = ++i;
    }

    res.push(a[i]);
  }

  return res;
}

var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => ["1", "2", 1]

虽然复杂度还是 O(n^2)，但是可以看到结果不同，1 出现在了数组最后面，因为结果数组取的是元素最后一次出现的位置。

方法三（sort)

如果笔试面试时只答出了上面这样 O(n^2) 的方案，可能还不能使面试官满意，下面就来说几种进阶方案。

将数组用 sort 排序后，理论上相同的元素会被放在相邻的位置，那么比较前后位置的元素就可以了。

function unique(a) {
  return a.concat().sort().filter(function(item, pos, ary) {
    return !pos || item != ary[pos - 1];
  });
}

var a = [1, 1, 3, 2, 1, 2, 4];
var ans = unique(a);
console.log(ans); // => [1, 2, 3, 4]

但是问题又来了，1 和 "1" 会被排在一起，不同的 Object 会被排在一起，因为它们 toString() 的结果相同，所以会出现这样的错误：

var a = [1, 1, 3, 2, 1, 2, 4, '1'];
var ans = unique(a);
console.log(ans); // => [1, 2, 3, 4]

当然你完全可以针对数组中可能出现的不同类型，来写这个比较函数。不过这似乎有点麻烦。

方法四 （object）

用 JavaScript 中的 Object 对象来当做哈希表，这也是几年前笔试时的解法，跟 sort 一样，可以去重完全由 Number 基本类型组成的数组。

function unique(a) {
  var seen = {};

  return a.filter(function(item) {
    return seen.hasOwnProperty(item) ? false : (seen[item] = true);
  });
}

var a = [1, 1, 3, 2, 1, 2, 4];
var ans = unique(a);
console.log(ans); // => [1, 3, 2, 4]

还是和方法三一样的问题，因为 Object 的 key 值都是 String 类型，所以对于 1 和 "1" 无法分别，我们可以稍微改进下，将类型也存入 key 中。

function unique(a) {
  var ret = [];
  var hash = {};

  for (var i = 0, len = a.length; i < len; i++) {
    var item = a[i];

    var key = typeof(item) + item;

    if (hash[key] !== 1) {
      ret.push(item);
      hash[key] = 1;
    }
  }

  return ret;
}

var a = [1, 1, 3, 2, '4', 1, 2, 4, '1'];
var ans = unique(a);
console.log(ans); // => [1, 3, 2, "4", 4, "1"]

虽然解决了讨厌的 1 和 "1" 的问题，但是还有别的问题！

var a = [{name: "hanzichi"}, {age: 30}, new String(1), new Number(1)];
var ans = unique(a);
console.log(ans); // => [Object, String]

但是如果数组元素全部是基础类型的 Number 值，键值对法应该是最高效的！

方法五 （ES6）

ES6 部署了 Set 以及 Array.from 方法，太强大了！如果浏览器支持，完全可以这样：

function unique(a) {
  return Array.from(new Set(a));
}

var a = [{name: "hanzichi"}, {age: 30}, new String(1), new Number(1)];
var ans = unique(a);
console.log(ans); // => [Object, Object, String, Number]

_.unique

最后来看看 underscore 对此的实现方式，underscore 将此封装到了 .unique 方法中，调用方式为 .unique(array, [isSorted], [iteratee])。其中第一个参数是必须的，是需要去重的数组，第二个参数可选，如果数组有序，则可以传入布尔值 true，第三个参数可选，如果需要对数组迭代的结果去重，则可以传入一个迭代函数。而数组元素去重是基于 === 运算符的。

其实很简单，underscore 中的实现方式和上面的方法一相似。

我们来看它的核心代码：

for (var i = 0, length = getLength(array); i < length; i++) {
  var value = array[i],
      // 如果指定了迭代函数
      // 则对数组每一个元素进行迭代
      computed = iteratee ? iteratee(value, i, array) : value;

  // 如果是有序数组，则当前元素只需跟上一个元素对比即可
  // 用 seen 变量保存上一个元素
  if (isSorted) {
    // 如果 i === 0，则直接 push
    // 否则比较当前元素是否和前一个元素相等
    if (!i || seen !== computed) result.push(value);
    // seen 保存当前元素，供下一次对比
    seen = computed;
  } else if (iteratee) {
    // 如果 seen[] 中没有 computed 这个元素值
    if (!_.contains(seen, computed)) {
      seen.push(computed);
      result.push(value);
    }
  } else if (!_.contains(result, value)) {  
    // 如果不用经过迭代函数计算，也就不用 seen[] 变量了
    result.push(value);
  }
}

外面的循环遍历数组元素，对于每个元素，如果数组有序，则和前一个元素比较，如果相同，则已经出现过，不加入到结果数组中，否则则加入。而如果有迭代函数，则计算传入迭代函数后的值，对值去重，调用 .contains 方法，而该方法的核心就是调用 .indexOf 方法，和我们上面说的方法一异曲同工。

关于 _.unique 方法的详细代码，可以参考 https://github.com/hanzichi/underscore-analysis/blob/master/underscore-1.8.3.js/src/underscore-1.8.3.js#L519-L547

Read More

idda commented 8 years ago

学习了

silasFFF commented 8 years ago

1024

L9m commented 8 years ago

学习了

Wangbaogang commented 8 years ago

赞赞赞 -- 来自点赞小能手

aleen42 commented 7 years ago

方法三如果用严格判定 item !== arr[pos - 1] 的话，不就能解决 Number 与 String 排在一起的问题咯？

BigKongfuPanda commented 7 years ago

厉害，没想到有这么多种方法呢

BigKongfuPanda commented 7 years ago

我想咨询一个问题，如果说数组是这样：arr = [{name:"tom"},{name:"tom"},{age: 18}]; 请问数组中的第一项和第二项，是算重复的嘛？ 如果是的话，你上面的方法好像失效了。

aleen42 commented 7 years ago

@BigKongfuPanda 在作者看来，这种情况应该属于引用不同，因此不能称作完全相同的两个元素。这在于你如何理解两个元素何谓重复。

BigKongfuPanda commented 7 years ago

嗯。严格意义上来说，如果比较地址的话，肯定是不同的。还是看实际情况下的要求吧。

发送自我的三星 Galaxy 智能手机。 -------- 原始信息 --------由： Aleen notifications@github.com 日期: 17/2/24 17:25 (GMT+08:00) 收件人： hanzichi/underscore-analysis underscore-analysis@noreply.github.com 抄送： BigKongfuPanda zhqustb@163.com, Mention mention@noreply.github.com 主题： Re: [hanzichi/underscore-analysis] JavaScript 数组去重 (#9) @BigKongfuPanda 在作者看来，这种情况应该属于引用不同，因此不能称作完全相同的两个元素。这在于你如何理解两个元素何谓重复。

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

{"api_version":"1.0","publisher":{"api_key":"05dde50f1d1a384dd78767c55493e4bb","name":"GitHub"},"entity":{"external_key":"github/hanzichi/underscore-analysis","title":"hanzichi/underscore-analysis","subtitle":"GitHub repository","main_image_url":"https://cloud.githubusercontent.com/assets/143418/17495839/a5054eac-5d88-11e6-95fc-7290892c7bb5.png","avatar_image_url":"https://cloud.githubusercontent.com/assets/143418/15842166/7c72db34-2c0b-11e6-9aed-b52498112777.png","action":{"name":"Open in GitHub","url":"https://github.com/hanzichi/underscore-analysis"}},"updates":{"snippets":[{"icon":"PERSON","message":"@aleen42 in #9: @BigKongfuPanda 在作者看来，这种情况应该属于引用不同，因此不能称作完全相同的两个元素。这在于你如何理解两个元素何谓重复。"}],"action":{"name":"View Issue","url":"https://github.com/hanzichi/underscore-analysis/issues/9#issuecomment-282244872"}}}

tiansn commented 7 years ago

@hanzichi ,能分析下，每种方法的复杂度么，特别是最后的那几种

zhangbowei commented 7 years ago

function unique(a) { return Array.from(new Set(a)); }

var a = [{name: "hanzichi"}, {name: "hanzichi"},{age: 30}, new String(1), new Number(1)]; var ans = unique(a); console.log(JSON.stringify(ans)); //output [{"name":"hanzichi"},{"name":"hanzichi"},{"age":30},"1",1]

MarioGogogo commented 7 years ago

学习了

hms181231 commented 7 years ago

学习了

CatBone commented 7 years ago

还一种简单的，可以运用es6的扩展运算符 var unique = a => [...new Set(a)]

😝😝😝

HowardTangHw commented 7 years ago

您好,我有个疑问,为什么在方法2中j=++i会把外部的循环中断掉,而不执行语句res.push(a[i])呢?

function unique(a) {
  var res = [];

  for (var i = 0, len = a.length; i < len; i++) {
    for (var j = i + 1; j < len; j++) {
      if (a[i] === a[j]) {
        console.log('中断了')
        j = ++i;
      }
    }
    // 不清楚为啥j=++i;会break掉循环,不进入这一步
    console.log('没被中断');
    res.push(a[i]);
  }

  return res;
}

var a = [1, 1, "1", "2", 1];
var ans = unique(a);
console.log(ans); // => ["1", "2", 1]
Arvinzhu commented 7 years ago

@HowardTangHw 没有中断外部循环，而是内部循环在遇到充负的元素时，修改i的值，也就是修改外部循环下次循环的起点，当内部循环执行完毕后，push一个没有重复的值到res中，然后外部循环执行 以修改后的i值执行i++开始执行下一次循环

seaskymonster commented 7 years ago

对于 1 和 "1" 无法分别这个问题：

其实可以在你的方法四上直接改 function unique(a) { var seen = {}; return a.filter(function(item){ return seen.hasOwnProperty(typeof(item)+item) ? false: (seen[typeof(item)+item] = true); }) }

islishude commented 7 years ago

indexOf 最大的问题就是 NaN 无法去重

wangliang1124 commented 6 years ago

方法三： return !pos || item != ary[pos - 1]; 换成 return !pos || item !== ary[pos - 1]; 使用严格相等应该就行了吧

wangliang1124 commented 6 years ago

_20180328161606