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

Question

Lors de la construction d'un dictionnaire comme suit:

dict = { True: 'yes', 1: 'No'}

Quand je le lance dans interactive Python interprète le dict est représenté de cette façon:

dict = {True: 'No'}

Je comprends que les valeurs True et 1 sont égaux en raison de la contrainte de type parce que lorsque l'on compare les types numériques, le rétrécissement type est élargi à l'autre type (boolean est un enfant de l'entier). Donc, ce que j'ai compris de la documentation, lorsque nous entrons True == 1 Python convertit True de 1 et les compare.

Ce que je ne comprends pas, c'est pourquoi l' True est sélectionné comme l'un des principaux au lieu de 1.

Je suis en manque de quelque chose?

Answer 1

Les dictionnaires sont mis en œuvre comme les tables de hachage et il y a deux notions importantes lors de l'ajout de clés/valeurs de ici: de hachage et de l'égalité.

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

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

Cependant, si il y a déjà quelque chose dans cette ligne, Python a besoin de tester les clés pour l'égalité. Si les clés sont égaux (à l'aide d' ==) alors qu'ils sont réputés être la même clé et Python juste besoin de mettre à jour la valeur correspondante sur la ligne.

(Si les touches ne sont pas égaux Python regarde les autres lignes dans la table jusqu'à ce qu'il trouve la clé ou atteint d'une ligne vide, mais ce n'est pas pertinent pour cette question.)

---

Lorsque vous écrivez {True: 'yes', 1: 'No'}, vous dites Python pour créer un nouveau dictionnaire et le remplir avec deux paires clé/valeur. Ceux-ci sont traités de gauche à droite: True: 'yes' alors 1: 'No'.

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

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

Il en résulte un dictionnaire avec une entrée: {True: 'No'}.

---

Si vous voulez à scruter les entrailles de Disponible 3.5 pour voir ce que la création d'un dictionnaire regarde en dessous de la surface-Python niveau, voici plus en détail.

• Le code Python {True: 'yes', 1: 'No'} est analysée en jetons, et donné pour le compilateur. Compte tenu de la syntaxe, Python sait qu'un dictionnaire doit être créée en utilisant les valeurs à l'intérieur des accolades. De Byte code pour charger les quatre valeurs sur la machine virtuelle de la pile (LOAD_CONST), puis de construire le dictionnaire (BUILD_MAP) est mis en attente.

• Les quatre valeurs constantes sont poussées sur le haut de la pile dans l'ordre dans lequel ils sont vus:
  
  

  'No'
  1
  'yes'
  True
  

• L'opcode BUILD_MAP est alors appelée avec l'argument 2 (Python compté deux paires clé/valeur). Cet opcode est responsable de la création du dictionnaire à partir des éléments sur la pile. Il 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 ici sont comme suit:

1. Une table de hachage vide est créé à l'aide d' _PyDict_NewPresized. Petits dictionnaires (de seulement quelques éléments, comme les 2 dans ce cas) besoin d'une table avec huit lignes.

2. L' for boucle est entré, à partir de 2 (dans ce cas) et le compte à rebours à 0. PEEK(n) est une macro qui pointe vers le n-ième élément vers le bas de la pile. Par conséquent, à la première itération de la boucle, nous allons avoir

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

Cela signifie qu' *key sera True et *value sera 'yes' sur la première boucle à travers. Sur le second, il sera 1 et 'No'.

3. PyDict_SetItem est appelée à chaque tour de boucle pour mettre l' *key et *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é de travail où regarder en premier dans la table de hachage, puis, si nécessaire, de comparer la clé de toutes les clés existant sur cette ligne (voir ci-dessus).

Answer 2

Principe de base est - True et 1 ont même hachages et sont égaux les uns aux autres - c'est pourquoi ils ne peuvent pas être séparés des clés dans une table de hachage (techniquement inégalitaires de l'objet avec le même hachages peut - mais les collisions de hachage diminue 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'}")

Cette affiche:

      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

Essentiellement ce qui se passe est que le dict littérale est sous forme de jeton de clés et de valeurs, et ils sont poussés à pile. Après qu' BUILD_MAP 2 dessous des ailes de deux paires de clés, valeurs) au dictionnaire.

Le plus probable de l'ordre de données sur la pile (ce qui semble être déterminé par l'ordre des clés dans dict littéral) et les détails de mise en œuvre de l' BUILD_MAP décide résultant dict des clés et des valeurs.

Il semble que la clé-valeur des affectations sont effectuées dans l'ordre défini dans la dict littérale. L'affectation se comporte même comme d[key] = value de l'opération, de sorte qu'il est fondamentalement:

• si key n'est pas dans les dict (par l'égalité): ajouter key ne dict
• stocker value sous key

Compte tenu de {True: 'yes', 1: 'No'}:

1. Commencez avec {}

2. Ajouter (True, 'yes')

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

3. Ajouter (1, 'no')

   1. 1 est dans le dict (1 == True) -> il n'est pas nécessaire pour la nouvelle clé dans le dictionnaire
   2. Mise à jour de la valeur pour la clé, qui est égale à 1 (True) avec la valeur 'no'

Résultat: {True: 'No'}

Comme je l'ai commenté, je ne sais pas si c'est guarranted par Python spécifications ou si c'est juste Disponible définis par l'implémentation de comportement, il peut être différent dans d'autres interprète implémentations.

Answer 3

True et 1 sont des objets 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
 

Le premier élément est ajouté au dictionnaire; puis, lorsque l'autre est ajouté, cette valeur existe déjà en tant que clé . Ainsi, la clé est mise à jour, les valeurs de clé sont uniques.

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

Answer 4

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

Je crois qu'écrire x = {True:"a", 1:"b"} va 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 la changer? pourquoi ne pas simplement remplacer la valeur associée.

Answer 5

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'}