Comment set() est-il implémenté?

Question

J'ai vu des gens dire que les objets set en python ont une vérification d'appartenance O (1). Comment sont-ils mis en œuvre en interne pour permettre cela? Quel type de structure de données utilise-t-il? Quelles autres implications cette mise en œuvre a-t-elle? Chaque réponse ici était vraiment éclairante, mais je ne peux en accepter qu'une, alors je vais aller avec la réponse la plus proche de ma question initiale. Merci à tous pour l'info!

Answer 1

Selon this thread:

En effet, les jeux de CPython sont mis en œuvre comme quelque chose comme des dictionnaires avec des valeurs factices (les clés étant les membres de l'ensemble), avec une optimisation (s) qui exploitent ce manque de valeurs

Donc, fondamentalement, un set utilise une table de hachage comme structure de données sous-jacente. Ceci explique la vérification de l'appartenance O (1), puisque la recherche d'un élément dans une table de hachage est une opération O (1), en moyenne.

Si vous êtes si incliné, vous pouvez même parcourir le CPython source code for set qui, selon Achim Domma, est la plupart du temps un copier-coller de l'implémentation dict.

Answer 2

Je pense que c'est une erreur commune, set recherche (ou hashtable d'ailleurs) ne sont pas O (1).
from the Wikipedia

Dans le modèle le plus simple, la fonction de hachage est complètement non spécifiée et la table ne sont pas redimensionnés. Pour le meilleur choix possible de fonction de hachage, une table de taille n avec un adressage ouvert n'a pas de collisions et peut contenir jusqu'à n éléments, avec une seule comparaison pour une recherche réussie, et une table de taille n avec chaînage et k (0, kn) collisions et O (1 + k/n) comparaisons pour la recherche. Pour le pire choix de fonction de hachage, chaque insertion provoque une collision, et les tables de hachage dégénèrent en recherche linéaire, avec des comparaisons Ω (k) amorti par insertion et jusqu'à k comparaisons pour une recherche réussie.

connexes: Is a Java hashmap really O(1)?

Answer 3

Nous avons tous un accès facile à the source, où le commentaire précédent set_lookkey() dit:

/* set object implementation 
Written and maintained by Raymond D. Hettinger <python@rcn.com> 
Derived from Lib/sets.py and Objects/dictobject.c. 
The basic lookup function used by all operations. 
This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. 
The initial probe index is computed as hash mod the table size. 
Subsequent probe indices are computed as explained in Objects/dictobject.c. 
To improve cache locality, each probe inspects a series of consecutive 
nearby entries before moving on to probes elsewhere in memory. This leaves 
us with a hybrid of linear probing and open addressing. The linear probing 
reduces the cost of hash collisions because consecutive memory accesses 
tend to be much cheaper than scattered probes. After LINEAR_PROBES steps, 
we then use open addressing with the upper bits from the hash value. This 
helps break-up long chains of collisions. 
All arithmetic on hash should ignore overflow. 
Unlike the dictionary implementation, the lookkey function can return 
NULL if the rich comparison returns an error. 
*/ 


... 
#ifndef LINEAR_PROBES 
#define LINEAR_PROBES 9 
#endif 

/* This must be >= 1 */ 
#define PERTURB_SHIFT 5 

static setentry * 
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) 
{ 
... 

Answer 4

Quand les gens disent ensembles ont O (1) membres vérification, ils sont parle de la en moyenne cas. Dans le cas pire (lorsque toutes les valeurs hachées entrent en collision) la vérification d'appartenance est O (n). Voir le Python wiki on time complexity.

Le Wikipedia article dit le meilleur des cas complexité temporelle pour une table de hachage qui ne redimensionne pas est O(1 + k/n). Ce résultat ne s'applique pas directement aux ensembles Python car les ensembles Python utilisent une table de hachage qui est redimensionnée.

Un peu plus loin l'article de Wikipedia dit que, pour le cas moyen , et en supposant une fonction de hachage uniforme simple, la complexité de temps est O(1/(1-k/n)), où k/n peut être délimitée par une c<1 constante.

Big-O se réfère uniquement au comportement asymptotique comme n → ∞. Puisque k/n peut être délimitée par une constante, c < 1, indépendant de n,

O(1/(1-k/n)) pas est plus grand que O(1/(1-c)) qui est équivalent à O(constant) = O(1).

En supposant un hachage simple et uniforme, sur en moyenne, la vérification d'appartenance pour les ensembles Python est O(1).

Answer 5

Pour souligner un peu plus la différence entre set's et dict's, voici un extrait des sections commentaire setobject.c, qui clarifie la principale différence entre les sets et les dicts.

Les cas d'utilisation des ensembles diffèrent considérablement des dictionnaires où les touches recherchées sont plus susceptibles d'être présentes. En revanche, les ensembles sont principalement sur les tests d'appartenance où la présence d'un élément n'est pas connue dans avance. En conséquence, l'implémentation de l'ensemble doit optimiser à la fois le cas trouvé et le cas non trouvé.

source sur github