Empat kaedah praktikal untuk mengalih keluar pendua daripada kemahiran js arrays_javascript

Soalan yang mesti disediakan oleh penemuduga bahagian hadapan: Cara mengalih keluar pendua daripada Tatasusunan Javascript. 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 tentang melaksanakan fungsi ini, tetapi juga tentang pemahaman mendalam anda tentang pelaksanaan program komputer.

Saya menghasilkan sejumlah tiga algoritma untuk mencapai 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 kedua-duanya menggunakan kaedah indexOf 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.

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.