Trouver sur la toile une fonction JavaScript de calcul d’intersection de tableaux qui soit efficace sur des tableaux dépassant les 50 entrées relève de l’impossible. C’est bien simple, les différentes solutions que j’ai pu rencontrer réalisent des calculs linéaires donc autant dire qu’à partir d’un certain seuil leurs performances deviennent catastrophiques.

C’est pourquoi je vous propose ici une fonction de recherche des intersections pour un nombre arbitraire de grands tableaux plus efficace que ce que j’ai pu tester, benchmarks à l’appui. Est également disponible la suite des tests unitaires.

Benchmark réalisé sous Google Chrome 5.0.375.99 / Mac Pro 2 x 3 Ghz Quad-Core Intel Xeon / Mac OS X 10.5.8

Benchmark réalisé sous Google Chrome 5.0.375.99 / Mac Pro 2 x 3 Ghz Quad-Core Intel Xeon sous Mac OS X 10.5.8

La fonction array_big_intersect()

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
/**
 * Compute the intersection of big arrays.
 *
 * @author  Mehdi Kabab <http://pioupioum.fr/>
 * @license http://www.opensource.org/licenses/mit-license.php MIT License.
 * @see     http://pioupioum.fr/developpement/javascript-array-intersection.html
 * @version 1.0.1
 *
 * @param  {Array} arr1 First array.
 * @param  {Array} arr2 Second array.
 * @param  {Array} [arr3[, arr4[, ...]]] Optional arrays.
 * @return {Array} A new array containing elements common to the arrays passed
 *                 in arguments, with no duplicates.
 */
function array_big_intersect () {
  var args = Array.prototype.slice.call(arguments),
      aLower = [],
      aStack = [],
      count,
      i,
      nArgs,
      nLower,
      oRest = {},
      oTmp = {},
      value,
      compareArrayLength = function (a, b) {
        return (a.length - b.length);
      },
      indexes = function (array, oStack) {
        var i = 0,
            value,
            nArr = array.length,
            oTmp = {};
 
        for (; nArr > i; ++i) {
          value = array[i];
          if (!oTmp[value]) {
            oStack[value] = 1 + (oStack[value] || 0); // counter
            oTmp[value] = true;
          }
        }
 
        return oStack;
      };
 
  args.sort(compareArrayLength);
  aLower = args.shift();
  nLower = aLower.length;
 
  if (0 === nLower) {
    return aStack;
  }
 
  nArgs = args.length;
  i = nArgs;
  while (i--) {
    oRest = indexes(args.shift(), oRest);
  }
 
  for (i = 0; nLower > i; ++i) {
    value = aLower[i];
    count = oRest[value];
    if (!oTmp[value]) {
      if (nArgs === count) {
        aStack.push(value);
        oTmp[value] = true;
      }
    }
  }
 
  return aStack;
}

Un gain de performances

Le gain de performances tient à peu de choses. En premier lieu, l’ordre d’analyse des tableaux est un point à ne pas négliger. Par définition, l’ensemble des valeurs constituant l’intersection se retrouve dans le plus petit des tableaux. De ce fait, je me base sur le plus petit d’entre-eux pour effectuer les comparaisons de présence d’une valeur dans les ensembles restants.

Aussi, la fonction crée un Hash de toutes les valeurs uniques et stocke leur fréquence d’apparition. Si une valeur apparaît autant de fois qu’il y a de tableaux, c’est qu’une intersection est trouvée.

Et c’est tout :-)

Petit avertissement, si vous avez à travailler sur des tableaux de petites tailles, je vous conseille plutôt d’utiliser la fonction Array#intersect() de la librairie JSLab qui s’avère être des plus performantes.

Anecdote

Anecdote (ou pas), mon benchmark met en évidence des erreurs de calcul de la part des librairies Prototype et Extensions. La seconde ayant moins d’impact car peu propagée, il en est tout autre pour Prototype. En effet, cette dernière exclue systématiquement la valeur 0 (zéro) du tableau résultant. Ce qui est plus qu’embarrassant, pourtant le bug est connu depuis fin 2009.

publicité (chargement)

6 réponses pour JavaScript : optimiser le calcul de l’intersection de tableaux de grandes tailles

  1. jpvincent dit :

    merci d’avoir partagé ce code !

    est ce que tu sais comment ça pourrait se comparer en termes de perfs à cette librairie : http://maraksquires.com/JSLINQ/

    qui simule du SQL en JS, et qui possède entre autre une fonction .intersect()

  2. piouPiouM dit :

    J’ai ajouté JSLINQ au benchmark. Verdict : c’est plus lent dans la majorité des cas (il arrive que ce soit plus rapide sur 100 éléments numériques sous Safari 4.0.5).

    Comme tu peux le lire dans la suite de tests réalisée, on est obligé d’appliquer un JSLINQ#Distinct() après la recherche d’intersection pour supprimer les entrées dupliquées (et accessoirement un appel à JSLINQ#ToArray(), mais j’applique cela dans un callback non comptabilisé par le timer).

  3. jpvincent dit :

    merci pour ce bench, il montre si cela manquait qu’un code spécifique est toujours meilleur qu’une librairie générique, et lorsque l’on cherche les performances, il faut s’intéresser au spécifique

  4. FGRibreau dit :

    Vraiment pressé de tester ce code sous Node… vraiment :’)

  5. vincent voyer dit :

    Belle performance, deux questions :

    • pourquoi ne pas proposer ce code dans les librairies javascript du marché ? As tu déjà essayé ?
    • FGRibreau, pour quels cas/usages tu aurais besoin de array intersect dans node js ? (curieux:))
  6. piouPiouM dit :

    Je n’ai pas essayé de la proposer à des librairies JavaScript. Affaire à suivre (on verra si l’équipe de jQuery est encore fermée, cf mon patch pour jQuery Color proposé il y a 7 mois qui n’a toujours pas eu de réponse).

Ajouter un commentaire


Syndication

Réseaux sociaux