Comment est-set (), mis en œuvre?

Question

J'ai vu des gens dire qu' set objets en python ont O(1) l'adhésion à la vérification. Comment sont-ils mis en œuvre en interne pour permettre cela? Quel type de structure de données faut-il utiliser? Quelles sont les autres conséquences que la mise en œuvre?

Chaque réponse a été très enrichissant, mais je ne peux accepter qu'un seul, donc je vais aller avec le plus proche de la réponse à ma question d'origine. Merci à tous pour les infos!

Answer 1

Selon ce thread:

En effet, Disponible de jeux sont mis en œuvre en tant que quelque chose comme des dictionnaires avec des valeurs fictives (les clés étant les membres de l'ensemble), avec quelques optimisation(s), qui profitent de cette absence de valeurs

Donc, fondamentalement, une set utilise une table de hachage comme c'est sous-jacente de la structure de données. C'est ce qui explique le O(1) l'adhésion de la vérification, depuis la recherche d'un élément dans une table de hachage est un O(1) le fonctionnement, en moyenne.

Si vous êtes si incliné, vous pouvez même parcourir le Disponible le code source pour définir ce qui, selon Achim Domma, est surtout un copier-coller à partir de la dict mise en œuvre.

Answer 2

Quand les gens disent des ensembles de O(1) l'adhésion à la vérification, ils parlent de la moyenne des cas. Dans le pire des cas (lorsque toutes les valeurs de hachage collision) la qualité de membre de vérification est O(n). Voir le Python wiki sur le temps de la complexité.

L' article de Wikipedia dit le meilleur des cas, le temps de la complexité pour une table de hachage qui ne permet pas de redimensionner est - O(1 + k/n). Ce résultat ne s'applique pas directement à Python ensembles depuis Python jeux de l'utilisation d'une table de hachage qui se redimensionne.

Un peu plus loin l'article de Wikipédia dit que pour la moyenne des cas, et en supposant qu'un simple uniforme de la fonction de hachage, la complexité du temps est - O(1/(1-k/n))où k/n peut être bornée par une constante c<1.

Big-O désigne seulement le comportement asymptotique que n → ∞. Depuis k/n peut être bornée par une constante c<1, indépendant de n,

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

Donc en supposant uniforme simple hachage, sur la moyenne, l'adhésion de vérification pour Python ensembles O(1).

Answer 3

Je pense que c'est une erreur commune, set de recherche (ou de la table de hachage (hashtable) ne sont pas O(1).
de la Wikipedia

Dans le modèle le plus simple, la fonction de hachage est complètement indéterminé et le tableau n'est pas redimensionnée. Pour le choix de la fonction de hachage, un tableau de taille n avec abordant a pas de collisions et tient jusqu'à n éléments, avec une simple comparaison pour la réussite de la recherche, et un tableau de taille n avec chaînage et k touches a le minimum de max(0, k-n), les collisions et les O(1 + k/n) comparaisons pour la recherche. Pour le pire choix de la fonction de hachage, chaque insertion provoque une collision, et les tables de hachage de dégénérer à la recherche linéaire, avec Ω(k) amorti des comparaisons par insertion et jusqu'à k comparaisons de succès de la recherche.

Relative: Java Est hashmap vraiment O(1)?

Answer 4

Nous avons tous un accès facile à la source, d'où le commentaire précédant set_lookkey() dit:

/*
The basic lookup function used by all operations.
This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
Open addressing is preferred over chaining since the link overhead for
chaining would be substantial (100% with typical malloc overhead).

The initial probe index is computed as hash mod the table size. Subsequent
probe indices are computed as explained in Objects/dictobject.c.

All arithmetic on hash should ignore overflow.

Unlike the dictionary implementation, the lookkey functions can return
NULL if the rich comparison returns an error.
*/
static setentry *
set_lookkey(PySetObject *so, PyObject *key, register long hash)
{
...