Pense-bête ruby : compter les occurences des éléments d'un tableau

Cela fait un certain nombre de fois que je me retrouve en situation de devoir compter les occurrences d'éléments dans un tableau, et à chaque fois c'est la même galère pour retrouver les bonnes pages sur StackOverflow ou ailleurs. Alors je me fend d'un billet sur le sujet, comme ça la prochaine fois je saurai où chercher et peut-être qu'à force la logique finira par rentrer…

Obtenir un hash avec les éléments d'un tableau et leurs occurences

Prenons ce tableau de chaines ruby comme base de départ.

words = %w(how much wood would a wood chuck chuck)

Avec inject

inject est une fonction permettant de parcourir un “Enumerable” à l'aide d'une valeur de départ et un opérateur binaire. Sous cette forme on utilsera d'ailleurs plutôt son alias reduce.

(5..10).reduce(:+)
#=> 45

La valeur de départ est injectée dans un “accumulateur” que l'on amende ou modifie avec l'élélement d'itération en cours dans un bloc qu'on lui fournit. L'accumulateur précède l'élément dans la définition des variables du bloc. La fonction renvoie la valeur de l'accumulateur à la fin des itérations, c'est pourquoi il faut également le renvoyer à la fin du bloc.

words.inject(Hash.new(0)) { |a, e| a[e] += 1 ; a } 
#=> {"how"=>1, "much"=>1, "wood"=>2, "could"=>1, "a"=>1, "chuck"=>2}

Avec each_with_object

each_with_object à le même fonctionnement que l'exemple précédent lorsqu'on lui donne un bloc, mais l'ordre des variables de bloc est inversé. Il est d'ailleurs recommandé en lieu et place de la forme inject utilisée ci-dessus (merci Rubocop)

words.each_with_object(Hash.new(0)) { |e, a| a[e] += 1 }
#=> {"how"=>1, "much"=>1, "wood"=>2, "could"=>1, "a"=>1, "chuck"=>2}

Pour information on peut appeler each_with_object sans bloc et juste récupérer l'énumérateur.

Avec un constructeur de Hash

Hash[words.group_by{ |e| e }.map{ |k,v| [k,v.length] }]
#=> {"how"=>1, "much"=>1, "wood"=>2, "would"=>1, "a"=>1, "chuck"=>2}

Un syntaxe un peu moins accessible mais en découpant individuellement les éléments on “déchiffre” que :

  • Hash[] est un constructeur qui fait un hash avec un array d’array
  • group_by qui fait un hash avec comme clé “e” et comme valeur le tableau des éléments qui match la valeur comparée ici “e”

Performances

Vu qu'il y a moulte manière de faire, quid des performances de ces trois méthodes ? Voici un petit script de benchmark avec les résultats :

#!/usr/bin/env ruby

require 'Benchmark'

iterations  = 10_000
a_few_words = %w(how much wood would a chuck)
many_words  = []
500.times { many_words << a_few_words.sample }

def inject_method(words)
  words.inject(Hash.new(0)) { |a, e| a[e] += 1 ; a }
end

def each_wo_method(words)
  words.each_with_object(Hash.new(0)) { |e, a| a[e] += 1 }
end

def hash_method(words)
  Hash[words.group_by{ |e| e }.map{ |k,v| [k,v.length] }]
end

Benchmark.bmbm(7) do |x|
  x.report("small array inject:  ") { iterations.times { inject_method  a_few_words } }
  x.report("small array each_wo: ") { iterations.times { each_wo_method a_few_words } }
  x.report("small array Hash:    ") { iterations.times { hash_method    a_few_words } }
  x.report("big array inject:    ") { iterations.times { inject_method  many_words  } }
  x.report("big array each_wo:   ") { iterations.times { each_wo_method many_words  } }
  x.report("big array Hash:      ") { iterations.times { hash_method    many_words  } }
end
$ ./benchmark.rb
Rehearsal ---------------------------------------------------------
small array inject:     0.030000   0.000000   0.030000 (  0.029513)
small array each_wo:    0.030000   0.000000   0.030000 (  0.027106)
small array Hash:       0.050000   0.000000   0.050000 (  0.049614)
big array inject:       1.070000   0.000000   1.070000 (  1.076534)
big array each_wo:      1.030000   0.000000   1.030000 (  1.033481)
big array Hash:         0.810000   0.000000   0.810000 (  0.810381)
------------------------------------------------ total: 3.020000sec

                            user     system      total        real
small array inject:     0.030000   0.000000   0.030000 (  0.024837)
small array each_wo:    0.030000   0.000000   0.030000 (  0.026654)
small array Hash:       0.050000   0.000000   0.050000 (  0.050111)
big array inject:       1.040000   0.000000   1.040000 (  1.046067)
big array each_wo:      1.040000   0.000000   1.040000 (  1.047735)
big array Hash:         0.790000   0.010000   0.800000 (  0.790335)

Il apparaît donc que l'usage de inject soit préconisé pour les tableaux de petite taille alors que le contructeur de Hash soit plus rentable pour le tableau plus importants.

Corrections

  • 10/08/2016 : merci à Sylvain/@rivsc57 pour ses remarques sur twitter, j'ai donc amendé le billet original.
  • 10/08/2016 : merci à Nicolas pour ses remarques sur également sur twitter, j'ai donc remplacé Benchmark.bm par bmbm pour inhiber l’intervention du garbage collector, ainsi que séparé en 2 tests sur des tableaux de tailles différentes comme Sylvain le faisait remarquer.