Dédoublonner efficacement un tableau

Par Christophe Porteneuve • Publié le 4 mai 2020 • 4 min

La série des 19

Extrait de la liste des articles :

1. Dédoublonner efficacement un tableau (cet article)
2. Extraire efficacement une sous-chaîne de texte
3. Formater proprement un nombre
4. …au-delà, c’est la surprise ! (mais les 19 sont déjà calés)…

« Dédoublonner » ?

Dédoublonner, ou dédupliquer (en anglais, deduplicate, un doublon étant un duplicate) : l’action de retirer dans une liste toutes les occurrences surnuméraires de valeurs, pour ne conserver au final que des valeurs uniques.

La liste n’est pas obligatoirement triée et les valeurs ne sont pas obligatoirement d’un type uniforme. L’implémentation peut par ailleurs choisir de préserver l’ordre (d’être « stable ») des valeurs d’origine conservées, ou pas.

Le genre de mots qu’on utilise assez peu dans la vie de tous les jours.

À l’ancienne

Pas tellement d’autre choix que de traverser toute la liste.

Si on ne peut pas supposer qu’elle était triée (et que les valeurs ne sont pas forcément des Strings) c’est encore plus moche : à chaque fois, on devra parcourir le résultat courant pour voir si la valeur n’y existe pas déjà ! Un parcours dans un parcours : l’algo est quadratique, de complexité O(n²). En gros, si tu as un tableau de mille éléments, tu fais un million de tours… Une implémentation un poil naïve (surtout vu qu’on est manifestement en ES2015+) pourrait ressembler à ça :

function naiveUniq(items) {
  const result = []
  for (const item of items) {
    if (!result.includes(item)) {
      result.push(item)
    }
  }
  return result
}

Si tu te sens désarçonné·e par for…of ou Array#includes(…), donc plutôt ES3 (pré-2009) dans l’esprit, tu as cette version-ci, encore plus lente :

function lousyUniq(items) {
  var result = [],
    len = items.length
  for (var index = 0; index < len; ++index) {
    var item = items[index]
    if (result.lastIndexOf(item) === -1) {
      result.push(item)
    }
  }
  return result
}

Si tu peux supposer que items est « triée » à la base (les valeurs identiques sont adjacentes), tu gagnes beaucoup en évitant de reparcourir result à chaque fois. Ton algo passe de quadratique à linéaire (O(n), donc mille éléments donnent mille tours) :

function sortedUniq(items) {
  const result = []
  let lastSeen
  let first = true
  for (const item of items) {
    if (first || lastSeen !== item) {
      result.push(item)
      first = false
      lastSeen = item
    }
  }
  return result
}

Bon, c’est pas la fête. Si tes valeurs sont toutes des Strings, tu peux optimiser un peu la vérification d’existence, mais à peine, en utilisant un objet comme dictionnaire, et en mettant les clés dedans, pour tester avec seen.hasOwnProperty(item) ou plus basiquement seen[item], mais c’est pas fou (changer la « forme » de seen à chaque ajout de valeur rencontrée pour la première fois pète pour l’essentiel les optimisations de consultation).

« Oui, mais Lodash ! »

Absolument ! Lodash a depuis longtemps uniq et ses copains (uniqWith, uniqBy, sortedUniq, etc.). On ne l’a d’ailleurs pas attendu, puisque Prototype.js le faisait déjà en 2005.

Comme un·e boss

Bien sûr, si vous avez des besoins avancés (comparateur maison, clé dérivée, etc.) vous aurez besoin de Lodash ou consorts. Mais pour le cas de base : dédoublonner les valeurs nues, l’astuce, depuis ES2015, consiste à passer par un Set.

Set est un des deux nouveaux types de collection, avec Map, qui a fait son apparition en 2015 dans la bibliothèque standard du langage. Ce type, qu’on retrouve dans de nombreux écosystèmes, représente un ensemble, au sens mathématique. Il est en particulier caractérisé par deux aspects :

• Il n’a pas d’ordre intrinsèque
• Toutes les valeurs sont uniques

En pratique, undefined, null et NaN sont des valeurs comme les autres. Set utilise pour ses comparaisons le pseudo-algorithme SameValueZero défini par la spécification de JavaScript. C’est comme l’égalité stricte (opérateur ===, qui vérifie d’abord que le type est le même, et le cas échéant compare les valeurs), à un détail près : -0, 0 et +0 sont considérés identiques. Je doute que ce micro-détail vous gêne 😉

Il se trouve qu’un Set peut être construit sur base d’un itérable quelconque. Il y a des tas d’itérables (ce qui rend notre code encore plus générique et utile !), mais Array est sans doute le plus connu.

On pourrait donc faire :

const result = new Set(items)

Construire un Set en lui passant un itérable constitue en quelque sorte la variante optimisée d’un peuplement manuel, qui parcourerait l’itérable (avec un for…of justement) et appellerait add(…) à chaque fois, mais sémantiquement, c’est pareil. Avantage sympathique : l’ordre est donc préservé, l’algo est « stable » de ce point de vue.

La définition de add(…) veut qu’elle ignore tout argument qui serait déjà présent dans le Set. En interne, l’implémentation utilise des structures de données optimisées pour le stockage et la vérification d’existence, faute de notion d’ordre. C’est pourquoi un set.has(x), qui est généralement en O(log(n)), est potentiellement beaucoup plus performant qu’un arr.includes(x), lequel est en O(n). Tu préfères quoi, 3–4 tours ou mille tours ?

Bon, mais on se retrouve avec un Set, pas un joli Array sur lequel on aurait plein de méthodes pratiques… Comment retomber sur nos pattes ?

Un Set est un itérable lui aussi, ce qui veut dire qu’on peut le spreader avec l’opérateur ..., de sorte que pour en faire à nouveau un Array, il suffit de faire ça :

const result = [...new Set(items)]

En spreadant dans un littéral tableau ([…]), on obtient bien un Array au final. Au prix d’une consommation de l’ensemble, de complexité O(n), pour un coût total de l’ordre de O(2n log(n)), ce qui reste nettement mieux que O(n²). Petit comparatif, en supposant 10ns de temps de comparaison SameValueZero, ce qui n’est pas déconnant :

Ahem.

Et voilà !

function lovelyUniq(items) {
  return [...new Set(items)]
}

Si items était « triée », il faudrait mesurer dans le cas précis concerné si une accumulation manuelle avec un Set de contrôle donnerait de meilleurs résultats, mais j’en doute : les itérations manuelles sont souvent plus coûteuses que celles implémentées dans le code natif de la bibliothèque standard. L’écart éventuel sera sans doute trop mince pour justifier le volume de code supplémentaire et tout ce qu’il entraîne (documentation, tests, etc.).