JavaScript array_javascript 팁의 고유 메소드

배열 로컬 객체에 프로토타입 메서드를 추가합니다. 그 목적은 배열 항목에서 중복 항목(여러 개가 있을 수 있음)을 삭제하는 것입니다. 반환 값은 삭제된 중복 항목을 포함하는 새 배열입니다.

공식 설명:
입력
Array(size=N)
출력
Array1=중복 및 순서 보존이 없는 배열의 하위 집합,
중복 의미 없음, 모든 경우 a, b는 Array1에 속합니다. a!=b
순서 보존은 Array에 있는 a의 첨자가 Array에 있는 b의 첨자보다 작으면 Array1에 있는 a의 첨자도 b의 첨자보다 작다는 것을 의미합니다.
Array2=Array-Array1로 표시됨, 순서 보존
realazy는 새로운 솔루션을 제공하며 아이디어는 매우 명확합니다. 순차 순회는 각 요소에 액세스하며, 이 요소의 값에 액세스한 경우 이를 Array2, 그렇지 않으면 Array1을 추가합니다. 현재 요소의 값에 접근했는지 확인하는 방법은 접근된 모든 요소를 ​​순차적으로 순회하는 것이다.
이 알고리즘의 복잡도는 O(N^2) 정도라는 것을 쉽게 알 수 있습니다.

그의 알고리즘 프레임워크에서 약간의 개선을 했습니다. 핵심은 순회 프로세스 중에 현재 요소의 값이 방문되었는지 확인하는 방법에 있습니다. 원본 배열의 값 범위가 양의 정수이고 범위(범위=최대값-최소값)가 너무 크지 않다는 조건에서 간단한 "버킷" 알고리즘을 사용할 수 있습니다.
범위 길이의 부울 배열 b를 준비하고 모두 false로 초기화합니다. 원래 배열의 각 값 값에 대해 b[값]=true이면 해당 값에 액세스하여 Array2에 배치되었음을 의미하고, 그렇지 않으면 Array1에 배치되고 b[값]=true라는 의미입니다.
이것은 분명히 O(N) 알고리즘이며 비용은 추가 공간 복잡도 범위이며 원래 배열 값 범위는 양의 정수여야 합니다.
값 범위가 정수인 경우로 일반화하는 것은 어렵지 않습니다. 실제로 버킷 번호 value-min(Array)을 양의 정수로 변환할 수 있는 경우만 검토하면 됩니다.

너무 큰 범위로 인한 공간 낭비를 피하기 위해 해싱 알고리즘은 "버킷" 알고리즘, 특히 선형 합동 오픈 해싱 방법을 기반으로 개선되었습니다. 목적은 값 범위를 압축하고 이를 연속 양의 정수의 제어 가능한 작은 하위 집합에 매핑하는 동시에 서로 다른 원본 이미지가 동일한 이미지에 해당할 확률을 가능한 한 작게 보장하는 것입니다. 즉, 버킷 간의 로드는 다음과 같아야 합니다. 최대한 균형있게.
예를 들어, 이것은 실수 범위를 갖는 해시 함수입니다:
key=hashFun(value)=Math.floor(value)*37�
이것은 여전히 ​​O(N) 알고리즘입니다( 분명히 O(N)은 모든 uniq 알고리즘의 복잡성의 하한입니다. 장점은 공간 오버헤드를 제어할 수 있고 정수가 아닌 값 필드에 적응할 수 있다는 것입니다.



下side是桶(bucket)算法的实现：
   var resultArr = [],
       returnArr = [], 
       origLen = this.length,
       resultLen;
   var maxv=this[0],minv=this[0];
   for (var i=1; i       if(this[i]>maxv)maxv=this[i];
       else if(this[i]   }
   var blen=maxv-minv 1;
   var b=new 배열(blen);
   for(var i=0;i   for (var i=0; i       if (b[this[i]-minv]){
           returnArr.push(this[i]); 
       } else {
           resultArr.push(this[i]);
           b[this[i]-minv]=true;
       }
   }
   resultLen = resultArr.length;
   this.length = resultLen;
   for (var i=0; i       this[i] = resultArr[i];
   }
   반환 returnArr;
下面是散列(hash)算法的实现
var shuffler = 37
var beta=0.007;
var origLen=this.length
var bucketSize=Math.ceil(origLen*beta);
var hashSet=new Array(bucketSize); 
var hashFun = function(value){
var key = (Math.floor(value)*shuffler)%bucketSize;
반환 키;
}
//init hashSet
for(var i=0;i//
var ret=[],self=[];
var 키,값; 
var bucket,openLen;
var everContribute;
for(var i=0;ivalue=this[i];
key=hashFun(값);
버킷 = hashSet[키];
openLen=bucket.length;//if(openLen>1)return;
everConflect=false; 
for(var j=0;j if(bucket[j]==value){
  ret.push(value);
  everConflect=true;
  휴식;
 }
}
if(!everContribute){
 bucket.push(value);
 self.push(값);
}
}
   selfLen = self.length;
   this.length = selfLen;
   for (i=0; i       this[i] = self[i];
   }
//평균 버킷 크기 계산
var lens=[],sum=0;
for(var i=0;iaverage=sum/hashSet.length;//시계 렌즈,평균
   return ret;


사용k*10000个0~k*100적随机整数测试计算时间(ms)
k 1 2 3 4 5
realazy 240 693 1399 2301 3807 
버킷 55 101 141 219 293
해시 214 411 654 844 1083
测试框架借鉴了http://realazy.org/lab/uniq.html
测试环境Firefox2.0.0.6/Ubuntu7. 10/2.66 GHzP4/1024MBDDR