S'il vous plaît expliquer l'ordre des ensembles

Question

J'ai trouvé du code qui utilise set s en Python. J'ai essayé de les émuler avec des listes, mais j'obtiens des résultats différents quand pop() d'eux!

J'ai ouvert ipython pour tester comment ces choses fonctionnent, et a trouvé quelque chose assez étrange:

In [16]: x 
Out[16]: set([]) 

In [17]: x.add("a") 

In [18]: x.add("b") 

In [19]: x.add("c") 

In [20]: x 
Out[20]: set(['a', 'c', 'b']) 

Ne devrait pas 'b' venir avant c, car il a été ajouté avant qu'il? Je ne comprends pas ça.

Answer 1

http://docs.python.org/library/stdtypes.html#set

Être une collection non ordonnée, ensembles n'enregistrent position de l'élément ou de l'ordre d'insertion. Par conséquent, les ensembles ne prennent pas en charge l'indexation, le découpage en tranches ou tout autre comportement de type séquence.

La structure de données sous-jacente d'un ensemble est une carte de hachage, il y a beaucoup d'informations sur ceux here.

Answer 2

Si vous regardez wikipedia's set entry, disent-ils

Une structure de données abstraite est une collection, ou agrégée des données. Les données peuvent être des booléens, des nombres, des caractères ou d'autres structures de données. Si l'on considère la structure produits par emballage [1] ou l'indexation, [2], il existe quatre structures de données de base: [3] [4]

non emballés, non indexée: grappe
emballés, non indexée: régler
non emballées, indexées: chaîne (séquence)
emballé, indexé: liste (array)

Ainsi ensembles sont non indexée, ou pas commandé d'une manière spécifique.

La documentation python est d'accord avec ce (toujours vérifier la documentation, Python a quelques-uns des meilleurs que j'ai vu):

5.7. Set Types

Un objet ensemble est une collection non ordonnée de hashable distincte objets. Les utilisations courantes incluent les tests d'appartenance, la suppression des doublons d'une séquence et le calcul d'opérations mathématiques telles que l'intersection, l'union, la différence et la différence symétrique. (Pour d'autres conteneurs voir la construction dans les dict, la liste et les classes de tuple, et le module de recouvrement.)

Answer 3

Outre les bonnes réponses jamylak et crashmstr vous a donné, vous pouvez voir par vous-même un exemple.

>>> stringA="A" 
>>> stringB="B" 
>>> hash(stringA) 
-269909568 
>>> hash(stringB) 
-141909181 
>>> mySet = set() 
>>> mySet.add(stringB) 
>>> mySet.add(stringA) 
>>> mySet 
set(['A', 'B']) 

J'ai donc inséré "B" dans l'ensemble avant "A". Pourquoi montre-t-il "A", "B" (quand une liste garderait l'ordre?). Eh bien, jetez un oeil aux hachages calculés pour les cordes "A" et "B". Lequel est le plus petit? Que se passerait-il si vous faites la même chose avec un dictionnaire où les clés sont ces hachages?:

>>> myDict = {-141909181: "B", -269909568: "A"} 
>>> myDict 
{-269909568: 'A', -141909181: 'B'} 

Peut-être que cela aide un peu à comprendre les ensembles.