Maison > interface Web > js tutoriel > le corps du texte

Exemples détaillés de plusieurs idées de déduplication de tableaux JavaScript

小云云
Libérer: 2018-02-08 16:14:00
original
1480 Les gens l'ont consulté

L'exigence pour la déduplication des données est en fait que les bibliothèques d'outils telles que lodash aient des implémentations matures et complètes et puissent être utilisées de manière mature dans des environnements de production. Mais cela ne nous empêche pas, dans la perspective d’une réflexion sur l’expansion, de voir comment la suppression des doublons peut être obtenue en utilisant plusieurs idées. Cet article partage principalement avec vous plusieurs idées de déduplication des tableaux JavaScript.

Le premier est la mise en œuvre de l'idée conventionnelle de comparaison de boucles à double couche

function doubleLoopUniq(arr) {
  let result = [];
  for (let i = 0, len = arr.length, isExist; i < len; i++) {
    // 定义一个变量表示当前元素在 result 中是否存在。
    isExist = false;
    for (let j = 0, rLen = result.length; j < rLen; j++) {
      if (result[j] === arr[i]) {
        // 依次对result 中的元素 和 原数组元素进行比对。
        isExist = true;
        break;
      }
    }
    // 最后判断如果不存在,则将此元素插入result
    !isExist && result.push(arr[i]);
  }
  return result;
}
Copier après la connexion

Utilisez l'indexOf intégré de js pour supprimer les doublons

function indexOfUniq(arr) {
  let result = [];
  for (let i = 0, len = arr.length; i < len; i++) {
    // 用indexOf 简化了二层循环的流程
    if (result.indexOf(arr[i]) === -1) result.push(arr[i]);
  }
  return result;
}
Copier après la connexion

Comparez avant et après avoir trié Déduplication

function sortUniq(arr) {
  let result = [], last;
  // 这里解构是为了不对原数组产生副作用
  [ ...arr ].sort().forEach(item => {
    if (item != last) {
      result.push(item);
      last = item;
    }
  });
  return result;
}
Copier après la connexion

Déduplication via hashTable

function hashUniq(arr) {
  let hashTable = arr.reduce((result, curr, index, array) => {
    result[curr] = true;
    return result;
  }, {})
  return Object.keys(hashTable).map(item => parseInt(item, 10));
}
Copier après la connexion

ES6 SET une ligne de code pour réaliser la déduplication

function toSetUniq(arr) {
  return Array.from(new Set(arr));
}
Copier après la connexion

déduplication d'épissure (exploite directement le tableau lui-même, avec des effets secondaires )

function inPlaceUniq(arr) {
  let idx = 0;
  while (idx < arr.length) {
    let compare = idx + 1;
    while (compare < arr.length) {
      if (arr[idx] == arr[compare]) {
        arr.splice(compare, 1);
        continue;
      }
      ++compare
    }
    ++idx;
  }
  return arr;
}
Copier après la connexion

Enfin, lancez un test simple sous nodejs pour voir lequel est le plus efficace~

let data = [];
for (var i = 0; i < 100000; i++) {
  data.push(Math.random())
}

// 实现一个性能测试的装饰器
function performanceTest(fn, descript) {
  var a = new Date().getTime();
  return function () {
    fn.apply(this, [].slice.call(arguments, 0));
    console.log(descript, new Date().getTime() - a)
  }
}

performanceTest(hashUniq, "hashTable")(data)
performanceTest(sortUniq, "sortUniq")(data)
performanceTest(toSetUniq, "toSetUniq")(data)
performanceTest(indexOfUniq, "indexOfUniq")(data)
performanceTest(doubleLoopUniq, "doubleLoopUniq")(data)
performanceTest(inPlaceUniq, "inPlaceUniq")(data)
Copier après la connexion

Les résultats sont les suivants

hashTable 168ms
sortUniq 332ms
toSetUniq 80ms
indexOfUniq 4280ms
doubleLoopUniq 13303ms
inPlaceUniq 9977ms
Copier après la connexion

Réflexions approfondies : Comment supprimer les doublons si les éléments du tableau sont des objets ?

Comme il s'agit d'un type référence, deepEqual sera forcément utilisé. Même si cette idée peut répondre à ce problème, elle n'est forcément pas assez efficace.

Le test ci-dessus montre également que la déduplication via les nouveaux Set et hashTable est la plus efficace.
Il ne fait donc aucun doute que nous devons transformer en fonction de ces deux méthodes. Je souhaite utiliser hashTable
D'un autre côté, afin de réduire le temps causé par une comparaison approfondie, j'essaie d'utiliser. JSON.stringify pour référencer Le type est converti en type de base.

function collectionUniq(collection) {
  let hashTable = {};
  collection.forEach(item => {
    hashTable[JSON.stringify(item)] = true;
  })
  return Object.keys(hashTable).map(item => JSON.parse(item))
}
Copier après la connexion

Ensuite, voici le problème. Nous savons tous que les attributs des objets ne sont pas ordonnés. Si les données sont comme ça, alors c'est GG.

let collection = [ { a: 1, b: 2, c: 3 }, { b: 2, c: 3, a: 1 } ]
Copier après la connexion

Il y a une idée toHash. Après avoir effectué une déduplication de base sur ce tableau, afin de garantir l'exactitude,
parcourez d'abord la chaîne JSON=>
Obtenez l'encodage Unicode de chaque chaîne via charCodeAt() =>
Add pour obtenir un nombre total, et enfin comparez-les par paires. Ceux qui ont des valeurs égales sont des doublons, obtenant ainsi l'effet de déduplication.

function toHash(obj) {
  let power = 1;
  let res = 0;
  const string = JSON.stringify(obj, null, 2);
  for (let i = 0, l = string.length; i < l; i++) {
    switch (string[i]) {
      case '{':
        power *= 2
        break
      case '}':
        power /= 2
        break
      case ' ':
      case '\n':
      case '\r':
      case '\t':
      break
      default:
        res += string[i].charCodeAt(0) * power
    }
  }
  return res
}
Copier après la connexion

Ceci n'est qu'une idée de base pour la mise en œuvre, et il y a beaucoup de place à l'amélioration. Afin de réduire le risque de collisions de hachage, le poids de certains caractères spéciaux peut être augmenté ou diminué.

La clé est de s'assurer que le risque de collision est inférieur à celui de gagner le jackpot.

Recommandations associées :

Partage de plusieurs méthodes de déduplication de tableau JavaScript

Implémentation PHP du code de la méthode de déduplication de tableau

Implémentation simple en JS de l'analyse de la méthode de déduplication de tableau

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal