javascript의 배열에 대한 unique()

Question

모두가 javascript의 배열에서 중복을 제거하는 기본 제공 함수가 없다는 것을 모두 알고 있습니다. 나는 이것이 또한 jQuery (DOM 선택을위한 유일한 기능을 가지고있다)에서 부족하다는 것을 알았다. 그리고 발견 된 가장 일반적인 스 니펫은 전체 배열과 각 엘리먼트에 대한 서브셋 (매우 효율적이지는 않다)을 검사한다. :

for (var i = 0; i < arr.length; i++) 
    for (var j = i + 1; j < arr.length; j++) 
     if (arr[i] === arr[j]) 
      //whatever 

그래서 내가 만든 내 자신 :

function unique (arr) { 
    var hash = {}, result = []; 
    for (var i = 0; i < arr.length; i++) 
     if (!(arr[i] in hash)) { //it works with objects! in FF, at least 
      hash[arr[i]] = true; 
      result.push(arr[i]); 
     } 
    return result; 
} 

나는이 경우에 가장 적합한으로 받아 들여 다른 알고리즘이 있는지 궁금합니다 (또는 고정 할 수있는 명백한 결함을 볼 경우), 또는 , 당신이 자바 스크립트에서 이것을 필요로 할 때 (나는 jQuery가 유일한 프레임 워크가 아니며 다른 것들은 이미 다룰 수 있음을 알고있다).

Answer 1

개체 리터럴을 사용하면 정확히 무엇을 할 수 있습니다. 많은 사람들이 사람들이이 기술을 놓쳤습니다. 많은 시간을 보냈는데, 전형적인 배열 산책은 원래 보여준 코드와 같습니다. 유일한 최적화는 매번 arr.length 조회를 피하는 것입니다. 그 외, O (n)은 당신이 독창성을 얻는만큼 좋으며 원래 O (n^2) 예제보다 훨씬 낫습니다.

function unique(arr) { 
    var hash = {}, result = []; 
    for (var i = 0, l = arr.length; i < l; ++i) { 
     if (!hash.hasOwnProperty(arr[i])) { //it works with objects! in FF, at least 
      hash[ arr[i] ] = true; 
      result.push(arr[i]); 
     } 
    } 
    return result; 
} 

// * Edited to use hasOwnProperty per comments 

시간의 복잡성은 대부분의 알고리즘과 마찬가지로

f() | unsorted | sorted | objects | scalar | library 
____________________________________________________________ 
unique | O(n) | O(n) | no | yes | n/a 
original | O(n^2) | O(n^2) | yes | yes | n/a 
uniq  | O(n^2) | O(n) | yes | yes | Prototype 
_.uniq | O(n^2) | O(n) | yes | yes | Underscore 

를 요약, 무역 오프가 있습니다. 스칼라 값만 정렬하는 경우 원본 알고리즘을 수정하면 최적의 솔루션을 얻을 수 있습니다. 그러나 비 스칼라 값을 정렬해야하는 경우 토론 된 라이브러리 중 하나의 방법을 사용하거나 모방하여 사용하는 것이 가장 좋습니다.

Answer 2

[Object object]과 같은 문자열 표현을 제공하는 배열에 객체 또는 함수가있을 때 버전이 작동하지 않을 것 같습니다. 객체의 키로 문자열을 가질 수 있기 때문에 (여기서는 "해시"객체에 있음). 새 항목이 이미 있는지 찾으려면 결과 배열로 반복해야합니다. 그것은 여전히 ​​첫 번째 방법보다 빠릅니다.

프로토 타입 JS에는 "uniq"방법이 있습니다. 영감을 얻으실 수 있습니다.

Answer 3

저는 알고리즘 전문가가 아니지만 언더 코어 .js를 주시하고 있습니다. 그들은 기능이라고 UNIQ로이 있습니다

http://documentcloud.github.com/underscore/#uniq

내가 자신의 라이브러리에있는 코드를보고하고, (나의 코드는,이 코드는 underscore.js에 속하는) 참조를 위해 여기를 복사 :

// Produce a duplicate-free version of the array. If the array has already 
// been sorted, you have the option of using a faster algorithm. 
_.uniq = function(array, isSorted) { 
    return _.reduce(array, [], function(memo, el, i) { 
     if (0 == i || (isSorted === true ? _.last(memo) != el : !_.include(memo, el))) memo.push(el); 
     return memo; 
    }); 
}; 

EDIT : 나머지 언더 코어 .js 코드를 살펴볼 필요가 있습니다. 이 코드가 여전히 유용한 경우를 위해 코드 스 니펫을 남겼습니다.

Answer 4

불행히도 JS 객체에는 언어에서 액세스 할 수있는 ID가 없습니다. 다른 포스터에서 언급했듯이 다른 객체의 문자열 표현이 같고 언어에 id() 기능이 없으면 객체를 사전 키로 사용하면 오류가 발생합니다.

개체를 수정할 수있는 경우 O (n^2) 전체 쌍이 === 신원을 확인하는 방법은 없습니다.임의의 문자열을 선택하고 해당 배열의 객체가 해당 이름의 속성을 갖고 있는지 확인한 다음 각각 i에 대해 arr[i][randomPropertyName]=1을 수행합니다. 배열의 다음 객체에 이미 해당 속성이있는 경우 중복됩니다.

불행히도 위의 내용은 수정 가능한 개체에만 적용됩니다. 그것은 (예를 들어, 정수, 42['random']=1 그냥 작동하지 않습니다 :() 속성 설정을 허용하지 않는 배열 값에 대한 재미 (ctional)와

Answer 5

재미

function uniqueNum(arr) { 
    return Object.keys(arr.reduce(
     function(o, x) {o[x]=1; return o;}, {})).map(Number); 
}