Pourquoi y a-t-il 2 complexités possibles pour la même opération ? Ne serait-il pas plus correct de calculer la complexité en utilisant en priorité le pire cas possible (O(n)) ?
Je crois avoir lu quelque part que la complexité pouvait monter à O(n) quand il y avait des "hash collisions" ou des "collision resolutions" mais je n'ai pas réussi à trouver beaucoup + d'information sur ce sujet.
Autre question : qu'est-ce qu'un bucket exactement ? La documentation explique que c'est quelque chose qui contient un ou plusieurs éléments de l'unordered_set en fonction du hash de l'élément. Cela veut donc dire que chaque élément d'un unordered_set est contenu dans un bucket mais on n'en sait pas beaucoup +.
Connaissez-vous des sources pour en apprendre + sur le sujet ?
En fait, il faut déjà arriver à comprendre ce que représente la complexité d'une fonction: elle représente le rapport qui existe entre l'obtention du résultat en fonction du nombre d'éléments qu'il faut manipuler.
Autrement dit, mettons qu'il nous faille un temps T pour obtenir un résultat. Ce temps T pourrait être le temps nécessaire pour effectuer une multiplication et une comparaison ou celui qui est nécessaire pour effectuer cinquante opérations différentes avant d'obtenir le résultat souhaité, cela n'a pas d'importance: avec un seul élément, il faudra le temps T pour obtenir le résultat.
La complexité essaye de déterminer combien de fois il faudra attendre le temps T s'il n'y avait plus un seul élément à manipuler mais 10, 100 ou ... 150 000? Pour nous donner une idée de l'évolution de ce temps, on va présenter la complexité sous la forme d'une fonction O(une_valeur_coherente).
Ainsi, si l'on souhaite représenter le fait que le temps nécessaire à l'obtention du résultat ne change pas malgré l'augmentation du nombre d'éléments -- autrement dit, si on veut représenter une opération se faisant en temps constant -- on représentera cette complexité sous la forme O(1), et, si on souhaite représenter le fait que le temps nécessaire à l'obtention du résultat évolue en fonction du nombre d'éléments à traiter, on représentera la complexité sous la forme O(n) pour signifier le fait que, plus le nombre d'élément augemente (plus n augmente), plus le temps nécessaire à l'obtention du résultat augmente.
Après, il y a quelques valeurs intéressantes comme O(log(n)), O(n log(n)), O(n²) ou O(n!).
Le problème, c'est que certains comportements peuvent voir leur complexité changer en fonction de la situation de départ.
Par exemple, si je veux remplir un arbre binaire équilibré, et que j'introduit les valeur de 1 à 15 dans l'ordre 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15, cela irait certainement plus vite que si je décidais d'introduire les mêmes chiffres dans l'ordre 1, 2, 3, 4, 5, 6, 7, 8 9, 10, 11, 12, 13, 14, 15. La raison de ce fait -- tout à fait vérifiable -- est que le premier ordre donné (8, 4, 12,...)nous permet d'obtenir un arbre binaire qui est directement équilibré, ce qui nous place dans la meilleure situation possible pour le remplissage avec une complexité en O(log(n)). Par contre, le deuxième ordre (1, 2, 3, 4, ...) nécessite non seulement d'insérer les éléments avec une complexité en O(log(n)), mais aussi de rééquilibrer l'arbre binaire après chaque insertion, ce qui ajoute une complexité en O(n log(n)) au comportement.
On se rend donc "assez facilement" compte que, dans une "situation idéale", dans "le meilleur des cas", nous avons un comportement dont la complexité est en O(log(n)), et que, dans "le pire des cas", le même comportement s'effectuera avec une complexite en O(log(n) + n log(n)); avec une "réalité effective" due à notre jeu de données qui se trouvera sans doute ... entre les deux, car rien ne nous laisse supposer que tous les ajouts nécessiteront forcément le rééquilibrage de l'arbre. Mais rien ne nous laisse supposer non plus qu'aucun ajout ne nécessitera un tel rééquilibrage.
Il est donc "assez fréquent" de donner le pire et le meilleur des cas lorsqu'on indique la complexité d'un comportement, voire, de donner le "cas moyen", qui aura été déterminé par expérimentation, de manière à rester "le plus impartial possible" dans l'évaluation de la complexité. Et c'est ce que tu viens de constater avec l'insertion dans un unordered_set:
Quand "tout se passe bien", et ce sera régulièrement le cas, l'insertion peut s'effectuer en temps constant, avec une complexité en O(1). Et pourtant, on ne peut ignorer le fait qu'il y aura des situations, des "pires des cas", dans lesquelles l'insertion s'effectuera en temps proportionnelle, avec une complexité en O(n).
Cependant, on peut se rassurer et considérer que ce "pire des cas" est sans doute plus théorique qu'autre chose parce que l'expérimentation tend à démontrer que l'on reste beaucoup plus proche, sur la moyenne des insertions, du temps constant, de la complexité en O(1), que du temps proportionnel, de la complexité en O(n).
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Le cas moyen, ça ne se détermine pas par expérimentation, mais par des considérations mathématiques. La moyenne de tous les cas.
Parce que c'est pas tout de connaître ce qui se passe dans les bons cas, et ce qui peut arriver dans les pires, il faut voir si les mauvais cas risquent de se produire souvent ou pas.
Lee fonctionnement d'un unordered_set (rangement par hachage) :
Admettons je veux stocker une centaine de chaînes de caractères, et pouvoir déterminer rapidement si une chaîne particulière y est ou pas.
Première idée : hachage
1. Pour stocker ces chaînes je vais utiliser un tableau de 256 chaînes
2. Je vais me donner une fonction qui, à partir d'une chaîne, retourne un entier de 0 à 255 (par exemple, la somme des caractères modulo 256)
3. Ce nombre me dit où je suis censé avoir rangé la chaîne dans le tableau. Si pour "abracadabra" la fonction de hachage renvoie 33, ben je regarde directement dans la case 33, pour voir si il est là.
Problème, ça marche pas bien. Parce que la fonction de hachage peut retourner la même valeur pour 2 chaînes différentes. Avec mon exemple de fonction de hachage, melanger les caractères de la chaîne, ça fait ça. C'est ce qu'on appelle une collision. Deux chaînes différentes qui se retrouveraient au même endroit.
Amélioration de l'idée : "buckets"
Le tableau va contenir, par 256 chaînes, mais 256 *listes* de chaînes. Les liste on appelle appelle ça des "buckets" (des seaux). Pour chercher, le hachage nous donne un numéro de bucket, et on regarde dedans.
statistiquement, en moyenne, il y a 100/256 (un demi, quoi) éléments par bucket donc la recherche est pas très longue.
Mais dans le pire des cas, toutes les chaînes avaient la même valeur de hachage, et il faut chercher dans une liste de taille 100. Heureusement, ce cas est très improbable, avec des chaînes tirées au hasard.
[ maintenant, les chaînes qu'on manipule réellement dans les programmes, sont elles réellement aléatoires ? C'est encore une autre histoire. Par exemple des noms de famille en France, y en a bien la moitié qui commencent par les 6 premières lettres A-F. Et c'est là qu'il faudrait "instrumenter" des utilisations réelles]
Il y a d'autres considérations pour réaliser un unordered_set (l'extension du tableau quand on ajoute, taux de remplissage, hachage modulo la taille du tableau), j'ai simplifié....
@koala01 du coup ce que tu dis c'est que c'est l'expérimentation qui permet de conclure que la complexité est dans le meilleur des cas O(1) et dans le pire des cas O(n) ? Je ne comprends pas vraiment en quoi cela explique la complexité O(1) et O(n) de unordered_set. Ok on observe que la complexité est O(1) ou O(n) mais quel est le raisonnement derrière ?
@michelbillaud
"C'est ce qu'on appelle une collision. Deux chaînes différentes qui se retrouveraient au même endroit."
Mais comment 2 chaînes différentes peuvent se retrouver au même emplacement mémoire ? Il ne peut y avoir qu'une seule information en mémoire.
"Mais dans le pire des cas, toutes les chaînes avaient la même valeur de hachage" comment cela est possible si les chaînes sont différentes ?
"Mais dans le pire des cas, toutes les chaînes avaient la même valeur de hachage" comment cela est possible si les chaînes sont différentes ?
En fait si le nombre total de données qui peuvent être passées à la fonction de hachage sont supérieures au nombre total de chaines données en sortie par la fonction de hachage il y a forcement au moins deux ensembles de données qui produiront une même chaine de hachage/signature.
Par exemple (pour schématiser) , si une fonction de hachage donne en sortie une chaine de 4 lettre minuscules cela fait "26 puissance 4" chaines possibles et si les données traitables par la fonction de hachage sont supérieures à "26 puissance 4" , il y aura bien une collision (=deux chaines de hachage identiques) par définition.
Ok je crois que je vois. C'est ce que je supposais quand j'ai vu dans la doc que la complexité était soit O(1) soit O(n).
L'unordered_set contient des buckets qui sont des "conteneurs" que l'on peut accéder par un hash. En principe, l'unordered_set est conçu pour placer chaque élément dans un bucket distinct pour avoir une complexité de O(1) mais dans de très rares cas il y a une collision de hashes ce qui aboutit à placer plusieurs éléments dans un même bucket. Et comme un bucket fonctionne comme une liste j'imagine, on tombe sur une complexité de O(n).
Mais je trouve qu'il faut quand même faire beaucoup de suppositions pour arriver à cette réponse-là. J'ai été un peu interloqué par le manque de précisions de la doc officielle.
>> C'est ce qu'on appelle une collision. Deux chaînes différentes qui se retrouveraient au même endroit." >Mais comment 2 chaînes différentes peuvent se retrouver au même emplacement mémoire ? Il ne peut y avoir qu'une seule information en mémoire.
C'est bien par que la fonction de hachage les enverrait au même endroit qu'il y a un problème, puisqu'on ne peut en mettre qu'une. Et donc qu'on utilise un tableau de buckets, conteneurs qui peuvent en contenir plusieurs.
> imprécision de la doc officielle
C'est à dire que ce genre de structure de données, c'est un grand classique qui fait partie de l'enseignement informatique "sérieux" traditionnel. On peut comprendre que le rédacteur de la doc n'avait pas envie de refaire le cours d'informatique de 2ieme année, et suppose que si le lecteur s'intéresse à la complexité, c'est qu'il a des connaissances de base qui incluent ce genre de truc.
> rareté des collisions
Statistiquement y en a pas énormément, parce qu'on s'arrange pour que la taille du tableau (de buckets) soit assez grande par rapport au nombre de trucs à mettre dedans. Par exemple en java, le taux de remplissage maximum est gardé en dessous de 75 %. Mais pas *très* rares. Ce qui est très rare c'est le pire des cas, que tout aille dans le même bucket.
On prend les 12 noms de mois (codées en UTF8), et on regarde comment ça se passe si on essaie de les ranger dans un tableau de 16 buckets.
Pour ça il nous faut d'abord une fonction de hachage sur les chaînes de caractères. On prend ça,
unsigned int hachage(const std::string &chaine) {
unsigned int h = 0;
for (unsigned char c: chaine) {
h = 31 * h + c;
}
return h;
}
(j'invente rien, c'est la même que le runtime java)
Si on l'applique à "mai", ça nous donne 107861 (y a que 3 lettres vous pouvez vérifier). "septembre", ça fait 2265118295.
Après, pour trouver le numéro de bucket on prend le reste de la division du "hashcode" par 16 (si il y a 16 buckets).
La fonction suivante fait afficher pour chaque chaine son hashcode et le numéro de bucket
void test(const std::string & titre,
const std::vector<std::string> chaines,
int nb_buckets)
{
std:: cout << "# essai avec " << titre
<< " (" << nb_buckets << " buckets)" << std::endl;
std::cout << std::setw(12) << "hashcode"
<< std::setw(6) << "num"
<< " chaine"
<< std::endl;
for (const auto &chaine : chaines) {
unsigned int h = hachage(chaine);
std::cout
<< std::setw(12) << h
<< std::setw(6) << (h % nb_buckets)
<< " "
<< chaine
<< std::endl;
}
std::cout << std::endl;
}
Attention, Mesdames et Messieurs, sous vos yeux ébahis le spectacle exceptionnel de l'affichage du résultat. Ouvrez bien les mirettes, qu'est ce qu'on remarque ?
g++ -std=c++20 -Wall -Wextra -pedantic -Werror -Wno-unused -g prog.cc -o prog
./prog
# essai avec noms de mois (16 buckets)
hashcode num chaine
2468344119 7 janvier
3593356014 14 février
3344085 5 mars
93209792 0 avril
107861 5 mai
3273648 0 juin
3036014509 13 juillet
93081646 14 août
2265118295 7 septembre
2673479782 6 octobre
1639129784 8 novembre
2783952404 4 décembre
=> Il y a des collisions pour les buckets 0 ("avril" et "juin"), 5, 7 et 14. C'est pas de bol.
Essayons avec 32
test("noms de mois", noms_mois, 32);
Ça donne
# essai avec noms de mois (32 buckets)
hashcode num chaine
2468344119 23 janvier
3593356014 14 février
3344085 21 mars
93209792 0 avril
107861 21 mai
3273648 16 juin
3036014509 13 juillet
93081646 14 août
2265118295 23 septembre
2673479782 6 octobre
1639129784 24 novembre
2783952404 20 décembre
Saleté, y en a encore (14, 21 et 23) !
Mais est-ce grave ?
Si on regarde ce que nous coûte une recherche d'une chaîne, prise parmi les 12 noms de mois
Y a 6 buckets avec seul élément, et 3 avec deux. Il y a donc une probabilité de (6+3)/12 (il faudra faire une comparaison) de tomber sur le premier de la liste, et de 3/12 (pour qui il en faudra 2).
Donc pour trouver un nom de mois il faut en moyenne 1 x 9/12 + 2 x 3/12 = 15/12 = 5/4 = 1,25 comparaison. C'est plus que 1, mais pas beaucoup.
Maintenant avec une chaîne aléatoire qui n'est pas un nom de mois. Ça tombe aléatoirement sur un des 32 buckets.
Y en a 23 qui sont vides (0 comparaisons), 6 avec 1 élément et 3 avec 2. Donc en moyenne il faut
pour vérifier qu'une chaîne n'est pas un nom de mois.
On peut comparer avec ce que ça donnerait si les noms de mois étaient dans un arbre binaire de recherche (ordered_set)
Avec 12, au mieux si l'arbre est équilibré, il y un sommet à la racine, 2 à hauteur 1, 4 à hauteur 5 et 5 à hauteur 3... Ça fait 5 chances sur 8 de faire 4 comparaisons et 3 d'en faire 3 => 4,6 comparaisons !
PS: précision, quand je dis qu'un bucket c'est une liste de machins, c'est pasforcement une liste chainée. D'un point de vue mathématique, j'aurais dû dire que c'est un ensemble (fini évidemment) de machins : il n'y a pas de doublons, l'ordre n'est pas important, et les opérations qu'on a besoin d'y faire c'est ajouter/chercher/supprimer. On peut implémenter le bucket par une liste chaînée, un tableau extensible etc. Dans la mesure où la taille moyenne des buckets est < à 1, la liste chaînée simple est raisonnable, le surcoût par élément est juste d'un pointeur (vers le suivant) + overhead d'allocation.
J'ai vu que vous faites le lien entre complexité temporelle et temps d'exécution.
Je souhaiterais ajouter que le grand O nous donne une information essentielle concernant l'algo : il nous indique qu'on s'intéresse à l'évolution d'un temps en fonction de la taille de l'entrée, **à partir d'un certain rang**, et la culture nous montre qu'on s'y intéresse plus particulièrement pour des grandes valeurs de n.
Il faut garder en tête le fait que le grand O nous donne une information **asymptotique** et fondamentalement approximative puisqu'il permet de comparer des quantités à une constante près (en ordre de grandeur, autrement dit).
De plus, le grand O permet d'étudier l'algorithme, et il ne prend pas en compte les spécificités du langage, de l'environnement d'exécution, etc. C'est un outil théorique.
Tout ça pour dire qu'il n'est pas judicieux de s'y attacher pour voir les résultats concrets coller avec la théorie. Une fonction en complexité pire cas cubique peut être plus efficace qu'une fonction en complexité pire cas linéaire qui fait la même chose, sur une même entrée... Bref, les histoires de temps d'exécution dépendent de bien plus que d'un simple ordre de grandeur qui n'a de sens qu'asymptotiquement.
Je ne savais pas que pour obtenir l’indice dans le set on utilisait le reste d’un hash de cette manière ! Tu as vu ça où @michelbillaud ?
"C’est à dire que ce genre de structure de données, c'est un grand classique qui fait partie de l'enseignement informatique "sérieux" traditionnel. On peut comprendre que le rédacteur de la doc n'avait pas envie de refaire le cours d'informatique de 2ieme année, et suppose que si le lecteur s'intéresse à la complexité, c'est qu'il a des connaissances de base qui incluent ce genre de truc."
Bah pas de chance pour moi, j’ai fait une école d’informatique mais je n’ai jamais fait de C++ et je n’ai jamais vu ce "grand classique". Je ne saurais même pas mettre un nom sur ce type de structure pour pouvoir en apprendre plus.
J'ai cherché un peu dans The C++ Standard Library de Nicolai M. Josuttis mais je ne suis pas sûr de chercher au bon endroit.
On trouve ça dans tous les bons bouquins parlant de l'implémentation des structures de données. L'utilisation de ce qu'il y a dans la bibliothèque standard, c'est un autre sujet.
Mon site web de jeux SDL2 entre autres : https://www.ant01.fr
https://zestedesavoir.com/tutoriels/822/la-programmation-en-c-moderne/