Comportement incohérent lors de la tentative de tri des structures imbriquées en Python

Question

J'essaie de trier des structures de listes ou de dictionnaires imbriquées dans Python 3 où la fonction triée intégrée ne peut pas comparer différents types d'objets, comme Python 2. J'ai obtenu La solution fonctionne et j'obtiens le résultat escompté la plupart du temps, mais j'ai un comportement incohérent dans l'un de mes tests qui tente de trier en profondeur un objet dictionnaire. Parfois, quand je lance le code ci-dessous les passes d'affirmation et parfois il échoue pour trier les éléments du dictionnaire de la liste intérieure:

OrderedDict([('journeys', [None, OrderedDict([('id', 1), ('passengers', [1, 2]), ('price', 100)]), OrderedDict([('id', 3), ('passengers', [1, 2]), ('price', 200)]), OrderedDict([('id', 2), ('passengers', [3, 4]), ('price', 150)])])]) 
Traceback (most recent call last): 
    File "solution.py", line 90, in <module> 
    assert new_lst == result 
AssertionError 

que je cherchais à mon code, mais je ne peux pas comprendre ce qui se passe mal car il ressemble à un comportement Cela peut arriver quand on travaille avec des processus ou des threads, mais ce n'est pas le cas. Si vous vous demandez s'il s'agit encore d'un code de version pour le portage du code Python 2.x, Python 3.x et le problème d'incompatibilité de la fonction "trié" entrent en jeu lorsque vous tentez de trier des structures imbriquées de différents types de données intégrés. J'utilise le modèle de visiteur pour parcourir tous les nœuds de manière récursive et j'utilise des règles prédéfinies (self.data_weights) pour trier différents types de données intégrés.

Je suis bloqué en ce moment et toute aide pour déterminer ce qui ne va pas avec le code ci-dessous est très appréciée.

J'exécute le code avec:

Python 3.4.3 (par défaut 17 Nov 2016, 01:08:31) [GCC 4.8.4] sur linux

Mise à jour : Mes tests passent régulièrement avec Python 3.6.2 (voir la version python ci-dessous). Le comportement étrange que j'éprouve se produit avec Python 3.4.3. Des idées?

Python 3.6.2 (par défaut 20 Jul 2017, 08:43:29) [GCC 4.9.4] sur linux

import collections 
from collections import OrderedDict 

class NodeVisitor: 
    def visit(self, node): 
     methname = 'visit_' + type(node).__name__ 
     meth = getattr(self, methname, None) 
     if meth is None: 
      meth = self.generic_visit 
     return meth(node) 

    def generic_visit(self, node): 
     raise RuntimeError('No {} method'.format('visit_' + type(node).__name__)) 


class Evaluator(NodeVisitor): 
    def __init__(self): 
     self.data_types = ["NoneType", "int", "float", "bool", 
          "str", "tuple", "list", "dict"] 

    def sort_node(self, node): 
     self.data_weights = collections.OrderedDict((i, []) for i in self.data_types) 
     for elem in node: 
      try: 
       self.data_weights[type(elem).__name__].append(elem) 
      except KeyError: 
       print (('Encountered unsuported data type "{}". \ 
         Ignoring it!').format(type(elem).__name__)) 
       continue 
     for k, v in self.data_weights.items(): 
      if k != 'dict': 
       v.sort() 
      else: 
       v.sort(key=lambda x: str(x)) 
     result = [] 
     for v in self.data_weights.values(): 
      if v: 
       for item in v: 
        result.append(item) 
     return result 

    def generic_visit(self, node): 
      return node 

    def visit_tuple(self, node): 
     sorted_node = self.sort_node(node) 
     return tuple(self.visit(elem) for elem in sorted_node) 

    def visit_str(self, node): 
     return ''.join(sorted(node)) 

    def visit_list(self, node): 
     sorted_node = self.sort_node(node) 
     return [self.visit(elem) for elem in sorted_node] 

    def visit_dict(self, node): 
     sorted_node = self.sort_node(node) 
     return collections.OrderedDict((k, self.visit(node[k])) for k in sorted_node) 


if __name__ == "__main__": 
    alist ={ 
    'journeys': [ 
    {'id': 1, 'passengers': [1, 2], 'price': 100}, 
    {'id': 3, 'passengers': [2, 1], 'price': 200}, 
    {'id': 2, 'passengers': [4, 3], 'price': 150}, 
    None, 
    ] 
    } 

    new = Evaluator() 
    new_lst = (new.visit(alist)) 
    print (new_lst) 

    expected = OrderedDict([ 
    ('journeys', [ 
    None, 
    OrderedDict([('id', 1), ('passengers', [1, 2]), ('price', 100)]), 
    OrderedDict([('id', 2), ('passengers', [3, 4]), ('price', 150)]), 
    OrderedDict([('id', 3), ('passengers', [1, 2]), ('price', 200)]) 
    ]) 
    ]) 
    assert new_lst == expected 

Answer 1

Je ne sais pas ce qui est la cause de votre échec assert: Je n'ai pas trouvé le comparatif spécifique qui peut parfois être faux. Mais je pense que cela pourrait être causé par cette ligne:

v.sort(key=lambda x: str(x)) 

où vous utilisez le str d'une valeur qui est un dict pour trier vos données.

Dans tous les cas, les symptômes me suggèrent qu'il est causé par le non-déterminisme spécifié de Python dans l'ordre de l'itération sur les dictionnaires.

En Python 2.7, si vous itérez sur un dictionnaire (y compris, par exemple, en appelant str dessus) alors vous obtiendrez un ordre arbitraire. Cependant, cet ordre sera toujours le même chaque fois que le même dictionnaire est construit de la même manière, avec la même séquence d'insertions et de suppressions.

Pour Python 3.3 à 3.5 ce n'était plus vrai. En raison de l'introduction de la randomisation de hachage par défaut, les invocations successives de Python pourraient changer cet ordre pour le dictionnaire même s'il a été construit de la même manière. La commande serait cohérente pendant la durée de vie d'un seul interprète mais pourrait changer la fois suivante.

En Python 3.6 qui a encore changé. Les dictionnaires conservent maintenant l'ordre dans lequel ils sont construits et l'itération est toujours dans cet ordre.

Donc je suspect que votre test est sensible à l'ordre d'itération d'un dictionnaire et que cela donne les résultats incohérents que vous voyez.