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

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

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

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

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

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

function toSetUniq(arr) {
  return Array.from(new Set(arr));
}

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

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)

Les résultats sont les suivants

hashTable 168ms
sortUniq 332ms
toSetUniq 80ms
indexOfUniq 4280ms
doubleLoopUniq 13303ms
inPlaceUniq 9977ms

---

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

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

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
}

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!