Bonnes pratiques, conseils

14 octobre 2010 à 9:20:39

Hello !

Je me suis mis recement au python.
J'aimerais avoir des conseils techniques sur le code qui va suivre. Il y a t'il moyen de l'ameliorer, de l'optimiser ? Peut t'on faire certaines choses plus facilement, en moins de lignes ?
(J'aimerais votre avis sur le code python en temps que tel, non sur la modelisation objet que j'ai choisi)

Le code implemente l'algo de Dijkstra sur un graph. Le graph est obtenu en parsant un fichier, il est oriente et value.
Le but est de trouve le plus cours chemin entre le sommet 'a', et tous les autres sommets du graph.

Voila le code :

main.py:

#!/usr/bin/python                                                                                                                                                      

import sys
from graph import *
from exception import *

if len(sys.argv) == 2:                                                                                                                                                 
    try:                                                                                                                                                               
        myGraph = Graph(sys.argv[1])                                                                                                                                   
        myGraph.buildVertex()                                                                                                                                          
        myGraph.buildAdjMatrix()                                                                                                                                       
        myGraph.findShortestWay()                                                                                                                                      
        myGraph.printInfo()                                                                                                                                            
                                                                                                                                                                       
    except IOError:                                                                                                                                                    
        print "Error: Input Output error with file " + sys.argv[1]                                                                                                     
    except HandleException as error:                                                                                                                                   
        print error.getErrorDesc()                                                                                                                                     
                                                                                                                                                                       
else:                                                                                                                                                                  
    print "Usage: ./main.py filename.txt"

exception.py:

class   HandleException:
    def __init__(self, errorDesc):
        self._errorDesc = errorDesc

    def getErrorDesc(self):
        return self._errorDesc

graph.py:

from exception import *

class   Graph:
    def __init__(self, fileName):
        myFile = open(fileName)
        self._vertex = []
        self._arc = []
        self._dist = []
        self._path = []
        self._fileName = fileName

        content = myFile.read()

        lines = content.split('\n')
        self._size = int(lines.pop(0))
        self._oArcMatrix = self.createMatrix(self._size, self._size)
        lines.pop()
        for thisLine in lines:
            arc = thisLine.split(' ')
            if len(arc) != 3:
                raise(HandleException('Error: Invalid line format'))
            elif int(arc[2]) < 0:
                raise(HandleException('Error: Invalid vertex distance'))
            self._arc.append([arc[0], arc[1], arc[2]])
        myFile.close()


    def createMatrix(self, sizeX, sizeY):
        matrix = []
        for index in range(sizeY):
            matrix.append([])
            for iterator in range(sizeX):
                if iterator == index:
                    matrix[index].append(0)
                else:
                    matrix[index].append(-1)
        return matrix

    def buildVertex(self):                                                                                                                                             
        for arc in self._arc:                                                                                                                                          
            dist = arc.pop()                                                                                                                                           
            for value in arc:                                                                                                                                          
                try:                                                                                                                                                   
                    self._vertex.index(value)                                                                                                                          
                except ValueError:                                                                                                                                     
                    self._vertex.append(value)                                                                                                                         
            arc.append(dist)                                                                                                                                           
        self._vertex.sort()                                                                                                                                            
                                                                                                                                                                       
                                                                                                                                                                       
    def buildAdjMatrix(self):                                                                                                                                          
        for arc in self._arc:                                                                                                                                          
            self._oArcMatrix[self._vertex.index(arc[0])][self._vertex.index(arc[1])] = int(arc[2])                                                                     
                                                                                                                                                                       
                                                                                                                                                                       
    def printInfo(self):                                                                                                                                               
        print "Nom du fichier: " + self._fileName                                                                                                                      
        print "Nombre de sommets: " + str(self._size)                                                                                                                  
        print "Nombre d'arcs: " + str(len(self._arc))                                                                                                                  
        for arc in self._arc:                                                                                                                                          
            print arc                                                                                                                                                  
        print "Plus courts chemins :"                                                                                                                                  
        print "Distance:"                                                                                                                                              
        for dist in self._dist:                                                                                                                                        
            print "a -> " + dist[0] + ' = ' + str(dist[1])                                                                                                             
        print "Detail des chemins:"                                                                                                                                    
        for path in self._path:                                                                                                                                        
            print path

    def dijkstra(self, way, end):                                                                                                                                      
        content = []                                                                                                                                                   
        maxi = 0xffffffff                                                                                                                                              
        for iterator in range(self._size):                                                                                                                             
            if way[len(way) - 1][iterator] == -2:                                                                                                                      
                content.append(-2)                                                                                                                                     
            else:                                                                                                                                                      
                content.append(-1)                                                                                                                                     
                if way[len(way) - 1][iterator] >= 0 and way[len(way) - 1][iterator] < maxi:                                                                            
                    maxi = way[len(way) - 1][iterator]                                                                                                                 
                    index = iterator                                                                                                                                   
                                                                                                                                                                       
        if index != self._vertex.index(end):                                                                                                                           
            content[index] = -2                                                                                                                                        
            way.append(content)                                                                                                                                        
                                                                                                                                                                       
            theEnd = True                                                                                                                                              
            for iterator in range(self._size):                                                                                                                         
                if way[len(way) - 2][iterator] != -2:                                                                                                                  
                    if self._oArcMatrix[index][iterator] > 0:                                                                                                          
                        theEnd = False                                                                                                                                 
                        p = way[len(way) - 2][index] + self._oArcMatrix[index][iterator]                                                                               
                        if way[len(way) - 1][iterator] == -1 or p < way[len(way) - 1][iterator]:                                                                       
                            way[len(way) - 1][iterator] = p                                                                                                            
                        else:                                                                                                                                          
                            way[len(way) - 1][iterator] = way[len(way) - 2][iterator]                                                                                  
                                                                                                                                                                       
                    elif way[len(way) - 1][iterator] != -2:                                                                                                            
                        way[len(way) - 1][iterator] = way[len(way) - 2][iterator]                                                                                      
            if theEnd is not True:                                                                                                                                     
                self.dijkstra(way, end)                                                                                                                                
            else:                                                                                                                                                      
                raise HandleException("Error: No path found")

    def buildWay(self, way, vertex):                                                                                                                                   
        path = []                                                                                                                                                      
        toGoIndex = vertex                                                                                                                                             
        goUp = len(way) - 1                                                                                                                                            
                                                                                                                                                                       
        toGoValue = way[goUp][self._vertex.index(toGoIndex)]                                                                                                           
                                                                                                                                                                       
        while toGoIndex != 'a':                                                                                                                                        
            value = way[goUp][self._vertex.index(toGoIndex)]                                                                                                           
            path.insert(0, toGoIndex)                                                                                                                                  
            while value == toGoValue:                                                                                                                                  
                goUp -= 1                                                                                                                                              
                value = way[goUp][self._vertex.index(toGoIndex)]                                                                                                       
                                                                                                                                                                       
            goLeft = self._size - 1                                                                                                                                    
            maxi = 0xffffffff                                                                                                                                          
            while goLeft >= 0:                                                                                                                                         
                if way[goUp][goLeft] >= 0 and way[goUp][goLeft] < maxi:                                                                                                
                    maxi = way[goUp][goLeft]                                                                                                                           
                    index = goLeft                                                                                                                                     
                goLeft -= 1                                                                                                                                            
                                                                                                                                                                       
            toGoIndex = self._vertex[index]                                                                                                                            
            toGoValue = way[goUp][index]                                                                                                                               
        path.insert(0, 'a')                                                                                                                                            
        path.append(way[len(way) - 1][self._vertex.index(vertex)])                                                                                                     
        return path                                                                                                                                                    
                                                                                                                                                                       
    def findShortestWay(self):                                                                                                                                         
        for vertex in self._vertex:                                                                                                                                    
            way = []                                                                                                                                                   
            content = []                                                                                                                                               
            for iterator in range(self._size):                                                                                                                         
                content.append(-1)                                                                                                                                     
            content[self._vertex.index('a')] = 0                                                                                                                       
            way.append(content)                                                                                                                                        
                                                                                                                                                                       
            try:                                                                                                                                                       
                self.dijkstra(way, vertex)                                                                                                                             
                if vertex != 'a':                                                                                                                                      
                    self._path.append(self.buildWay(way, vertex))                                                                                                      
                self._dist.append([vertex, way[len(way) - 1][self._vertex.index(vertex)]])                                                                             
            except HandleException as error:                                                                                                                           
                self._dist.append([vertex, -1])

Et un fichier de test qui contient un graph:
(La premiere ligne contient le nombre de sommet dans le graph, les autres lignes les arretes avec leur valuation)

8
a b 4
a e 3
b c 3
b e 2
c f 2
d b 5
d c 2
e d 1
f d 1
f e 3
y z 5

Ou le tout dans une archive:
http://vlad.washere.free.fr/src/Python/work.tar

Voila (:

Découvrez un petit jeu Android bien sympa : http://www.siteduzero.com/forum/sujet/appli-jeu-android-cube-racer

nohar

14 octobre 2010 à 9:30:25

Déjà, à chaque fois que tu fais way[len(way) -1] , tu peux le remplacer par way[-1] .

Ensuite, tu peux beaucoup alléger tes boucles en les organisant différemment. Au lieu d'itérer sur un indice explicitement, tu peux itérer sur les éléments de way[-1] et way[-2] :

for it1, it2 in zip(way[-1], way[-2]):
    # ...

En faisant ainsi, par exemple, la ligne suivante (dans ton code) :

way[len(way) - 1][iterator] = way[len(way) - 2][iterator]

devient :

it1 = it2

Niveau lisibilité, y'a pas photo, et ton code sera probablement plus rapide.

Edit :
En fait, ceci ne fonctionne que si les types parcourus par l'itérateur sont des objets (donc pas des nombres). Sinon, ce que tu peux faire aussi, c'est renverser ton tableau way (inverser les indices) et itérer dessus directement (ton itérateur retourne donc des listes), ce qui donnerait (pour la ligne que j'ai prise en exemple) :

for it in way:
    # ...
    it[-1] = it[-2]
    # ...

Enfin, si tu as quand même besoin d'accéder aux indices, tu peux utiliser la fonction enumerate .

D'une manière générale, il est plus pythonique d'itérer sur les éléments d'une séquence directement plutôt que de faire un for "à-la-C" sur les indices.

Zeste de Savoir, le site qui en a dans le citron !

Maxibolt

14 octobre 2010 à 12:37:40

Je ne me suis jamais penché sur le module graph, mais il me semble que dans ton try, il n'y a que la première ligne qui soit susceptible de lever une exception qu'on puisse traiter après. dans ce cas, il vaut mieux ne garder que cette ligne dans le bloc, et mettre les autres dans le bloc else (pour avoir un meilleur contrôle sur l'endroit où se produisent les exceptions).

Lord Casque Noir

14 octobre 2010 à 12:54:15

Un exemple pour createMatrix

def createMatrix(self, sizeX, sizeY):
        matrix = [ [-1]*sizeX for y in xrange( sizeY ) ]
	for x in xrange( min( sizeX, sizeY )):
		matrix[x][x] = 0
	return matrix

Ensuite, tu utilises beaucoup de list.index(). On utilise rarement ceci, puisque python a un type dict, et une recherche dans un dict est beaucoup plus rapide qu'une recherche dans une liste...

Yannshu

15 octobre 2010 à 9:54:23

Merci pour tous ces conseils !

Citation : NoHaR

Déjà, à chaque fois que tu fais way[len(way) -1] , tu peux le remplacer par way[-1] .

C'est tout simplement genial !

Citation : NoHaR

Edit :
En fait, ceci ne fonctionne que si les types parcourus par l'itérateur sont des objets (donc pas des nombres). Sinon, ce que tu peux faire aussi, c'est renverser ton tableau way (inverser les indices) et itérer dessus directement (ton itérateur retourne donc des listes), ce qui donnerait (pour la ligne que j'ai prise en exemple) :
for it in way:
    # ...
    it[-1] = it[-2]
    # ...

Humm, cela ne va pas avoir le meme effet que le code que j'ai. En effet, si on fait cela, on va modifier way[0][-1], way[1][-1], way[2][-1] ..., et non way[-1][0], way[-1][1], way[-1][2] ... comme mon code le fait. Mais l'idee est cependant excellente.

Citation : Maxibolt

Je ne me suis jamais penché sur le module graph, mais il me semble que dans ton try, il n'y a que la première ligne qui soit susceptible de lever une exception qu'on puisse traiter après. dans ce cas, il vaut mieux ne garder que cette ligne dans le bloc, et mettre les autres dans le bloc else (pour avoir un meilleur contrôle sur l'endroit où se produisent les exceptions).

Effectivement, merci.

Citation : Lord Casque Noir

matrix = [ [-1]*sizeX for y in xrange( sizeY ) ]

Je ne savais pas qu'on pouvait faire ca, c'est super pratique.

Citation : Lord Casque Noir

Ensuite, tu utilises beaucoup de list.index(). On utilise rarement ceci, puisque python a un type dict, et une recherche dans un dict est beaucoup plus rapide qu'une recherche dans une liste...

J'utilise les listes car elles sont ordonnees, contraitement aux dictionnaires. Mais je prend note

(au final, c'est un peu la meme chose que des std::list & std::map en C++ non ?)

Découvrez un petit jeu Android bien sympa : http://www.siteduzero.com/forum/sujet/appli-jeu-android-cube-racer

nohar

15 octobre 2010 à 10:16:42

Citation : Yannshu

Citation : NoHaR
Edit :
En fait, ceci ne fonctionne que si les types parcourus par l'itérateur sont des objets (donc pas des nombres). Sinon, ce que tu peux faire aussi, c'est renverser ton tableau way (inverser les indices) et itérer dessus directement (ton itérateur retourne donc des listes), ce qui donnerait (pour la ligne que j'ai prise en exemple) :
for it in way:
    # ...
    it[-1] = it[-2]
    # ...
Humm, cela ne va pas avoir le meme effet que le code que j'ai. En effet, si on fait cela, on va modifier way[0][-1], way[1][-1], way[2][-1] ..., et non way[-1][0], way[-1][1], way[-1][2] ... comme mon code le fait. Mais l'idee est cependant excellente.

Ben justement, on dirait bien que c'est le genre de cas qui justifie de représenter tes données différemment : en transposant ta matrice.
Ça peut se faire plutôt simplement avec la fonction zip :

transposee = [list(t) for t in zip(*way)]

Si tu transposes juste pour itérer dessus, tu peux même itérer sur ta transposée en en faisant un générateur :

transposee = (list(t) for t in zip(*way))
for it in transposee:
    #...
    it[-1] = it[-2]

De cette manière, seule ta fonction dijkstra change (pas le code qui l'utilise).

Edit : À noter, si tu utilises python 2, que tu peux utiliser itertools.izip au lieu de zip.
Par contre, je pense qu'en faisant ça, tu ne modifies pas le tableau <way> en-place dans ta boucle, étant donné que tu ne manipules pas des objets...

Zeste de Savoir, le site qui en a dans le citron !