《多种数组去重性能对比》

发表于 分类于 ， Valine：

测试模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 创建一个 1 ~ 10w 的数组，Array.from为ES6语法
let arr1 = Array.from(new Array(1000000), (x, index) => {
  return index;
});

let arr2 = Array.from(new Array(500000), (x, index) => {
  return index + index;
});

let start = new Date().getTime();
console.log("开始数组去重");

// 数组去重
function distinct(a, b) {
  let arr = a.concat(b);
  // 去重方法
}

console.log("去重后的长度", distinct(arr1, arr2).length);
let end = new Date().getTime();
console.log("耗时", end - start + "ms");

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// 创建一个 1 ~ 10w 的数组，Array.from为ES6语法
let arr1 = Array.from(new Array(1000000), (x, index) => {
  return index;
});

let arr2 = Array.from(new Array(500000), (x, index) => {
  return index + index;
});

let start = new Date().getTime();
console.log("开始数组去重");

// 数组去重
function distinct(a, b) {
  let arr = a.concat(b);

  方法1，耗时约11675ms，约11s
  return arr.filter((item, index) => {
    return arr.indexOf(item) === index
  })

  方法2，耗时约22851ms，约22s，性能最差
  for (let i = 0, len = arr.length; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (arr[i] == arr[j]) {
        arr.splice(j, 1);
        // splice 会改变数组长度，所以要将数组长度 len 和下标 j 减一
        len--;
        j--;
      }
    }
  }
  return arr

  方法3，耗时约12789ms，约12s，和方法1相当
  let result = []
  for (let i of arr) {
    !result.includes(i) && result.push(i)
  }
  return result

  方法4，耗时约23ms，ES5标准中性能最高
  arr = arr.sort()
  let result = [arr[0]]
  for (let i = 1, len = arr.length; i < len; i++) {
    arr[i] !== arr[i - 1] && result.push(arr[i])
  }
  return result

  方法5，ES6的Set数据结构，耗时约20ms，性能高，代码简洁
  return Array.from(new Set([...a, ...b]))

  方法6，耗时约16ms，所有方法中 性能最高！ (千万级数据量下效率比方法5高4倍，for...of 为ES6语法)
  let result = [];
  let obj = {};
  for (let i of arr) {
    if (!obj[i]) {
      result.push(i);
      obj[i] = 1;
    }
  }
  return result;
}

console.log("去重后的长度", distinct(arr1, arr2).length);
let end = new Date().getTime();
console.log("耗时", end - start + "ms");

结论

ES5 标准中性能最高的数组去重方法为:

1
2
3
4
5
6
7
// 耗时约23ms
arr = arr.sort();
let result = [arr[0]];
for (let i = 1, len = arr.length; i < len; i++) {
  arr[i] !== arr[i - 1] && result.push(arr[i]);
}
return result;

ES6 标准中性能最高的数组去重方法为:

1
2
3
4
5
6
7
8
9
10
// 耗时约16ms (千万级数据量下效率比使用Set数据结构方法高4倍，for...of 为ES6语法)
let result = [];
let obj = {};
for (let i of arr) {
  if (!obj[i]) {
    result.push(i);
    obj[i] = 1;
  }
}
return result;

代码既简洁性能又相对高的去重方法为：

1
2
// 耗时约20ms，性能高，代码简洁
return Array.from(new Set([...a, ...b]));