Re: Comparaisons d'un ensemble de valeurs

Posté par DaWaaaaghBabal le 11/10/2019 18:11:57

Voui. Un set, ça fait de la sorcellerie. En termes non-techniques:
- Pour ajouter un élément à une liste, on le pose à côté des éléments déjà présents, sans trou. L'implémentation varie, mais dans tous les cas on a une structure compacte ou les éléments sont rangés dans l'ordre d'insertion, mais aucune information sur ce qu'on peut s'attendre à trouver à un emplacement donné, ni sur l'emplacement où on peut s'attendre à trouver un élément donné. Donc, chercher dedans consiste à énumérer tous les éléments : "C'est celui-ci ? Ah, non. C'est le suivant ? Ah, non. C'est le suivant ? Ah, non." Donc, plus la liste est longue, plus le temps moyen pour trouver un élément dedans est long.

- Pour ajouter un élément à un set, on commence par calculer où il devrait être. Et on le met là, peu importe si on fait des trous dans la structure. En conséquence, chercher un élément dans la liste devient très simple : est-ce qu'il est à l'endroit où je m'attendrais à le trouver ?
Ce calcul ne dépend pas de la taille de l'ensemble. Il est beaucoup plus lourd, en général, que la comparaison "est-ce que c'est celui-ci ?", mais on ne le fait qu'une fois, quelle que soit la taille de l'ensemble (aux cas pathologiques près).

Un set prend donc plus de place, puisqu'on accepte de faire des trous, mais gagne énormément en temps de calcul.