|
|
形式化描述：
input
Array(size=N)
output
Array1=Array的無(wú)重復(fù)保序的子集，
無(wú)重復(fù)是指，對(duì)任意a,b屬于Array1，a!=b
保序是指，若a在Array的下標(biāo)小于b在Array的下標(biāo)，則a在Array1中的下標(biāo)也小于b在Array的下標(biāo)
Array2=Array-Array1，保序
realazy給出了一個(gè)新解，思路非常清晰：順序遍歷訪問(wèn)每個(gè)元素，如果這個(gè)元素的值已經(jīng)訪問(wèn)過(guò)了，則加入Array2，否則加入Array1。判斷當(dāng)前元素的值是否已經(jīng)訪問(wèn)過(guò)所采用的方法是順序遍歷已經(jīng)訪問(wèn)過(guò)的所有元素。
易見(jiàn)該算法復(fù)雜度約O(N^2)。
我在他的算法框架下稍微做了一些改進(jìn)，關(guān)鍵在于遍歷過(guò)程中如何判斷當(dāng)前元素的值是否已經(jīng)訪問(wèn)過(guò)。在原數(shù)組值域?yàn)檎麛?shù)且極差（range=max value-min value）不太大的條件下，可以采用簡(jiǎn)單的"桶"算法。
準(zhǔn)備一個(gè)長(zhǎng)度為range的boolean數(shù)組b，初始化全為false。對(duì)于原數(shù)組中每個(gè)值value，如果b[value]=true，則表明這個(gè)值訪問(wèn)過(guò)，放入Array2，否則放入Array1同時(shí)令b[value]=true。
這顯然是O(N)的算法，代價(jià)是額外的空間復(fù)雜度range，而且要求原數(shù)組值域?yàn)檎麛?shù)。
不難推廣到值域?yàn)檎麛?shù)的情形，事實(shí)上只需考察桶號(hào)value-min(Array)即可轉(zhuǎn)化為正整數(shù)的情形。
為了避免range太大造成的空間的浪費(fèi)，在"桶"算法基礎(chǔ)上改進(jìn)為散列算法，具體說(shuō)來(lái)是線性同余開(kāi)散列法。目的是將值域壓縮映射到一個(gè)可控的小的連續(xù)正整數(shù)子集中，同時(shí)保證不同的原象對(duì)應(yīng)的相同的象的概率要盡可能小，也就是說(shuō)桶與桶之間要盡量負(fù)載均衡。
例如這是一個(gè)值域?yàn)閷?shí)數(shù)的散列函數(shù)：
key=hashFun(value)=Math.floor(value)*37%91
這仍然是O(N)的算法，（顯然O(N)是所有uniq算法的復(fù)雜度下界），好處是可以控制空間的開(kāi)銷，而且可以適應(yīng)非整數(shù)值域，只需要設(shè)計(jì)相應(yīng)的散列函數(shù)即可。
下面是桶(bucket)算法的實(shí)現(xiàn)：
var resultArr = [],
returnArr = [],
origLen = this.length,
resultLen;
var maxv=this[0],minv=this[0];
for (var i=1; i<origLen; ++i){
if(this[i]>maxv)maxv=this[i];
else if(this[i]<minv)minv=this[i];
}
var blen=maxv-minv+1;
var b=new Array(blen);
for(var i=0;i<blen;++i)b[i]=false;
for (var i=0; i<origLen; ++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<resultLen; ++i){
this[i] = resultArr[i];
}
return returnArr;
下面是散列(hash)算法的實(shí)現(xiàn)
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;
return key;
}
//init hashSet
for(var i=0;i<bucketSize;i++)hashSet[i]=new Array();
//
var ret=[],self=[];
var key,value;
var bucket,openLen;
var everConflict;
for(var i=0;i<origLen;i++){
value=this[i];
key=hashFun(value);
bucket = hashSet[key];
openLen=bucket.length;//if(openLen>1)return;
everConflict=false;
for(var j=0;j<openLen;j++){
if(bucket[j]==value){
ret.push(value);
everConflict=true;
break;
}
}
if(!everConflict){
bucket.push(value);
self.push(value);
}
}
selfLen = self.length;
this.length = selfLen;
for (i=0; i<selfLen; ++i){
this[i] = self[i];
}
//compute average bucket size
var lens=[],sum=0;
for(var i=0;i<hashSet.length ;++i){lens.push(hashSet[i].length);sum+=hashSet[i].length};
average=sum/hashSet.length;//watch lens,average
return ret;
用k*10000個(gè)0~k*100的隨機(jī)整數(shù)測(cè)試計(jì)算時(shí)間(ms)
k 1 2 3 4 5
realazy 240 693 1399 2301 3807
bucket 55 101 141 219 293
hash 214 411 654 844 1083
測(cè)試框架借鑒了http://realazy.org/lab/uniq.html
測(cè)試環(huán)境Firefox2.0.0.6/Ubuntu7.10/2.66GHzP4/1024MBDDR
JavaScript技術(shù)：JavaScript 數(shù)組的 uniq 方法，轉(zhuǎn)載需保留來(lái)源！
鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。
