가장 빠른 배열 중복 제거 알고리즘

Posted on Edited on In ,

가장 빠른 배열 중복 제거 알고리즘

통계 사용시에 중복을 제거해야하는 경우가 있다.

소스

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
/*
  @author http://www.shamasis.net/2009/09/fast-algorithm-to-find-unique-items-in-javascript-array/
*/

// prototype
Array.prototype.unique = function () {
  var o = {},
    i,
    r = [];
  var l = this.length;

  for (i = 0; i < l; i++) {
    o[this[i]] = this[i];
  }

  for (i in o) {
    r.push(o[i]);
  }

  return r;
};

// function
var uniqueArray = function (arr) {
  var o = {},
    i,
    r = [];
  var l = arr.length;

  for (i = 0; i < l; i++) {
    o[arr[i]] = arr[i];
  }

  for (i in o) {
    r.push(o[i]);
  }

  return r;
};

예제

1
2
3
4
5
6
var testArray = [1, 2, 1, 3];

testArray = testArray.unique();
testArray = uniqueArray(testArray);

console.log(testArray); // [ 1, 2, 3 ];

여담

언더스코어를 알게된 후로는 lodash의 uniq나 uniqBy를 사용한다.