IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Calcul scientifique Python Discussion :

Optimisation d'un code sur les matrices d'adjacence [Python 3.X]


Sujet :

Calcul scientifique Python

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Mai 2017
    Messages
    24
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : Mai 2017
    Messages : 24
    Par défaut Optimisation d'un code sur les matrices d'adjacence
    Bonjour,

    J'ai un code qui permet de générer des matrices d'adjacence de façons aléatoires et ensuite qui permet de voir si elle sont connexe ou non. Avec cela je trace ensuite le graphique montrant le pourcentage de matrice connexe en fonction de leur nombre d'arrête. Ce qui m'interesse est pour les cas de très grosses matrices à partir de 100 et donc que cela est très long si quelqu'un peut m'aider à l'optimiser pour gagner ?

    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
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    import random
    import numpy
    import matplotlib.pyplot as plt
     
    def creer_noeud(taille, arrete):
    	L=[]
    	i=0
    	while(i<arrete):
    		al1=random.randint(0,taille-1)
    		al2=random.randint(0,taille-1)
    		if(al1,al2) not in L and (al2,al1) not in L:
    			if al1 == al2:
    				L.append((al1, al2))
    			else:
    				L.append((al1,al2))
    				L.append((al2,al1))
    			i= i + 1
    	return L
     
     
     
    def creer_matrice(taille, arrete):
    	"""int * int-> list[list[int]]
                    Créer une matrice d'adjacence aléatoire d'un graphe non orienté"""
    	mat = [[0] * taille for _ in range(taille)]
    	noeud = creer_noeud(taille, arrete)
    	for i in range(len(noeud)):
    		(x,y)=noeud[i]
    		mat[x][y] = 1
    	return mat
     
    def DFS(mat, src):
    	visite = []
    	DFS_rec(mat, src, visite)
    	return visite
     
    def DFS_rec(mat,src, visite):
    	"""
            Retourne la liste des sommets rencontrés lors
            d'un parcours en profondeur issu du sommet <src>.
     
            Arguments:
            mat -- matrice d'adjacence du graphe
            src -- un sommet du graphe, départ du parcours
     
            >>> DFS([[0, 0, 1, 1, 0], [1, 0, 0, 0, 0], [0, 1, 0, 1, 0], [0, 1, 1, 0, 0], [1, 0, 1, 0, 0]],0)
            {0, 2, 1, 3}
            """
    	visite.append(src)
    	for j in range(0, len(mat)):
    		if j not in visite and mat[src][j] == 1:
    			DFS_rec(mat, j, visite)
    	return visite
     
    def isConnected(mat):
    	"""
            Retourne vrai si le graphe est connexe, faux sinon.
     
            Arguments:
            mat -- matrice d'adjacence du graphe
     
            >>> isConnected([[0, 1, 0], [0, 0, 0], [0, 0, 0]])
            False
     
            >>> isConnected([[0, 1, 0], [0, 0, 1], [0, 0, 0]])
            True
            """
     
    	return (len(DFS(mat, 0)) == len(mat))
     
    def pour_connexe(n, taille, arrete):
    	res=0
    	for i in range(n):
    		if isConnected(creer_matrice(taille, arrete)):
    			res = res + 1
    	return (res * 100)/n 
     
    def liste_connexe(taille, n):
    	R = []
    	for i in range((taille**2)//2):
    		R.append(pour_connexe(n, taille, i))
    		print(i)
    	return R
     
     
    plt.plot(liste_connexe(50, 10))
    plt.title("% de graphe connexe en fonction du nnombre d'arrete")
    plt.ylabel('% de graphe connexe')
    plt.xlabel("nb d'arrete")
    plt.show()
    Merci
    Bonsoir

  2. #2
    Expert éminent
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 741
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 741
    Par défaut
    Salut,

    En utilisant d'une matrice d'adjacences, la complexité est O(n²). Si vous utilisiez des listes de nœuds adjacents, çà tomberait à O(n + m). A partir de là, vous savez comment "optimiser"...

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  3. #3
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Mai 2017
    Messages
    24
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : Mai 2017
    Messages : 24
    Par défaut
    Merci de me répondre si vite mais mon problême est que je dois utiliser des matrices d'adjacence et non des listes.
    Mais merci

  4. #4
    Membre Expert

    Homme Profil pro
    Ingénieur calcul scientifique
    Inscrit en
    Mars 2013
    Messages
    1 229
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur calcul scientifique

    Informations forums :
    Inscription : Mars 2013
    Messages : 1 229
    Par défaut
    C'est bien d'importer numpy, c'est mieux de l'utiliser !

  5. #5
    Membre Expert

    Homme Profil pro
    Ingénieur calcul scientifique
    Inscrit en
    Mars 2013
    Messages
    1 229
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur calcul scientifique

    Informations forums :
    Inscription : Mars 2013
    Messages : 1 229
    Par défaut
    Il y a pas mal de trucs bancal aussi dans ton code.
    Pourquoi stocker la liste des noeuds si tu n'as besoin que de la matrice d'adjacence ? Tire au hasard un noeud, update la matrice d'adjacence et tu peux passer au noeud suivant sans avoir à te rappeler du précédent.

    En utilisant la remarque précédente et en utilisant numpy regardes déjà ci dessous, je gagne sur ma machine par rapport à ton code:
    - 40% sur le temps d'éxécution pour une taille 10
    - je divise le temps de calcul par 2 pour une taille 20

    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
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    import random
    import numpy as np
    import matplotlib.pyplot as plt
    from time import time
     
     
    def creer_noeud(taille, arrete):
    	L=[]
    	i=0
    	while(i<arrete):
    		al1=random.randint(0,taille-1)
    		al2=random.randint(0,taille-1)
    		if(al1,al2) not in L and (al2,al1) not in L:
    			if al1 == al2:
    				L.append((al1, al2))
    			else:
    				L.append((al1,al2))
    				L.append((al2,al1))
    			i= i + 1
    	return L
     
     
    def creer_matrice(taille, arrete):
    	"""int * int-> list[list[int]]
                    Créer une matrice d'adjacence aléatoire d'un graphe non orienté"""
    	mat = [[0] * taille for _ in range(taille)]
    	noeud = creer_noeud(taille, arrete)
    	for i in range(len(noeud)):
    		(x,y)=noeud[i]
    		mat[x][y] = 1
    	return mat
     
    def DFS(mat, src):
    	visite = []
    	DFS_rec(mat, src, visite)
    	return visite
     
    def DFS_rec(mat,src, visite):
    	"""
            Retourne la liste des sommets rencontrés lors
            d'un parcours en profondeur issu du sommet <src>.
     
            Arguments:
            mat -- matrice d'adjacence du graphe
            src -- un sommet du graphe, départ du parcours
     
            >>> DFS([[0, 0, 1, 1, 0], [1, 0, 0, 0, 0], [0, 1, 0, 1, 0], [0, 1, 1, 0, 0], [1, 0, 1, 0, 0]],0)
            {0, 2, 1, 3}
            """
    	visite.append(src)
    	for j in range(0, len(mat)):
    		if j not in visite and mat[src][j] == 1:       
    			DFS_rec(mat, j, visite)
    	return visite
     
     
    def isConnected(mat):
    	"""
            Retourne vrai si le graphe est connexe, faux sinon.
     
            Arguments:
            mat -- matrice d'adjacence du graphe
     
            >>> isConnected([[0, 1, 0], [0, 0, 0], [0, 0, 0]])
            False
     
            >>> isConnected([[0, 1, 0], [0, 0, 1], [0, 0, 0]])
            True
            """
     
    	return (len(DFS(mat, 0)) == len(mat))
     
    def pour_connexe(n, taille, arrete):
    	res=0
    	for i in range(n):
    		if isConnected(creer_matrice(taille, arrete)):
    			res = res + 1
    	return (res * 100)/n 
     
    def liste_connexe(taille, n):
    	R = []
    	for i in range((taille**2)//2):
    		R.append(pour_connexe(n, taille, i))
    #		print(i)
    	return R
     
     
    ###################
     
    def creer_matrice2(taille, arrete):
    	"""Créer une matrice d'adjacence aléatoire d'un graphe non orienté"""
    	mat = np.zeros( (taille,taille), dtype=int)
    	i=0
    	while (i<arrete) :
    		al1=random.randint(0,taille-1)
    		al2=random.randint(0,taille-1)
    		if mat[al1,al2] == 0 :
    			mat[al1,al2] = 1
    			mat[al2,al1] = 1
    			i= i+1
    	return mat
     
    def DFS2(mat,src, visite=None):
    	"""
            Retourne la liste des sommets rencontrés lors
            d'un parcours en profondeur issu du sommet <src>.
     
            Arguments:
            mat -- matrice d'adjacence du graphe
            src -- un sommet du graphe, départ du parcours
     
            >>> DFS([[0, 0, 1, 1, 0], [1, 0, 0, 0, 0], [0, 1, 0, 1, 0], [0, 1, 1, 0, 0], [1, 0, 1, 0, 0]],0)
            {0, 2, 1, 3}
            """
    	if visite is None : visite = []
    	visite.append(src)
    	for j in range(0, len(mat)):
    		if j not in visite and mat[src,j] == 1:      
    			DFS2(mat, j, visite)
    	return visite
     
    def isConnected2(mat):
    	"""
            Retourne vrai si le graphe est connexe, faux sinon.
     
            Arguments:
            mat -- matrice d'adjacence du graphe
     
            >>> isConnected([[0, 1, 0], [0, 0, 0], [0, 0, 0]])
            False
     
            >>> isConnected([[0, 1, 0], [0, 0, 1], [0, 0, 0]])
            True
            """
    	return (len(DFS2(mat, 0)) == len(mat))
     
    def pour_connexe2(n, taille, arrete):
    	res=0
    	for i in range(n):
    		if isConnected2(creer_matrice2(taille, arrete)):
    			res = res + 1
    	return (res * 100)/n 
     
    def liste_connexe2(taille, n):
    	s = (taille**2)//2
    	R = np.zeros(s)
    	for i in range(s):
    		R[i]=pour_connexe2(n, taille, i)
    #		print(i)
    	return R    
     
     
    np.random.seed(0)
    random.seed(0)
     
    t_start = time() 
    res_simu = liste_connexe(10, 3)
    #res_simu = liste_connexe(20, 4)
    #res_simu = liste_connexe(50, 10)
    print("Exectime : %s s"%(time()-t_start))
     
    np.random.seed(0)
    random.seed(0)
     
    t_start = time()
    res_simu2 = liste_connexe2(10, 3)
    #res_simu2 = liste_connexe2(20, 4)
    #res_simu2 = liste_connexe(50, 10)
    print("Exectime : %s s"%(time()-t_start))
     
    #### Pour vérifier que mes résultats sont bien identiques aux tiens
    print("Erreur entre les 2 methodes : "+str(np.sum(res_simu!=res_simu2)))
     
    plt.plot(res_simu)
    plt.title("% de graphe connexe en fonction du nnombre d'arrete")
    plt.ylabel('% de graphe connexe')
    plt.xlabel("nb d'arrete")
    plt.show()
    J'ai remis DFS dans une seule et même fonction (c'est très maladroit d'avoir DFS_rec derriere) ...
    D'autre part je ne suis pas sûr que l'algo que tu utilises ici soit super optimal. Regarde ce qui est fait ici par exemple :

    http://eddmann.com/posts/depth-first...rch-in-python/

  6. #6
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Mai 2017
    Messages
    24
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : Mai 2017
    Messages : 24
    Par défaut
    Merci pour votre réponse rapide t pour ce gain de temps en calcul.
    Je vous remercie énormément cela mets très utile

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [MySQL] Optimisation du code sur les boucles
    Par izguit dans le forum PHP & Base de données
    Réponses: 2
    Dernier message: 07/08/2009, 15h05
  2. faut programme sur les matrices
    Par alouha dans le forum Langage
    Réponses: 1
    Dernier message: 29/04/2008, 09h44
  3. Opérations sur les matrices
    Par mister3957 dans le forum Développement 2D, 3D et Jeux
    Réponses: 2
    Dernier message: 01/11/2007, 23h47
  4. exercice sur les matrices
    Par massimo dans le forum MATLAB
    Réponses: 3
    Dernier message: 22/03/2007, 17h20
  5. Opérations sur les matrices...
    Par aokiseiichiro dans le forum C
    Réponses: 32
    Dernier message: 28/07/2005, 17h10

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo