Ringkasan enam kaedah untuk mengalih keluar pendua daripada kemahiran javascript arrays_javascript

Soalan yang mesti disediakan oleh penemuduga bahagian hadapan: Cara mengalih keluar pendua daripada Javascript Array. Setahu saya, Baidu, Tencent, Shanda, dan lain-lain semuanya telah bertanya soalan ini dalam temu bual. Soalan ini nampak mudah, tetapi ia sebenarnya mengandungi bahaya tersembunyi. Ujian ini bukan sahaja untuk merealisasikan fungsi ini, tetapi juga tentang pemahaman mendalam anda tentang pelaksanaan program komputer.

Saya menghasilkan sejumlah tiga algoritma untuk mencapai tujuan ini:

Array.prototype.unique1 = function()
{
 var n = []; //一个新的临时数组
 for(var i = 0; i < this.length; i++) //遍历当前数组
 {
 //如果当前数组的第i已经保存进了临时数组，那么跳过，
 //否则把当前项push到临时数组里面
 if (n.indexOf(this[i]) == -1) n.push(this[i]);
 }
 return n;
}
Array.prototype.unique2 = function()
{
 var n = {},r=[]; //n为hash表，r为临时数组
 for(var i = 0; i < this.length; i++) //遍历当前数组
 {
 if (!n[this[i]]) //如果hash表中没有当前项
 {
  n[this[i]] = true; //存入hash表
  r.push(this[i]); //把当前数组的当前项push到临时数组里面
 }
 }
 return r;
}
Array.prototype.unique3 = function()
{
 var n = [this[0]]; //结果数组
 for(var i = 1; i < this.length; i++) //从第二项开始遍历
 {
 //如果当前数组的第i项在当前数组中第一次出现的位置不是i，
 //那么表示第i项是重复的，忽略掉。否则存入结果数组
 if (this.indexOf(this[i]) == i) n.push(this[i]);
 }
 return n;
}

Kaedah pertama dan ketiga menggunakan kaedah indexOf bagi tatasusunan. Tujuan kaedah ini adalah untuk mencari kejadian pertama parameter yang disimpan dalam tatasusunan. Jelas sekali, enjin js akan merentasi tatasusunan sehingga ia menemui sasaran apabila melaksanakan kaedah ini. Jadi fungsi ini membuang banyak masa. Kaedah kedua menggunakan jadual hash. Simpan kejadian dalam objek dalam bentuk subskrip. Rujukan berlangganan adalah lebih pantas daripada mencari tatasusunan menggunakan indexOf.

Untuk menilai kecekapan ketiga-tiga kaedah ini, saya membuat program ujian untuk menjana tatasusunan nombor rawak dengan panjang 10,000, dan kemudian menggunakan beberapa kaedah untuk menguji masa pelaksanaan. Keputusan menunjukkan bahawa kaedah kedua adalah lebih cepat daripada dua kaedah lain. Walau bagaimanapun, dari segi penggunaan memori, kaedah kedua lebih cenderung digunakan kerana terdapat jadual hash tambahan. Inilah yang dinamakan ruang untuk masa. Ini adalah halaman ujian, anda juga boleh menyemaknya.

Menurut idea pakar hpl, saya menulis kaedah keempat:

Array.prototype.unique4 = function()
{
 this.sort();
 var re=[this[0]];
 for(var i = 1; i < this.length; i++)
 {
 if( this[i] !== re[re.length-1])
 {
  re.push(this[i]);
 }
 }
 return re;
}

Idea kaedah ini adalah untuk mengisih tatasusunan dahulu, dan kemudian membandingkan dua nilai bersebelahan. Kaedah isihan asli JS digunakan semasa mengisih Enjin JS harus menggunakan isihan pantas secara dalaman. Keputusan ujian akhir adalah bahawa masa berjalan kaedah ini adalah kira-kira tiga kali ganda daripada kaedah kedua secara purata, tetapi ia adalah lebih cepat daripada kaedah pertama dan ketiga.

Kaedah kelima

Saya baru-baru ini menggunakan fungsi [Sejarah Carian] dan mula menggunakan kaedah indexOf Kaedah ini hanya disokong dalam ECMA5, tetapi tidak disokong dalam IE8-.

Kita boleh menulis fungsi sendiri (kaedah objek Array semuanya ditakrifkan pada objek prototaip), seperti berikut:

Array.prototype.unique = function(){
  var length = this.length;
  if(length <= 1){
    return this;
  }
  if(!Array.prototype.indexOf){    
    Array.prototype.indexOf = function(item){
      var l = this.length, i = 0, r = -1;
      if(l <= 0){
　　　　　　 　　return -1;
　　　　　　　}
      for(; i < l; i++){
        if(this[i] === item){
          r = i;
        }
      }
      return r;
    }
  }
  
  var result = []; //去重数组
  for(var i = 0; i < length; i++){
    if(result.indexOf(this[i]) === -1){
      result.push(this[i]);
    }
  }
  return result;
}

Kaedah keenam

Jenis Tatasusunan tidak menyediakan kaedah deduplikasi Jika anda ingin mengalih keluar elemen pendua daripada tatasusunan, anda perlu mencari jalan sendiri:

function unique(arr) {
  var result = [], isRepeated;
  for (var i = 0, len = arr.length; i < len; i++) {
    isRepeated = false;
    for (var j = 0, len = result.length; j < len; j++) {
      if (arr[i] == result[j]) {  
        isRepeated = true;
        break;
      }
    }
    if (!isRepeated) {
      result.push(arr[i]);
    }
  }
  return result;
}

Idea umum adalah untuk memindahkan elemen tatasusunan ke tatasusunan lain satu demi satu Semasa proses pemindahan, semak sama ada elemen itu diduakan dan jika ya, buang terus. Seperti yang dapat dilihat dari gelung bersarang, kaedah ini sangat tidak cekap. Kita boleh menggunakan struktur hashtable untuk merekodkan elemen sedia ada, supaya gelung dalaman dapat dielakkan.