JavaScript の uniq メソッド array_javascript ヒント

プロトタイプ メソッドを Array ローカル オブジェクトに追加します。その目的は、配列エントリ内の重複エントリ (複数ある場合があります) を削除することです。戻り値は、削除された重複エントリを含む新しい配列です。

正式な説明:
入力
Array(size=N)
出力
Array1=重複と順序保持のない配列のサブセット、
重複なしを意味します。 a, b は Array1 に属し、a!=b
順序保持とは、Array の a の添字が Array の b の添字より小さい場合、Array1 の a の添字も b の添字よりも小さいことを意味します。配列内で
Array2=Array-Array1 とマークされ、順序を保持する
により新しい解決策が得られます。アイデアは非常に明確です。シーケンシャル トラバーサルは各要素にアクセスし、この要素の値がアクセスされている場合はそれを追加します。 Array2、そうでない場合は Array1 を追加します。現在の要素の値がアクセスされたかどうかを判断するために使用される方法は、アクセスされたすべての要素を順番に走査することです。
このアルゴリズムの複雑さは約 O(N^2) であることが簡単にわかります。

私は彼のアルゴリズム フレームワークに基づいて若干の改善を加えました。重要なのは、現在の要素の値が走査プロセス中に訪問されたかどうかを判断する方法にあります。元の配列の値の範囲が正の整数であり、範囲 (範囲=最大値-最小値) が大きすぎないという条件下では、単純な「バケット」アルゴリズムを使用できます。
範囲の長さのブール配列 b を用意し、すべて false に初期化します。元の配列の各値の値について、b[value]=true の場合、値がアクセスされて Array2 に配置されたことを意味します。それ以外の場合、値は Array1 に配置され、b[value]=true になります。
これは明らかに O(N) アルゴリズムであり、コストは追加の空間複雑さの範囲であり、元の配列値の範囲は正の整数である必要があります。
値の範囲が整数である場合に一般化することは難しくありません。実際には、バケット番号 value-min (配列) を正の整数に変換できる場合を調べるだけで済みます。

範囲が大きすぎることによるスペースの無駄を避けるために、ハッシュ アルゴリズムは「バケット」アルゴリズム、具体的には線形合同オープン ハッシュ法に基づいて改良されています。目的は、値の範囲を圧縮し、それを連続した正の整数の制御可能な小さなサブセットにマッピングすると同時に、異なる元のイメージが同じイメージに対応する確率を可能な限り小さくすることです。つまり、バケット間の負荷を次のようにする必要があります。可能な限りバランスをとります。
たとえば、これは実数範囲のハッシュ関数です:
key=hashFun(value)=Math.floor(value)*37�
これはまだ O(N) アルゴリズムです (明らかに、O(N) はすべての uniq アルゴリズムの複雑さの下限です)。利点は、スペースのオーバーヘッドを制御でき、対応するハッシュ関数を設計するだけで済むことです。



下はバケツ(バケット)演算法の实现：
var resultArr = [],
returnArr = [],
origLen = this.length,
結果Len;
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=新しい 配列(ブレンド);
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];
}
return returnArr;
下は分散列(ハッシュ)算法の計算です
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 everConflict;
for(var i=0;ivalue=this[i];
キー=ハッシュファン(値);
バケット = ハッシュセット[キー];
openLen=bucket.length;//if(openLen>1)return;
everConflict=false; 
for(var j=0;j if(bucket[j]==value){
ret.push(value);
everConflict=true;
休憩;
}
}
if(!everConflict){
bucket.push(value);
self.push(value);
}
}
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;//watch lens,average
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