JavaScript : optimiser le calcul de l’intersection de tableaux de grandes tailles

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 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.