Choix effectué par Python 3.5 pour choisir les clés lors de leur comparaison dans un dictionnaire

Les dictionnaires sont implémentés en tant que tables de hachage et il y a deux concepts importants lors de l’ajout de clés / valeurs ici: le hachage et l’ égalité .

Pour insérer une clé / valeur particulière, Python calcule d’abord la valeur de hachage de la clé. Cette valeur de hachage est utilisée pour déterminer la ligne de la table où Python doit d’abord essayer de mettre la clé / valeur.

Si la ligne de la table de hachage est vide, great: la nouvelle clé / valeur peut être insérée dans le dictionnaire, en remplissant la ligne vide.

Cependant, s’il y a déjà quelque chose dans cette ligne, Python doit tester les clés pour l’égalité. Si les clés sont égales (en utilisant == ), elles sont réputées être la même clé et Python doit simplement mettre à jour la valeur correspondante sur cette ligne.

(Si les clés ne sont pas égales, Python examine les autres lignes de la table jusqu’à ce qu’il trouve la clé ou atteigne une ligne vide, mais cela n’est pas pertinent pour cette question.)

Lorsque vous écrivez {True: 'yes', 1: 'No'} , vous demandez à Python de créer un nouveau dictionnaire, puis de le remplir avec deux paires clé / valeur. Celles-ci sont traitées de gauche à droite: True: 'yes' puis 1: 'No' .

Nous avons hash(True) égal à 1. La clé True va à la ligne 1 dans la table de hachage et la chaîne 'yes' est sa valeur.

Pour la paire suivante, Python voit que le hash(1) est également 1 et regarde donc la ligne 1 de la table. Il y a déjà quelque chose, alors Python vérifie maintenant les clés pour l’égalité. Nous avons 1 == True donc 1 est réputé être la même que True et sa valeur correspondante est changée en chaîne 'No' .

Cela se traduit par un dictionnaire avec une entrée: {True: 'No'} .

Si vous voulez examiner les entrailles de CPython 3.5 pour voir ce que la création d’un dictionnaire a l’air au-dessous du niveau surface-Python, voici plus de détails.

• Le code Python {True: 'yes', 1: 'No'} est analysé en jetons et donné au compilateur. Étant donné la syntaxe, Python sait qu’un dictionnaire doit être créé en utilisant les valeurs entre accolades. Le code d’octet pour charger les quatre valeurs sur la stack de la machine virtuelle ( LOAD_CONST ), puis créer le dictionnaire ( BUILD_MAP ) est mis en queue.

• Les quatre valeurs constantes sont placées en haut de la stack dans l’ordre où elles sont visibles:

   'No' 1 'yes' True 

• L’opcode BUILD_MAP est alors appelé avec l’argument 2 (Python a compté deux paires clé / valeur). Cet opcode est chargé de créer réellement un dictionnaire à partir des éléments de la stack. Cela ressemble à ceci :

   TARGET(BUILD_MAP) { int i; PyObject *map = _PyDict_NewPresized((Py_ssize_t)oparg); if (map == NULL) goto error; for (i = oparg; i > 0; i--) { int err; PyObject *key = PEEK(2*i); PyObject *value = PEEK(2*i - 1); err = PyDict_SetItem(map, key, value); if (err != 0) { Py_DECREF(map); goto error; } } while (oparg--) { Py_DECREF(POP()); Py_DECREF(POP()); } PUSH(map); DISPATCH(); } 

Les trois étapes clés sont les suivantes:

1. Une table de hachage vide est créée à l’aide de _PyDict_NewPresized . Les petits dictionnaires (de quelques éléments seulement, comme 2 dans ce cas) nécessitent un tableau de huit lignes.

2. La boucle for est entrée, commençant à 2 (dans ce cas) et comptant jusqu’à 0. PEEK(n) est une macro qui pointe vers le nième élément de la stack. Par conséquent, lors de la première itération de la boucle, nous aurons

 PyObject *key = PEEK(2*2); /* item 4 down the stack */ PyObject *value = PEEK(2*2 - 1); /* item 3 down the stack */ 

Cela signifie que la *key sera True et que la *value sera 'yes' sur la première boucle. Au second il sera 1 et 'No' .

3. PyDict_SetItem est appelé dans chaque boucle pour mettre la *key actuelle et la *value dans le dictionnaire. C’est la même fonction qui est appelée lorsque vous écrivez dictionary[key] = value . Il calcule le hachage de la clé pour déterminer où chercher en premier dans la table de hachage, puis, si nécessaire, compare la clé à une clé existante sur cette ligne (comme indiqué ci-dessus).

La prémisse de base est – True et 1 ont les mêmes hachages et sont égaux les uns aux autres – c’est pourquoi ils ne peuvent pas être des clés séparées (object techniquement inégal avec les mêmes hachages – mais les collisions de hachage diminuent les performances).

 >>> True == 1 True >>> hash(1) 1 >>> hash(True) 1 

Maintenant, considérons un bytecode:

 import dis dis.dis("Dic = { True: 'yes', 1: 'No'}") 

Cela imprime:

  0 LOAD_CONST 0 (True) 3 LOAD_CONST 1 ('yes') 6 LOAD_CONST 2 (1) 9 LOAD_CONST 3 ('No') 12 BUILD_MAP 2 15 STORE_NAME 0 (Dic) 18 LOAD_CONST 4 (None) 21 RETURN_VALUE 

Fondamentalement, ce qui se passe, c’est que dict literal est symbolisé par des clés et des valeurs, et ils sont poussés à emstackr. Après cela, BUILD_MAP 2 couvre deux paires de (clés, valeurs) au dictionnaire.

L’ordre le plus probable des données sur la stack (qui semble être déterminé par l’ordre des clés dans le littéral dict) et les détails d’ BUILD_MAP de BUILD_MAP déterminent les clés et les valeurs dict.

Il semble que les affectations de valeurs-clés soient effectuées dans l’ordre défini dans le dict literal. L’affectation se comporte de la même manière que l’opération d[key] = value , c’est donc essentiellement:

• si la key n’est pas dans dict (par égalité): append la key do dict
• stocker la value sous la key

Étant donné {True: 'yes', 1: 'No'} :

1. Commencez avec {}

2. Ajouter (True, 'yes')

   1. True n’est pas dans dict -> (True, hash(True)) == (True, 1) est une nouvelle clé dans dict
   2. Mettre à jour la valeur de la clé égale à 1 pour 'yes'

3. Ajouter (1, 'no')

   1. 1 est dans dict ( 1 == True ) -> il n’y a pas besoin de nouvelle clé dans le dictionnaire
   2. Mettre à jour la valeur de la clé égale à 1 ( True ) avec la valeur 'no'

Résultat: {True: 'No'}

Comme je l’ai dit, je ne sais pas si cela est garanti par les spécifications de Python ou s’il s’agit simplement d’un comportement défini par l’implémentation de CPython, il se peut qu’il diffère dans les autres implémentations d’interpréteur.

True et 1 sont des objects différents, mais ils ont tous deux la même valeur:

 >>> True is 1 False >>> True == 1 True 

Ceci est similaire à deux chaînes qui peuvent avoir la même valeur, mais sont stockées dans des emplacements de mémoire différents:

 >>> x = str(12345) >>> y = str(12345) >>> x == y True >>> x is y False 

Tout d’abord, un élément est ajouté au dictionnaire; alors, lorsque l’autre est ajouté, cette valeur existe déjà en tant que clé . Ainsi, la clé est mise à jour, les valeurs clés sont uniques.

 >>> {x: 1, y: 2} {"12345": 2} 

Si la clé est déjà présente dans le dictionnaire, elle ne remplace pas la clé uniquement la valeur associée.

Je crois que l’écriture x = {True:"a", 1:"b"} est dans le sens de:

 x = {} x[True] = "a" x[1] = "b" 

et au moment où il atteint x[1] = "b" la clé True est déjà dans le dict alors pourquoi le changer? pourquoi ne pas simplement remplacer la valeur associée.

La commande semble être la raison. Exemple de code:

 >>> d = {True: 'true', 1: 'one'} >>> d {True: 'one'} >>> d = {1: 'one', True: 'true'} >>> d {1: 'true'} 

C’est une déclaration ambiguë.

Logique: d = { True: 'no', 1: 'yes'}

Lorsque python évalue l’expression, il le fait de manière séquentielle, ce qui équivaut à cela.

d = dict() d[True] = 'no' d[1] = 'yes'

La constante True est la clé, mais elle est évaluée à 1, vous définissez donc simplement la valeur de la clé deux fois.