Quelqu'un a tort ! Test d'appartenance dans les cas concrets§

Évidemment, quand quelqu'un a tort sur Internet, faut bien faire quelque chose. Dans ce cas précis, un quidam sur StackOverflow a mentionné qu'utiliser des maps pour le test d'appartenance était plus lent que de simplement itérer sur un tableau, pour n suffisamment petit.

Son argument était que le coût du hachage de la valeur était plus élevé que celui d'une recherche dans un tableau, pour la plupart des tailles réalistes. Selon ses termes, taille réaliste voulait dire jusqu'à plus d'un million de valeurs.

Vous vous demandez peut-être pourquoi je ne mets pas directement de lien vers le commentaire en question. La raison est que je ne le retrouve plus. Je me souviens seulement que le commentaire m'a assez agacé pour me faire crier « Quelqu'un a tort sur Internet ! » (xkcd 386, « Duty Calls »).

Mais j'avais des doutes ; son argument aurait pu avoir du sens. Je veux dire, peut-être que le coût du hachage est supérieur à celui d'itérer et de comparer pour n inférieur à quelque\ chose. Mon instinct me disait que c'était des conneries, mais je ne suis pas assez prétentieux pour affirmer que c'était des conneries avant d'avoir réellement vérifié que c'était des conneries.

Au fond, retrouver le commentaire (et dire au coupable qu'il a tort !) n'a pas d'importance. Ce qui compte, c'est La Vérité. Dans ce billet, nous explorons la vérité à l'aide du langage de programmation Go, le meilleur langage qui soit (sans exagération aucune).

TL;DR§

Évidemment, ce quidam avait tort. Vérifié pour n>1, le test d'appartenance sur une map est toujours plus rapide que sur une slice. Cela veut dire que, dans tous les cas, vous ne devriez pas utiliser une slice à la place d'une map.

<insert fancy graph here>

mise à jour : les tests qui suivent supposent des ensembles de type string. Les mêmes tests avec des types int révèlent que les slices sont légèrement plus rapides jusqu'à n \approx 30.

Problème§

Le test d'appartenance consiste à demander à une structure de données si elle contient une valeur ou non. Parmi les nombreuses façons de l'implémenter, deux sont abordées ici :

Map§

Utiliser une map[value]bool, puis vérifier si une valeur est dans la map :

func isMapMember(m map[string]bool, key string) bool {
  _, ok := m[key]
  return ok
}

Slice§

Utiliser une []value, puis itérer sur toutes les valeurs pour vérifier si l'une d'elles est dans la slice :

func isSliceMember(s []string, key string) bool {
  for _, entry := range s {
    if key == entry {
      return true
    }
  }
  return false
}

Question§

Laquelle des deux est la plus rapide ?

Hypothèse§

Mon hypothèse est qu'utiliser une slice sera plus rapide. J'aime essayer de prouver que j'ai tort.

Prédiction§

Si mon hypothèse est effectivement juste, il y aura un n pour lequel utiliser une slice sera plus rapide qu'utiliser une map. Cela voudra dire que le quidam avait raison. Dans de nombreux cas d'utilisation, le test d'appartenance se fera sur des ensembles qui contiennent quelques valeurs.

Expérimentation§

Je vois 3 4 dimensions qui pourraient influer sur les résultats.

1. n, la taille de l'ensemble testé. La thèse ici est que pour n suffisamment petit, une slice sera plus rapide.
2. valSize, la taille des valeurs individuelles stockées dans l'ensemble. À mesure que valSize augmente, il est possible que les structures se comportent différemment qu'avec une valSize plus petite.
3. Que l'élément soit ou non dans l'ensemble. Il se pourrait que les maps soient plus rapides pour déterminer la non-appartenance. Ou les slices. Qui sait !
4. mise à jour : le type des valeurs contenues dans l'ensemble.

Méthodologie§

En tenant compte des dimensions ci-dessus, nous allons benchmarker les deux méthodes de test d'appartenance.

• Pour un ensemble de n éléments uniques, prendre au hasard un élément qui est dans l'ensemble. Mesurer combien de temps il faut pour vérifier que cet élément appartient à l'ensemble.
• Pour un ensemble de n éléments uniques, prendre au hasard un élément qui n'est pas dans l'ensemble. Mesurer combien de temps il faut pour vérifier que cet élément n'appartient pas à l'ensemble.

La première étape est de créer un ensemble de n éléments uniques, chacun étant une chaîne générée aléatoirement de longueur valSize. Le vrai code de benchmark les sépare en deux fonctions, afin d'exécuter un seul type de benchmark à la fois.

func makeRandomSet(n, valSize int) (map[string]bool, []string) {
  mapset := make(map[string]bool, n)
  sliceset := make([]string, 0, n)

  for len(mapset) != n {
    str := makeRandomString(valSize)
    if _, ok := mapset[str]; !ok {
      mapset[str] = true
      sliceset = append(sliceset, str)
    }
  }
  return mapset, sliceset
}

Ensuite, nous avons deux voies : vérifier l'appartenance, vérifier la non-appartenance.

Appartenance§

Prendre un échantillon de l'ensemble :

func sampleInSlice(sliceset []string) {
  randIdx := rand.Intn(len(sliceset))
  return sliceset[randIdx]
}

L'échantillonnage dans la map se fait de la même façon, mais vous devez d'abord extraire les clés de la map dans une slice. Pour les besoins du benchmark, cette fonction renvoie en fait une slice d'échantillons uniques, puis nous mesurons combien de temps il faut pour vérifier l'appartenance de chacun.

Nous utiliserons cette fonction utilitaire pour benchmarker les maps :

func benchMapMembers(b *testing.B, size int, keySize int) {
  m := makeRandomMap(size, keySize)
  samples := sampleFromMap(m, b.N)

  var member string
  var ok bool
  b.ResetTimer()
  for i := 0; i < b.N; i++ {
    member = samples[i]
    ok = isMapMember(m, member)
  }
  _ = ok
}

Et celle-ci pour benchmarker les slices :

func benchSliceMembers(b *testing.B, size int, keySize int) {
  s := makeRandomSlice(size, keySize)
  samples := sampleFromSlice(s, b.N)

  var member string
  var ok bool
  b.ResetTimer()
  for i := 0; i < b.N; i++ {
    member = samples[i]
    ok = isSliceMember(s, member)
  }
  _ = ok
}

Non-appartenance§

Trouver des éléments qui ne sont pas dans l'ensemble :

func sampleNotInMap(mapset map[string]bool, valSize int) (sample string) {
  for {
    str := makeRandomString(valSize)
    if !mapset[str] {
      return str
    }
  }
}

L'échantillonnage dans la slice se fait de la même façon. Ensuite, nous créons aussi des fonctions utilitaires de benchmark assez semblables aux fonctions utilitaires d'appartenance.

Pour les maps :

func benchMapNotMembers(b *testing.B, size int, keySize int) {
  m := makeRandomMap(size, keySize)
  samples := sampleNotInMap(m, b.N, keySize)

  var member string
  var ok bool
  b.ResetTimer()
  for i := 0; i < b.N; i++ {
    member = samples[i]
    ok = isMapMember(m, member)
  }
  _ = ok
}

Pour les slices :

func benchSliceMembers(b *testing.B, size int, keySize int) {
  s := makeRandomSlice(size, keySize)
  samples := sampleFromSlice(s, b.N)

  var member string
  var ok bool
  b.ResetTimer()
  for i := 0; i < b.N; i++ {
    member = samples[i]
    ok = isSliceMember(s, member)
  }
  _ = ok
}

Duel !§

Nous exécutons les fonctions utilitaires d'appartenance au moyen d'une série de benchmarks, avec n dans (2,3,4,5,6,7,8,9,10, 100, 1000, 10000, 100000, 1000000) et valSize dans (10, 100).

func BenchmarkMap_2key_10bytes(b *testing.B)        { benchMapMembers(b, 2, 10) }
func BenchmarkMap_3key_10bytes(b *testing.B)        { benchMapMembers(b, 3, 10) }
...
func BenchmarkMap_1000000key_100bytes(b *testing.B) { benchMapMembers(b, 1000000, 100) }

func BenchmarkSlice_2key_10bytes(b *testing.B)        { benchSliceMembers(b, 2, 10) }
func BenchmarkSlice_3key_10bytes(b *testing.B)        { benchSliceMembers(b, 3, 10) }
...
func BenchmarkSlice_1000000key_100bytes(b *testing.B) { benchSliceMembers(b, 1000000, 100) }

Tester la non-appartenance est beaucoup plus coûteux que tester l'appartenance, puisqu'il faut créer des chaînes aléatoires qui ne sont pas dans l'ensemble d'origine. C'est très long à mettre en place, donc j'ai limité cette partie du test à quelques valeurs, et je suppose que le comportement de la non-appartenance sera cohérent avec celui de l'appartenance. C'est une supposition acceptable, étant donné que l'expérience que j'ai effectivement mesurée suggère que c'est bien le cas.

De plus, Go tue les benchmarks qui tournent plus de 600 s (10 min). L'exécution des combinaisons ci-dessus dure à peine moins de 600 s (584 s).

func BenchmarkMapNot_10key_10bytes(b *testing.B)      { benchMapNotMembers(b, 10, 10) }
func BenchmarkMapNot_1000key_10bytes(b *testing.B)    { benchMapNotMembers(b, 1000, 10) }
func BenchmarkMapNot_1000000key_10bytes(b *testing.B) { benchMapNotMembers(b, 1000000, 10) }

func BenchmarkSliceNot_10key_10bytes(b *testing.B)      { benchSliceNotMembers(b, 10, 10) }
func BenchmarkSliceNot_10000key_10bytes(b *testing.B)   { benchSliceNotMembers(b, 10000, 10) }
func BenchmarkSliceNot_1000000key_10bytes(b *testing.B) { benchSliceNotMembers(b, 1000000, 10) }

Résultats§

Le code pour exécuter les benchmarks vous-même est sur github. Suivent les résultats de l'exécution de ce benchmark sur mon Mac.

Résultats d'appartenance§

Résultats de non-appartenance§

Les résultats sont clairs, mon hypothèse était fausse. Pour n > 1, le test d'appartenance est toujours plus rapide avec une map.

Donc clairement, quelqu'un avait tort sur Internet !!!!§

Mise à jour§

Ce qui précède a été écrit en considérant string comme le type contenu dans l'ensemble. Il s'avère que pour des ensembles d'int, les slices sont légèrement plus rapides que les maps jusqu'à n \approx 30.

Appartenance d'entiers§

Non-appartenance d'entiers§

Quelqu'un n'avait pas si clairement tort sur Internet !!!!§