Discussion :

[souki22]

Bonjour à tous,

J'ai écrit un script permettant de représenter les entiers naturels avec un DIET (discrete interval encoding tree). C'est en gros un arbre binaire dont les valeurs des noeuds sont des intervalles d'entiers. Je me suis basée sur l'article suivant :
http://web.engr.oregonstate.edu/~erw...Diet_JFP98.pdf

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class node:
        def __init__(self,n_Left=None,n_Right=None,LeftChild_=None,RightChild_=None):
          self.interval=[min(n_Left,n_Right),max(n_Left,n_Right)]
          self.RightChild=RightChild_
          self.LeftChild=LeftChild_
        def length(self):
            if (self.interval,self.LeftChild,self.RightChild)==([None,None],None,None):
                raise EmptyNode()
            return self.interval[1]-self.interval[0]+1
 
 
    class diet:
        def __init__(self,root_=None):
            self.root=root_
 
        def member(self,saught_value):
            node_=self.root #a node instance
            if node_==None: return False
            if (saught_value>=(node_.interval)[0]) and (saught_value<=(node_.interval)[1]):
                return True
            if saught_value<(node_.interval)[0]:
                L=diet(node_.LeftChild)
                return L.member(saught_value)
            R=diet(node_.RightChild)
            return R.member(saught_value)
 
        def append(self,value):
            if self.member(value):
                return self
            node_=self.root
            if node_==None:
                return diet(node(value,value))
            right_child=node_.RightChild
            left_child=node_.LeftChild
            if value<(node_.interval)[0] :
              if value+1==(node_.interval)[0] :
                Root=node(value,(node_.interval)[1],left_child,right_child)
                return joinLeft(diet(Root))
              else:
                subtree=diet(left_child) 
                Root=node((node_.interval)[0],(node_.interval)[1],subtree.append(value),right_child)
                return diet(Root)
            if value >(node_.interval)[1]:
              if value==(node_.interval)[1]+1:
                Root=node((node_.interval)[0],value,left_child,right_child)
                return joinRight(diet(Root))
              else:
                subtree=diet(right_child  )
                Root=node((node_.interval)[0],(node_.interval)[1],left_child,subtree.append(value))             
                return diet(Root)

Maintenant, je suis entrain de lancer des tests sur ce que j'ai codé en utilisant unittest :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 #TEST
    max_number_of_nodes=20 
    maximum=100
    minimum=0
 
    class Tests_Cases(unittest.TestCase):
        def setUp(self):
            self.number_of_nodes=random.randint(0,max_number_of_nodes)
            self.nLeft=random.randint(minimum,maximum)
            self.nRight=random.randint(minimum,maximum)
            self.root=node(self.nLeft,self.nRight)
            self.tree=diet(self.root)
            self.values=[]
            for i in range(max_number_of_nodes-1):
                (self.values).append(random.randint(minimum,maximum))
        def test_member(self):
            x=random.randint(minimum,maximum)
            self.assertFalse(diet().member(x))
            self.assertTrue(((self.tree).member(self.nLeft))&((self.tree).member(self.nRight)))
            for v in self.values:
                self.tree=(self.tree).append(v)
            for v in self.values:
                self.assertTrue((self.tree).member(v))

En exécutant ces tests, j'obtiens un message d'erreur que je ne comprends pas. Voici le message :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
ERROR: test_member (__main__.Tests_Cases)
 
    ----------------------------------------------------------------------
    Traceback (most recent call last):
      File "script.py", line 155, in test_member
        self.tree=(self.tree).append(v)
      File "script.py", line 101, in append
        if self.member(value):
      File "script.py", line 96, in member
        return R.member(saught_value)
      File "script.py", line 90, in member
        if (saught_value>=(node_.interval)[0]) and (saught_value<=(node_.interval)[1]):
    AttributeError: diet instance has no attribute 'interval'

Je n'arrive pas à comprendre pourquoi il considère que node_ est une instance de diet lorsqu'il exécute R.member(saught_value). node_ est censé être le noeud racine de R, je ne vois pas en quoi il pense que c'est un diet.

Si vous pouvez m'aider à résoudre ce problème et y voir plus clair, ça serait vraiment génial.

Bien à vous.

[VinsS]

Salut,

Ton problème vient peut-être d'ici:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
            for v in self.values:
                self.tree=(self.tree).append(v)

donc self.tree est modifié à chaque valeur, celles-ci étant aléatoires.

Il s'ensuit que self.tree pourrait être:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
                return joinLeft(diet(Root))
                # ou
                return joinRight(diet(Root))

Que sont ces joinLeft(), joinRight() ? Que retournent-ils ?

N'hésite pas à faire usage de print pour vérifier le type de tes données et objets.

[wiztricks]

Salut,

Je n'arrive pas à comprendre pourquoi il considère que node_ est une instance de diet lorsqu'il exécute R.member(saught_value). node_ est censé être le noeud racine de R, je ne vois pas en quoi il pense que c'est un diet

L'interpréteur Python ne pense pas, il se contente d’exécuter les instructions de votre programme.
Comprendre pourquoi node_ se retrouve instance de diet (plutôt qu'autre chose) s'appelle debugger le code.

Le votre étant passablement compliqué, je ne vois pas comment s'en sortir sans passer par le debugger symbolique.
Il permet d'exécuter le code instruction par instruction et de regarder ce qui est assigné à quoi à chaque étape.

C'est un outil qu'on apprend à maîtriser dans ces cas comme çà.

- W

[souki22]

Tout d'abord, je vous remercie pour vos réponses.

joinRight et joinLeft sont censés arranger les valeurs des noeuds de l'arbre lorsque l'élément que l'on veut lui ajouter s'avère être d'une unité juste avant (ou juste après) un bord d'un des intervalles de l'arbre. En effet, le DIET respecte certaines règles (expliquées dans l'url) et il faut s'assurer que l'arbre obéira à ces règles lorsqu'on va lui ajouter un élément. Ces deux fonctions prennent en argument une instance de diet, et renvoient une instance de diet, comme on peut le voir ci dessous :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def joinLeft(diet_):
       node_=diet_.root
       right_child=node_.RightChild
       left_child=node_.LeftChild
       if left_child==None: return diet_
       (x,y,L)=splitMax(left_child)
       if y+1==(node_.interval)[0]:
               ToBeReturned=node(x,(node_.interval)[1],L,right_child)
               return diet(ToBeReturned)
       else:
               TobeReturned=node((node_.interval)[0],(node_.interval)[1],left_child,right_child)
               return diet(ToBeReturned)
 
#joinRight est défini de la même manière sauf qu'on raisonne symétriquement sur les noeuds enfants

Je suis maintenant entrain de mettre des print pour savoir un peu ce qui se passe. Je vous informe si j'aboutis à quelque chose.


En réponse à wiztricks, peux tu me dire s'il te plaît un peu plus sur le debugger symbolique (nom du module à importer, nom de l'objet, etc ….) afin que je puisse lire la documentation dessus ? J'avoue que je ne sais pas comment debugger en python.

[wiztricks]

En réponse à wiztricks, peux tu me dire s'il te plaît un peu plus sur le debugger symbolique (nom du module à importer, nom de l'objet, etc ….) afin que je puisse lire la documentation dessus ? J'avoue que je ne sais pas comment debugger en python.

Le debugger Python est avec le module pdb.
Mais l'utiliser "brut de fonderie" est assez ardu.
Normalement, on programme avec un IDE qui intègre les fonctionnalités du debugger et qui rend l'interface un peu plus conviviale et indépendante du langage de programmation.
note: si vous vous lancez dans l'écriture de programme compliqués, vous allez passer beaucoup de temps à la mise au point (le debug). Sans outils, c'est galère... même si parfois on ne peut utiliser autre chose que pdb

- W

[souki22]

Je crois comprendre que, dans la méthode member, LeftChild (ou RightChild) est considéré comme une instance de diet quand il n'est pas égal à None.