Résumé de six méthodes pour supprimer les doublons des compétences javascript arrays_javascript

Une question à laquelle les enquêteurs front-end doivent se préparer : Comment supprimer les doublons du tableau Javascript. Pour autant que je sache, Baidu, Tencent, Shanda, etc. ont tous posé cette question lors d'entretiens. Cette question semble simple, mais elle recèle en réalité des dangers cachés. Le test ne porte pas seulement sur la réalisation de cette fonction, mais également sur votre compréhension approfondie de l'exécution d'un programme informatique.

J'ai proposé un total de trois algorithmes pour atteindre cet objectif :

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;
}

Les première et troisième méthodes utilisent toutes deux la méthode indexOf du tableau. Le but de cette méthode est de trouver la première occurrence du paramètre stocké dans le tableau. Évidemment, le moteur js parcourra le tableau jusqu'à ce qu'il trouve la cible lors de l'implémentation de cette méthode. Cette fonction fait donc perdre beaucoup de temps. La deuxième méthode utilise une table de hachage. Stockez les occurrences dans un objet sous forme d'indices. Les références en indice sont beaucoup plus rapides que la recherche dans le tableau à l'aide de indexOf.

Afin de juger de l'efficacité de ces trois méthodes, j'ai réalisé un programme de test pour générer un tableau de nombres aléatoires d'une longueur de 10 000, puis j'ai utilisé plusieurs méthodes pour tester le temps d'exécution. Les résultats montrent que la deuxième méthode est beaucoup plus rapide que les deux autres méthodes. Cependant, en termes d'utilisation de la mémoire, la deuxième méthode est plus susceptible d'être utilisée car il existe une table de hachage supplémentaire. C'est ce qu'on appelle l'espace-temps. Ceci est la page de test, vous pouvez également la consulter.

Selon les idées des experts hpl, j'ai écrit la quatrième méthode :

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;
}

L'idée de cette méthode est de trier d'abord le tableau, puis de comparer deux valeurs adjacentes. La méthode de tri native JS est utilisée lors du tri. Le moteur JS doit utiliser le tri rapide en interne. Le résultat final du test est que le temps d'exécution de cette méthode est en moyenne environ trois fois supérieur à celui de la deuxième méthode, mais il est beaucoup plus rapide que les première et troisième méthodes.

La cinquième méthode

J'ai récemment utilisé la fonction [Search History] et commencé à utiliser la méthode indexOf. Cette méthode n'est prise en charge que dans ECMA5, mais n'est pas prise en charge dans IE8-.

On peut écrire une fonction nous-mêmes (les méthodes de l'objet Array sont toutes définies sur l'objet prototype), comme suit :

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;
}

La sixième méthode

Le type Array ne fournit pas de méthode de déduplication. Si vous souhaitez supprimer les éléments en double du tableau, vous devez trouver un moyen vous-même :

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;
}

L'idée générale est de transférer les éléments du tableau vers un autre tableau un par un. Pendant le processus de transfert, vérifiez si l'élément est dupliqué, et si c'est le cas, supprimez-le directement. Comme le montrent les boucles imbriquées, cette méthode est extrêmement inefficace. Nous pouvons utiliser une structure de table de hachage pour enregistrer les éléments existants, afin d'éviter la boucle interne.