Ma façon de dédoublonner VS lodash

Version imprimable

Ma façon de dédoublonner un array en js, trivial on dirait quand on regarde la façon d'écrire de lodash pour un même résultat, avouez que c'est moins lisible mais au niveau algo c'est + performant :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function removeDuplicate(arr = []){
 
    const { length } = arr;
 
    for(let i= 0 ;i < length; i++){
 
        for(let y= i+1;y < length; y++){
 
           if(arr[y] == arr[i]){
 
                arr.splice(y,1);
                y--;
            }
 
        }
 
    }
    return arr;
 
}

la façon de lodash :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function eq(value, other) {
    return value === other || (value !== value && other !== other)
}
 
function baseSortedUniq(array, iteratee) {
    let seen
    let index = -1
    let resIndex = 0
 
    const { length } = array
    const result = []
 
    while (++index < length) {
        const value = array[index], computed = iteratee ? iteratee(value) : value
 
        if (!index || !eq(computed, seen)) {
            seen = computed
            result[resIndex++] = value === 0 ? 0 : value
        }
    }
    return result
}

la façon ES6 en utilisant Set

Code:

1
2
3
4
5
var arr = [1,2,3,4,1,2,3,1,2,3]
 
var uniqueArr = [...new Set(arr)]
 
console.log(uniqueArr)

A tester, peut-être plus rapide ?

Code:

1
2
3
4
5
6
7
let arr = [1,2,3,4,1,2,3,1,2,3];
let tmp=[];
let i=-1;
while (arr[++i]){
!tmp.includes(arr[i]) && tmp.push(arr[i]);
}
console.log(tmp);

31/08/2021, 15h09
Gobble
Ta méthode semble en effet plus rapide !

Après il y a aussi la méthode filter qui est sympa j'ai trouvé.

Code:

const filteredArr = arr.filter( (el, pos) => arr.indexOf(ele) == pos );

mais le plus performant est
Code:

1 2 3 4 5 var arr = [1,2,3,4,1,2,3,1,2,3] var uniqueArr = [...new Set(arr)] console.log(uniqueArr)
31/08/2021, 15h37
SpaceFrog

il y a une petit coquille dans ton filter ...

Code:

arruniq =arr.filter((x, i, a) => a.indexOf(x) == i)

sinon la librairie underscore propose aussi un _.uniq
31/08/2021, 15h42
Gobble

En effet

Code:

const filteredArr = arr.filter( (el, pos) => arr.indexOf(el) == pos );
01/09/2021, 10h37
NoSmoking

Bonjour,
on a eu, il n'y a pas longtemps sur le forum jQuery, une discussion sur ce sujet : Que vaut la fonction qui classe et enlève les doublons d'un tableau ?

Au post #2 j'aivais fourni une réponse qui reprend effectivement ce qui est mentionné ici.

Une remarque quand même concernant ta première façon de faire, il me semble que de mettre en cache la longueur du tableau à parcourir, const { length } = arr t'expose à des effets de bord attendu que tu es amené à réduire la longueur de celui-ci du fait du arr.splice(y,1).
Tu pourrais donc être amené à vérifier un undefined == undefined et donc décrémenter ton y, et là cela va boucler :calim2:
02/09/2021, 14h46
Loralina

Bonjour,
J'avais lu "déboulonner", je m'attendais à du lourd :!: :haha:
Bon ça va, c'est intéressant quand même. :D

Gobble, je ne sais pas comment tu testes :question: 8O :haha:

:arrow: Dans ton premier message, tu mets un tableau en exemple pour lequel ton code tourne à l'infini (voir remarque de NoSmoking) et sur lequel celui de lodash n'agit pas (pas prévu pour, en fait).
Même [1,1,1], ton code n'en vient pas à bout... :haha:

:arrow: Ensuite concernant la performance, quels tests tu fais ?
Tu dis : "Après il y a aussi la méthode filter qui est sympa j'ai trouvé.", "mais le plus performant est " suivi de l'exemple avec Set.

Avec ton tableau de test, pour moi, c'est filter qui est le plus rapide (très largement sur Firefox, assez nettement sur Chrome et Edge).
Tu as vraiment constaté l'inverse ? Avec d'autres tableaux peut-être ?

À SpaceFrog, tu dis "Ta méthode semble en effet plus rapide !", mais sur la base de tests réels ou d'une vague impression ?!
:roll:

Sinon, concernant le code de lodash, je trouve étonnant qu'il ne soit pas optimisé à fond en vitesse : plutôt que de faire le test iteratee? à chaque itération, pourquoi ne pas l'avoir fait qu'une seule fois avec une boucle pour chacun des deux cas... Même le test systématique !index, je le trouve limite abusé.

Petites remarques sur des tests qui surprennent au premier abord :
- value === other || (value !== value && other !== other) : j'imagine que l'idée c'est de retourner true pour les valeurs NaN...
- value === 0 ? 0 : value : là, je suppose que c'est pour remplacer les -0... Par contre, s'il y a plusieurs -0 d'affilée, on se retrouverait avec un 0... Je pense que c'est un choix comme ça, un peu arbitraire...
02/09/2021, 18h23
Gobble

Hello,

Effectivement, grosse boulette avec la mise en cache du arr.length qui mouline.:oops:

Par contre je n'ai pas compris, concernant le tableau que j'ai mis en exemple ? Lequel ? le tableau en argument par défaut de la fonction ou bien celui déclaré dans l'exemple de set ?

Il me semble avoir testé la méthode de lodash et elle trie bien les valeurs uniques ?

Concernant les tests de performance j'ai utilisé :

Code:

console.time et console.timeEnd

Mais peut être qu'il existe des outils plus performants ? (console.profile(), performance.now()...)

La méthode de spaceFrog est plus rapide que la mienne mais moins rapide que le filter qui est lui même moins rapide que la méthode Set, sur chrome.
03/09/2021, 10h05
SpaceFrog

Citation:

À SpaceFrog, tu dis "Ta méthode semble en effet plus rapide !", mais sur la base de tests réels ou d'une vague impression ?!

Je pense que le plus rapide sera bien entendu

Code:

var uniqueArr = [...new Set(arr)]

Mais par expérience mon petit doigt me dit que la boucle while sera dans le top 3 dans un benchmark

Bonjour,

Citation:

Envoyé par Gobble

le tableau en argument par défaut de la fonction ou bien celui déclaré dans l'exemple de set ?

Celui-là : [1,2,3,4,1,2,3,1,2,3]

Citation:

Envoyé par Gobble

Il me semble avoir testé la méthode de lodash et elle trie bien les valeurs uniques ?

Sur quels tableaux ?
Pour moi, elle marche sur des répétitions successives, exemple :
Code:

1 2 3 4 5 6 7 const arr = [1,2,3,4,1,2,3,1,2,3]; console.log(baseSortedUniq(arr)); //[1,2,3,4,1,2,3,1,2,3] arr.sort(); console.log(baseSortedUniq(arr)); //[1,2,3,4] console.log(baseSortedUniq([2,0,1,1,1,4,5,7,1,8,8])); //[2,0,1,4,5,7,1,8]
Citation:

Envoyé par Gobble

La méthode de spaceFrog est plus rapide que la mienne mais moins rapide que le filter qui est lui même moins rapide que la méthode Set, sur chrome.

Avec quel tableau de test ? Il faudrait voir le code...

Voici un test filter vs Set vs includes avec console.time :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 <script> function test(meth) { const nb=1000000; const arr=[1,2,3,4,1,2,3,1,2,3]; let uniqueArr; console.time(meth); if(meth==="Filter") { for(let i=nb;i>0;i--) { uniqueArr=arr.filter((x,i,a) => a.indexOf(x)===i); } } else if(meth==="Set") { for(let i=nb;i>0;i--) { uniqueArr=[...new Set(arr)]; } } else { for(let i=nb;i>0;i--) { uniqueArr=[]; const {length}=arr; for(let j=0;j<length;j++){ !uniqueArr.includes(arr[j]) && uniqueArr.push(arr[j]); } } } console.timeEnd(meth); console.log(arr,uniqueArr); }; </script> <input type="button" onclick="test(this.value);" value="Filter"> <input type="button" onclick="test(this.value);" value="Set"> <input type="button" onclick="test(this.value);" value="Includes">
Pour la version avec includes :
- J'ai juste changé la boucle de SpaceFrog, c'est un peu plus rapide ainsi.
- Si le code était encapsulé dans une fonction, on perdrait un peu de vitesse.

Chez moi, sur Firefox, Edge et Chrome, la méthode avec Set est clairement la plus lente, sur ce test du moins.

03/09/2021, 14h27
Loralina

Je viens de faire un autre test en multipliant par 100 la taille du tableau à coup de copier-coller et en divisant par 100 le nombre d'itérations :
- Sur Chrome, Set est toujours plus lent, avec une exception : filter est lent sur la première tentative (voire les deux premières) pour ce nombre d'itérations (très variable selon le nombre). :weird:
- Sur Firefox, Set devient le plus rapide, à égalité avec includes.

Cela dépendra donc de la taille du tableau, peut-être de son contenu (à tester) et du navigateur.

Citation:

Envoyé par Loralina

Cela dépendra donc de la taille du tableau, peut-être de son contenu (à tester) et du navigateur.

Pour tester ces méthodes il me semble préférable de ne pas faire de boucle pour appeler la méthode mais de travailler sur des tableaux plus ou moins gros ce qui se rapproche quand même plus de ce qui va se faire, itération interne notamment.

En faisant de la sorte j’obtiens des résultats bien différents : Set toujours gagnant et de loin, includes et Filter, avantage pour Includes mais dépend du navigateur et ... dommage pour Gobble ... toujours la moins rapide :aie:

Je mets ici le fichier réalisé pour test :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
<!DOCTYPE html>
<html lang="fr">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Suppression des doublons d'un Array</title>
<meta name="Author" content="NoSmoking">
<meta name="DVP-discussion" content="d2116761">
<meta name="description" content="Test de « performance », comparaison des méthodes set, includes et filter sur les Array.">
<style>
html, body {margin: 0;padding: 0;font: 1em/1.5 Verdana,sans-serif;}
h1, h2, h3 {margin: .25em 0;color: #069;}
time {float: right;margin: .5em;font-size: 0.9em;color: #888;}
main {display: block;margin: auto;max-width: 60em;}
button {margin: .125em;min-width: 10em;font: inherit;line-height: 2;cursor: pointer;}
#perf {padding-left: 1em;font-family: Courier New;tab-size: 2;}
</style>
<body>
<main>
  <header>
    <time datetime="2021-09-05">Sept. 2021</time>
    <h1>Suppression des doublons d'un Array</h1>
    <p>Test de « performance » des méthodes.
  </header>
  <p class="cde">
    <button onclick="test(this.textContent)">Set</button>
    <button onclick="test(this.textContent)">Includes</button>
    <button onclick="test(this.textContent)">Filter</button>
    <button onclick="test(this.textContent)">Gobble</button>
  </p>
  <section>
    <h2>Résultats</h2>
    <pre id="perf"></pre>
  </section>
  <footer>
    <p>Voir la <a href="https://www.developpez.net/forums/showthread.php?t=2116761">discussion sur Developpez.com</a>
  </footer>
</main>
<script>
"use strict";
const debug = {
  elem: document.getElementById("perf"),
  log: function(txt) {
    this.elem.insertBefore(document.createTextNode(txt + "\n"), this.elem.firstChild);
  },
  clear: function() {
    while (this.elem.firstChild) {
      this.elem.firstChild.remove()
    }
  }
};
 
// création array de réfèrence
const NBR_VALEURS = 50000;  // !! c'est suffisant pour le test
const tabRef = new Array(NBR_VALEURS).fill(0).map((el, ind) => Math.floor(Math.random() * NBR_VALEURS))
 
function test(meth) {
  const arr = [...tabRef];
  let uniqueArr;
 
  const deb = performance.now();
  switch (meth.trim().toLowerCase()) {
    case 'filter':
      uniqueArr = arr.filter((x, i, a) => a.indexOf(x) === i);
      break;
    case 'set':
      uniqueArr = [...new Set(arr)];
      break;
    case 'includes':
      uniqueArr = [];
      const {length} = arr;
      for (let j = 0; j < length; j++) {
        !uniqueArr.includes(arr[j]) && uniqueArr.push(arr[j]);
      }
      break;
    case 'gobble':
      for (let i = 0; i < arr.length; i += 1) {
        for (let y = i + 1; y < arr.length; y += 1) {
          if (arr[y] == arr[i]) {
            arr.splice(y, 1);
            y--;
          }
        }
      }
      uniqueArr = arr;
      break;
  }
 
  const end = performance.now();
  debug.log(`${meth} : ${Math.floor(end-deb)} ms \t-> récup. de ${uniqueArr.length} éléments`);
}
debug.log(`\nTest réalisé sur un Array de ${tabRef.length} éléments`);
</script>
</body>
</html>

Ici on ne travail qu'avec des valeurs numériques, il conviendrait de tester avec des contenus de même type mais de nature différente, objet par exemple, pour être un peu plus complet.

Je vous laisse regarder et en tirer certaines conclusions intéressantes comme le fait qu'il n'y a pas de linéarité dans les résultats lorsque l'on augmente/diminue le nombre d'enregistrements traités.
Attention toutefois de ne pas être trop gourmand le navigateur pourrait ne pas aimer cela ;)

Le fichier de test en ligne :

Suppression des doublons d'un Array

03/09/2021, 19h22
Loralina

Bonsoir,

Citation:

Envoyé par NoSmoking

Pour tester ces méthodes il me semble préférable de ne pas faire de boucle pour appeler la méthode mais de travailler sur des tableaux plus ou moins gros ce qui se rapproche quand même plus de ce qui va se faire, itération interne notamment.

Le mieux c'est de tester les deux en fait, car si une application utilise des petits tableaux, il n'est pas plus mal de savoir quelle méthode est la plus performante (même si le gain sera sans doute minime).
Mais je suis d'accord que Set s'en sort bien globalement et qu'il prend vite le dessus, genre dès 50 valeurs.

Gobble avait sans doute testé avec des tableaux suffisamment grands et pas simplement le petit [1,2,3,4,1,2,3,1,2,3]. :question:

Pour les grands tableaux, je constate que les méthodes basées sur filter et includes vont beaucoup plus vite s'il y a beaucoup de répétitions (tester par exemple : Math.floor(Math.random() * 100)).
La constitution du tableau final semble beaucoup leur coûter.
04/09/2021, 11h15
Loralina

Bonjour,
Deux petites choses :

1)

Citation:

Envoyé par Loralina

La constitution du tableau final semble beaucoup leur coûter.

Correction : après reconsidération et test, c'est plutôt la recherche des éléments lointains qui coûte (a.indexOf(x) et includes(arr[j])).
Par exemple, que vous ajoutiez && false (donc 0 valeur retenue) ou || true (toutes les valeurs retenues) dans le filter, le temps d'exécution sera du même ordre.
Mais si vous mettez juste true (toutes les valeurs retenues), le temps tombera presque à 0.

2) Puisque j'en avais parlé, j'ai testé les valeurs -0 et NaN ainsi que, par la même occasion, des <empty slots>.
Tableau de test : [-0,-0,0,0,NaN,NaN,,,].
- Filter :arrow: [-0]
- Set :arrow: [0,NaN,undefined]
- Includes :arrow: [-0,NaN,undefined]

Remarque bonus sous forme de question : [0] longeur 1 d'accord, mais pour [0,], quelle longueur et combien de <empty slots> vous diriez sans tester ? ;)
04/09/2021, 18h41
Gobble

Citation:

Remarque bonus sous forme de question : [0] longeur 1 d'accord, mais pour [0,], quelle longueur et combien de <empty slots> vous diriez sans tester ?

2 et 1 empty slot ?

Bonsoir Gobble,
C'est ce qu'on serait tenté de supposer, mais ajouter une seule virgule ne change rien :
[0,] :longueur 1, pas d'emplacement vide.

Après tout, c'est un peu logique : s'il y avait un emplacement vide après la virgule, on ne pourrait pas initialiser un tableau de longueur 1 sans valeur avec juste crochets et virgules.
[,] : longueur 1, 1 emplacement vide.
[,,] : longueur 2, 2 emplacements vides.

Pour rester dans le sujet, je pense qu'il sera généralement préférable d'ignorer les emplacements vides dans le traitement.
Bien sûr, ce n'est pas très courant d'avoir des emplacements vides, mais, conceptuellement, cela peut être pratique, par exemple si l'index des éléments a une signification particulière.
A noter qu'on peut utiliser delete pour remettre une case à vide.
Code:

1 2 3 4 5 6 <script> const arr=[1,,2,1,3,2,3]; console.log(arr.filter((x,i,a) => a.indexOf(x)===i)); //[1,2,3] console.log([...new Set(arr)]); //[1,undefined,2,3] console.log([...new Set(arr.filter(() => true))]); //[1,2,3] </script>
6/9 8h50 : j'ajoute une version avec Set qui permet d'ignorer les emplacements vides et qui devrait rester très rapide pour les grands tableaux.

08/09/2021, 10h29
NoSmoking

Citation:

6/9 8h50 : j'ajoute une version avec Set qui permet d'ignorer les emplacements vides et qui devrait rester très rapide pour les grands tableaux.

Tu pourrais également faire un simple :

Code:

console.log([...new Set(arr.flat())]); //[1,2,3]

Bonjour NoSmoking,
Oui, merci, en revanche, autant Firefox s'en fiche, c'est pareil pour lui, autant Chrome ne semble pas trouver ça plus simple, lui ! :ouin:
Nettement plus long avec flat. 8O

Je laisse un script de test.
J'ai un peu abusé sur le copier-coller :haha:, j'espère qu'il n'y aura pas d'erreur. :)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
<script>
function tableau(length,prob) {
	const arr=new Array(length);
	for(let i=length-1;i>=0;i--) {
		if(Math.random()<prob) {
			arr[i]=Math.floor(Math.random()*length*prob);
		}
	}
	return arr;
}
 
function test(meth,arr) {
	let nb;
	let uniqueArr;
 	nb=arr.length<100?100000:1;
	console.time(meth);
	if(meth==="Set(arr)") {
		for(let i=nb;i>0;i--) {
			uniqueArr=[...new Set(arr)];
		}
	}
	else if(meth==="Set(arr.flat())") {
		for(let i=nb;i>0;i--) {
			uniqueArr=[...new Set(arr.flat())];
		}
	}
	else {
		for(let i=nb;i>0;i--) {
			uniqueArr=[...new Set(arr.filter(()=>true))];
		}
	}
	console.timeEnd(meth);
	if(arr.length<100) {
		console.log(arr,uniqueArr);
	}
	else {
		console.log(arr.length,uniqueArr.length);
	}
}
 
let length=10;
const arrA0=tableau(length,0);
const arrA05=tableau(length,0.5);
const arrA1=tableau(length,1);
 
length=100000;
const arrB0=tableau(length,0);
const arrB05=tableau(length,0.5);
const arrB1=tableau(length,1);
</script>
Tableau vide, longeur 10
<input type="button" onclick="test(this.value,arrA0);" value="Set(arr)">
<input type="button" onclick="test(this.value,arrA0);" value="Set(arr.flat())">
<input type="button" onclick="test(this.value,arrA0);" value="Set(arr.filter(()=>true))">
<br><br>
Tableau mi-plein, longeur 10
<input type="button" onclick="test(this.value,arrA05);" value="Set(arr)">
<input type="button" onclick="test(this.value,arrA05);" value="Set(arr.flat())">
<input type="button" onclick="test(this.value,arrA05);" value="Set(arr.filter(()=>true))">
<br><br>
Tableau plein, longeur 10
<input type="button" onclick="test(this.value,arrA1);" value="Set(arr)">
<input type="button" onclick="test(this.value,arrA1);" value="Set(arr.flat())">
<input type="button" onclick="test(this.value,arrA1);" value="Set(arr.filter(()=>true))">
<br><br>
Tableau vide, longeur 100000
<input type="button" onclick="test(this.value,arrB0);" value="Set(arr)">
<input type="button" onclick="test(this.value,arrB0);" value="Set(arr.flat())">
<input type="button" onclick="test(this.value,arrB0);" value="Set(arr.filter(()=>true))">
<br><br>
Tableau mi-plein, longeur 100000
<input type="button" onclick="test(this.value,arrB05);" value="Set(arr)">
<input type="button" onclick="test(this.value,arrB05);" value="Set(arr.flat())">
<input type="button" onclick="test(this.value,arrB05);" value="Set(arr.filter(()=>true))">
<br><br>
Tableau plein, longeur 100000
<input type="button" onclick="test(this.value,arrB1);" value="Set(arr)">
<input type="button" onclick="test(this.value,arrB1);" value="Set(arr.flat())">
<input type="button" onclick="test(this.value,arrB1);" value="Set(arr.filter(()=>true))">

08/09/2021, 19h04
NoSmoking

Citation:

Oui, merci, en revanche, autant Firefox s'en fiche, c'est pareil pour lui, autant Chrome ne semble pas trouver ça plus simple, lui ! :ouin:
Nettement plus long avec flat. 8O

Effectivement après tests rapides, les optimisations des uns ne sont pas les optimisations des autres et inversement ...