Discussion :

[eyquem]

Tu peux éliminer la définition de fonction
def matrice_en_liste(Adj,nb_sommet):

et remplacer la ligne

Code :

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

Adj_liste = matrice_en_liste(Adj)

par

Code :

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

Adj_liste = [ [ j for j in xrange(i+1,nb_sommet) if Adj[i][j] ] for i in range(nb_sommet) ]

[hyuga33]

J'ai essayé ton code sur mon programme et je trouve 64.
Avec ma premiére version je trouve 40 en général et dès fois 39.
Que fait zip()?

[hyuga33]

Merci eyquem, je viens de tester et ça marche nickel.
Le fait d'enlever la fonction nous fais gagner quoi exactement?
Je sais pas du tout.
Je pense juste qu'on gagne en taille de programme et en temps de calcul(le temps d'aller chercher la fonction) mais je ne suis qu'au stade de l'hypothése.

[eyquem]

Mon code dans quel message ?

Je crois que mes codes précédents n’ont pas d’intérêt parce que je n’avais pas encore bien compris



zip() -> doc

[hyuga33]

je répondais à josmiley, désolé eyquem.

[eyquem]

Elle nous fait gagner de perdre de la non–anti-complication


Avec moins de lignes on gagne de la lisibilité, de la hauteur de vue sur le code, de la maniabilité du code (quand on a a modifier quelque chose, on a moins de lignes sur lesquelles on doit intervenir).

Et on peut espérer qu’on gagne en vitesse.

[eyquem]

Pas besoin de la ligne

Adj[int(liste2[i])-1][int(liste1[i])-1]=1

puisqu’elle remplit une moitié de la matrice qui est symétrique de l’autre moitié que remplit la première ligne

Adj[int(liste1[i])-1][int(liste2[i])-1]=1

ces deux moitiés étant symétriques par rapport à la diagonale.

Car ensuite la list comprehension de création de Adj_liste comporte xrange(i+1,nb_sommet) pour éviter de comptabiliser des sommets déjà vus. Enfin bref tu comprends .









J’ai fait tourner le code suivant avec le c que tu as donné dans le message #1.

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
# -*- coding: cp1252 -*-
# ==============================================================================
# METHODE RECUIT SIMULE
# ==============================================================================
"""ALGORITHME RECUIT SIMULE"""
__author__  = ""
__version__ = "1.0"
__date__    = " Avril 2010 "
__usage__   = " Mini-Projet."
# ------------------------------------------------------------------------------
from random import randrange, sample, choice, random, randint
from math import log, exp
import time
# ------------------------------------------------------------------------------
def complementaire():
    """renvoie la classe complementaire de c1: c2"""
    c1 = (sample(xrange(nb_sommet),int(nb_sommet/2)))
    c2 = [ i for i in xrange(nb_sommet) if not (i in c1) ]
    c1.sort()
    c2.sort()
    return c1, c2   
# ------------------------------------------------------------------------------
def arete_inter(c):
    """renvoie le poids des arêtes entre c[0] et c[1]"""
    poids = 0
    setC0 = set(c[0])
    setC1 = set(c[1])
    for i in c[0]:
        print '\ni = '+str(i)+'  de c[0]'
        print 'setC1 =',setC1
        print 'Adj[i] =',Adj_liste[i]
        print 'setC1 & set(Adj_liste[i]) =',setC1 & set(Adj_liste[i])        
        poids += len(setC1 & set(Adj_liste[i]))
        print 'poids =',poids
    print '\n'
    for j in c[1]:
        print '\nj = '+str(j)+'  de c[1]'
        print 'setC0 =',setC0
        print 'Adj[j] =',Adj_liste[j]
        print 'setC0 & set(Adj_liste[j]) =',setC0 & set(Adj_liste[j])        
        poids += len(setC0 & set(Adj_liste[j]))
        print 'poids =',poids
    return poids
# ------------------------------------------------------------------------------
def Temp_init(taux_acc,c):
    """renvoie la donnée initiale de température"""
    temp = [ arete_inter(c) for i in range(100) ]
    temp.sort()
    return sum( temp[-1-i] for i in range(20) )/20/log(1./taux_acc)
# ------------------------------------------------------------------------------
def pick_and_drop(c):
    """calcul les voisins de c[0] dans c[1]"""
    c1,c2 = c[0][:],c[1][:]
    n = randint(1,2)
    if (n == 1) and (len(c1)>int(nb_sommet/2)-p):
        a = choice(c1)
        c2.append(a)
        c1.remove(a)
    elif (n == 2) and (len(c2)>int(nb_sommet/2)-p):
        a = choice(c2)
        c1.append(a)
        c2.remove(a)
    else:
        if (len(c1)>int(nb_sommet/2)-p):
            a = choice(c1)
            c2.append(a)
            c1.remove(a)
        else:
            a = choice(c2)
            c1.append(a)
            c2.remove(a)  
    c1.sort()
    c2.sort()
    return c1,c2
# ------------------------------------------------------------------------------
def sweep_and_swap(c):
    """calcul les voisins de c[0] dans c[1]"""
    c1,c2 = [],[]
    c1.extend(c[0])
    c2.extend(c[1])
    temp1 = choice(c1)
    temp2 = choice(c2)
    c1.remove(temp1)
    c2.remove(temp2)
    c1.append(temp2)
    c2.append(temp1)
    c1.sort()
    c2.sort()
    return c1,c2
# -----------------------------------------------------------------------------
 
 
# ==============================================================================                   
def main():
    global nb_sommet, Adj_liste, taux_acc, coef, p, gel, equil_stat
 
    fichier = '20s.txt'#raw_input ("Quel fichier souhaitez-vous utiliser?")
    f = open(fichier,"r")
    donnees = f.read()
    f.close()
    nb = donnees.split()
    nb_sommet,nb_arete = int(nb[0]),int(nb[1])
    print "Le nombre de sommet est "+str(nb_sommet)+" et le nombre d'arêtes est "+str(nb_arete)
    liste1 = nb[2::3]
    liste2 = nb[3::3]
    p=int(nb_sommet*0.01)+1
    Adj = [[0 for j in range(nb_sommet)] for i in range(nb_sommet)]
 
    for i in range(nb_arete):
        #print 'i ='+str(i)+'   '+ str(int(liste1[i])-1)+' / '+str(int(liste2[i])-1)
        Adj[int(liste1[i])-1][int(liste2[i])-1]=1
 
    print '\nlen(Adj) =',len(Adj)
    print 'Adj =\n[ '+',\n  '.join(repr(u) for u in Adj)+' ]'
    Adj_liste = [ [ j for j in xrange(i+1,nb_sommet) if Adj[i][j] ] for i in range(nb_sommet) ]
    print '\nAdj_liste =\n[ '+',\n  '.join(repr(u) for u in Adj_liste)+' ]'
 
 
    c =  ([0, 2, 3, 5, 6, 7, 8, 11, 13, 17], [1, 4, 9, 10, 12, 14, 15, 16, 18, 19])
 
    poids = arete_inter(c)
    print '\n\npoids total =',poids

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
...
....
....
.....
i = 0  de c[0]
setC1 = set([1, 4, 9, 10, 12, 14, 15, 16, 18, 19])
Adj[i] = [1, 2, 5, 6, 8, 10, 14, 16, 17, 18]
setC1 & set(Adj_liste[i]) = set([16, 1, 10, 18, 14])
poids = 5
 
i = 2  de c[0]
setC1 = set([1, 4, 9, 10, 12, 14, 15, 16, 18, 19])
Adj[i] = [3, 4, 5, 6, 7, 9, 14, 16, 17, 18]
setC1 & set(Adj_liste[i]) = set([16, 9, 18, 4, 14])
poids = 10
 
i = 3  de c[0]
setC1 = set([1, 4, 9, 10, 12, 14, 15, 16, 18, 19])
Adj[i] = [4, 5, 11, 15, 16]
setC1 & set(Adj_liste[i]) = set([16, 4, 15])
poids = 13
 
i = 5  de c[0]
setC1 = set([1, 4, 9, 10, 12, 14, 15, 16, 18, 19])
Adj[i] = [8, 10, 14, 15, 16, 17, 18]
setC1 & set(Adj_liste[i]) = set([16, 10, 18, 14, 15])
poids = 18
 
i = 6  de c[0]
setC1 = set([1, 4, 9, 10, 12, 14, 15, 16, 18, 19])
Adj[i] = [7, 9, 11, 12, 13, 15, 16, 17]
setC1 & set(Adj_liste[i]) = set([16, 9, 12, 15])
poids = 22
 
etc etc

Ça a l'air bon non ?

[hyuga33]

c'est bon même je pense, j'ai vérifié avec quelque données que l'on m'a données et dont on connait les résultats.
ça marche nickel.
Merci beaucoup pour l'aide.

[eyquem]

Je m’amuse.


Pas besoin de créer des ensemble dans la fonction arete_inter()
Ceci marche

Code :

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

1
2
3
4
def arete_inter(c0,c1):
    """renvoie le poids des arêtes entre c[0] et c[1]"""
    return  sum( 1 for i in c0 for u in Adj_liste[i] if u in c1 )\
           +sum( 1 for j in c1 for y in Adj_liste[j] if y in c0 )

Je pense qu’on peut laisser ça sous forme de cette fonction a deux parametres




Par contre je sors

c1 = (sample(xrange(nb_sommet),int(nb_sommet/2)))
c2 = [ i for i in xrange(nb_sommet) if not (i in c1) ]
c1.sort()
c2.sort()

de fonction, ce sera plus rapide
j’ai renommé c1,c2 en c0,c1
on passe directement c0,c1 comme arguments à arete_inter(c0,c1)

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
# -*- coding: cp1252 -*-
# ==============================================================================
# METHODE RECUIT SIMULE
# ==============================================================================
"""ALGORITHME RECUIT SIMULE"""
__author__  = ""
__version__ = "1.0"
__date__    = " Avril 2010 "
__usage__   = " Mini-Projet."
# ------------------------------------------------------------------------------
from random import randrange, sample, choice, random, randint
from math import log, exp
import time
 
# ------------------------------------------------------------------------------
def arete_inter(c0,c1):
    """renvoie le poids des arêtes entre c[0] et c[1]"""
    return  sum( 1 for i in c0 for u in Adj_liste[i] if u in c1 )\
           +sum( 1 for j in c1 for y in Adj_liste[j] if y in c0 )
 
# ------------------------------------------------------------------------------
def Temp_init(taux_acc,c):
    """renvoie la donnée initiale de température"""
    temp = [ arete_inter(c) for i in range(100) ]
    temp.sort()
    return sum( temp[-1-i] for i in range(20) )/20/log(1./taux_acc)
# ------------------------------------------------------------------------------
def pick_and_drop(c):
    """calcul les voisins de c[0] dans c[1]"""
    c1,c2 = c[0][:],c[1][:]
    n = randint(1,2)
    if (n == 1) and (len(c1)>int(nb_sommet/2)-p):
        a = choice(c1)
        c2.append(a)
        c1.remove(a)
    elif (n == 2) and (len(c2)>int(nb_sommet/2)-p):
        a = choice(c2)
        c1.append(a)
        c2.remove(a)
    else:
        if (len(c1)>int(nb_sommet/2)-p):
            a = choice(c1)
            c2.append(a)
            c1.remove(a)
        else:
            a = choice(c2)
            c1.append(a)
            c2.remove(a)  
    c1.sort()
    c2.sort()
    return c1,c2
# ------------------------------------------------------------------------------
def sweep_and_swap(c):
    """calcul les voisins de c[0] dans c[1]"""
    c1,c2 = [],[]
    c1.extend(c[0])
    c2.extend(c[1])
    temp1 = choice(c1)
    temp2 = choice(c2)
    c1.remove(temp1)
    c2.remove(temp2)
    c1.append(temp2)
    c2.append(temp1)
    c1.sort()
    c2.sort()
    return c1,c2
# -----------------------------------------------------------------------------
 
 
# ==============================================================================                   
def main():
    global nb_sommet, Adj_liste, taux_acc, coef, p, gel, equil_stat
 
    fichier = '20s.txt'#raw_input ("Quel fichier souhaitez-vous utiliser?")
    f = open(fichier,"r")
    donnees = f.read()
    f.close()
    nb = donnees.split()
    nb_sommet,nb_arete = int(nb[0]),int(nb[1])
    print "Le nombre de sommet est "+str(nb_sommet)+" et le nombre d'arêtes est "+str(nb_arete)
    liste1 = nb[2::3]
    liste2 = nb[3::3]
    p=int(nb_sommet*0.01)+1
    Adj = [[0 for j in range(nb_sommet)] for i in range(nb_sommet)]
 
    for i in range(nb_arete):
        #print 'i ='+str(i)+'   '+ str(int(liste1[i])-1)+' / '+str(int(liste2[i])-1)
        Adj[int(liste1[i])-1][int(liste2[i])-1]=1
 
    #print '\nlen(Adj) =',len(Adj)
    #print 'Adj =\n[ '+',\n  '.join(repr(u) for u in Adj)+' ]'
    Adj_liste = [ [ j for j in xrange(i+1,nb_sommet) if Adj[i][j] ] for i in range(nb_sommet) ]
    print '\nAdj_liste =\n[ '+',\n  '.join(repr(u) for u in Adj_liste)+' ]'
 
 
    c =  ([0, 2, 3, 5, 6, 7, 8, 11, 13, 17], [1, 4, 9, 10, 12, 14, 15, 16, 18, 19])
 
    poids = arete_inter(c[0],c[1])
    print '\n\npoids total sur exemple du message #1 =',poids
 
    c0 = (sample(xrange(nb_sommet),int(nb_sommet/2)))
    c1 = [ i for i in xrange(nb_sommet) if not (i in c0) ]
    c0.sort()
    c1.sort()
    print '\n(c0,c1) au hasard =',(c0,c1)
    poids = arete_inter(c0,c1)
    print '\n\npoids total sur (c0,c1) hasard =',poids

[josmiley]

eyquem,
tu peux expliquer ce qu'il fallait faire ?

[dividee]

Ce que je comprends du problème de hyuga33, c'est qu'il cherche la bisection des sommets d'un graphe (la partition en 2 parties de même cardinalité) qui minimise le nombre d'arêtes qui traversent d'une partie à l'autre. Cela semble être une variante du problème de "coupe minimale", et je suppose qu'on peut dire qu'il s'agit de trouver une "coupe minimale balancée" mais je ne trouves pas de référence directe à ce problème sur le web. Peut-être huyga33 peut nous éclairer sur ses applications ?

Je vois plusieurs opportunités d'optimisations importantes, dans la boucle principale:

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
        while gel>0:
            k = 0
            while k<equil_stat:
                k += 1
                Ncourante = pick_and_drop(courante)
                delta = arete_inter(Ncourante) - arete_inter(courante)
                if delta<0:
                    courante = Ncourante
                    if arete_inter(Ncourante)<poids:
                        poids = arete_inter(Ncourante)
                        solution = Ncourante
                else:
                    a = random()
                    if a<=exp(-delta/t):
                        courante = Ncourante
            t = t*coef
            gel -= 1

Je prends ici la boucle du "pick and drop" mais le même raisonnement s'applique pour le "sweep and swap".
La fonction arete_inter compte très certainement pour la majorité du temps d'exécution, surtout sur de grands graphes. arete_inter(Ncourante) est appelée jusque 3 fois par boucle, une seule fois suffirait.
arete_inter(courante) a déjà été calculé lors d'une itération précédente, on peut donc aussi éviter cet appel.

Cela donne (code non testé):

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
        poids_old = arete_inter(courante)
        while gel>0:
            k = 0
            while k<equil_stat:
                k += 1
                Ncourante = pick_and_drop(courante)
                poids_new = arete_inter(Ncourante)
                delta = poids_new - poids_old
                if delta<0:
                    courante = Ncourante
                    poids_old = poids_new
                    if poids_new < poids:
                        poids = poids_new
                        solution = Ncourante
                else:
                    a = random()
                    if a<=exp(-delta/t):
                        courante = Ncourante
                        poids_old = poids_new
            t = t*coef
            gel -= 1

Je considère ici ce morceau de code en isolation mais un nettoyage de tout le code de main() serait bienvenu...

Pour aller plus loin, pick_and_drop se contente de déplacer un seul sommet d'une partie dans l'autre. Au lieu de recalculer le poids de la partition à chaque fois à partir de rien, on peut remarquer que puisqu'un seul sommet change de côté, seules les arêtes contenant ce sommet peuvent changer de statut (traverser d'une partie à l'autre de la partition ou non). On pourrait donc calculer le delta en n'examinant que ces arêtes-là. Cela nécessite un peu plus de modifications au code que les autres optimisations ci-dessus, mais la différence sera énorme sur de grands graphes.

[EDIT]: Ah voilà: ce problème s'appelle "Minimum Graph Bisection" et est décrit notamment ici: http://tracer.lcc.uma.es/problems/bisect/bisect.htm. Cela aurait été plus simple si hyuga33 nous avait parlé de ça depuis le début...

[hyuga33]

C'est vrai que j'aurai du donner les références de suite..mais j'en n'avais aucune sur internet pour ce problème.
Je vais essayer de travailler sur le delta.

[eyquem]

Remarques fort pertinentes , dividee, comme très souvent. En voyant que tu avais posté , j’ai pensé que ton œil sagace avait vu une autre amélioration à faire dans le début du code, où j’en suis resté. Mais tu as amélioré le cœur du programme, c’est mieux.

J’ai à poster, mais pas le temps.

À+

[miawaw]

Salut tout le monde
J'ai d'abord repensé à la fonction arete_inter. Parmi les fonctions suivantes,

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
def eyquem():
    """renvoie le poids des arêtes entre c[0] et c[1]"""
    return  sum( 1 for i in c[0] for u in Adj_liste[i] if u in c[1] )\
           +sum( 1 for j in c[1] for y in Adj_liste[j] if y in c[0] )
 
def hyuga(c)
    poids = 0
    setC1 = set(c[1])
    setC0 = set(c[0])
    for i in c[0]:        
        poids += len(setC1 & set(Adj_liste[i]))
    for j in c[1]:
        poids += len(setC0 & set(Adj_liste[j]))
    return poids
 
from itertools import product
def miawaw(c):
    return len([1 for a,b in product(c[0],c[1]) if Adj[a][b]])

c'est miawaw qui est le plus rapide. Pour donner une idée, sur la matrice 19x19, donnée au début,
eyquem: 0.000103 = 1e-4
hyuga: 0.000085 = 8.5e-5
miawaw: 0.000052 = 5.2e-5
Remarque: j'ai utilisé la matrice d'adjacence, pas Adj_Liste. A mon avis, c'est plus rapide parce qu'on ne s'intéresse qu'aux bonnes entrées de la matrice Adj. (On peut jeter la liste Adj_liste au bac à mon humble avis)

Changement préliminaire
Ecrire des boucles for plutot que des boulces while:

Code :

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

1
2
3
for gelV in range(gel,0,-1):
        for k in range(equil_stat):
...

Essayons d'optimiser la fonction main()

J'ai tenu compte des bonnes remarques de dividee.

Je ne regarde pour commencer que de la partie qui suit 'if choix == '1'.

Bon, alors je vois deux boucles presque identiques.
Pour écrire moins de code, je pense à faire ça :

Code :

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

FonctionChoix = [pick_and_drop, sweep_and_swap][int(choix) - 1]

Ensuite, on n'écrit qu'une seule boucle. Les lignes concernées par le changement sont, d'abord

Code :

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

1
2
3
Ncourante = pick_and_drop(courante) # première boucle
#et
Ncourante = sweep_and_swap(courante) #deuxième boucle.

Dans l'unique boucle on écrit Ncourante = FonctionChoix(courante).

Il reste une adaptation à faire. Les conditions

Code :

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

1
2
3
if arete_inter(Ncourante)<arete_inter(solution):
#et
if arete_inter(Ncourante)<poids:

sont un peu différentes car dans l'une on appelle une fonction, dans l'autre on regarde la valeur de la variable poids. Idée:

Code :

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

1
2
3
4
5
def get_poids(a):
        return poids
 
FonctionCondition = [arete_inter, get_poids][int_choix - 1]
# ou bien: FonctionCondition = [arete_inter, lambda x: poids][int_choix - 1]

Concernant la remarque juste de dividee sur le fait de ne pas calculer le poids actuel par l'appel de la methode arete_inter mais en regardant uniquement les sommets qui changent de groupe, j'ai essayé, mais me suis rendu compte qu'il fallait modifier les methodes sweep_swap et prick_... pour qu'elles renvoyent les éléments qui doivent changer d'ensemble. Faire le changement et le calcul du nouveau poids dans une petite fonction, par exemple.
@+

[dividee]

Remarque: j'ai utilisé la matrice d'adjacence, pas Adj_Liste. A mon avis, c'est plus rapide parce qu'on ne s'intéresse qu'aux bonnes entrées de la matrice Adj. (On peut jeter la liste Adj_liste au bac à mon humble avis)

Hum... Bonne chance quand tu auras à traiter un graphe de 100 000 sommets, avec la matrice d'adjacence contenant 10 000 000 000 éléments...

Il faut savoir que beaucoup de grands graphes que l'on a à traiter en pratique sont en fait peu denses, ce qui veut dire qu'il y a peu d'arêtes par rapport au (carré du) nombre de sommets. Par exemple il n'y aura que 1 éléments sur 10 000 de la matrice d'adjacence qui sera différent de 0. Là tu conviendras que la matrice d'adjacence, tu peux la jeter au bac, je pense


Le code de création du graphe ne convient pas en l'état pour de grands graphes. Pas besoin de passer par la matrice d'adjacence pour créer la liste d'adjacence. Et il vaut mieux éviter de lire le fichier en mémoire en entier (mais c'est moins important, après tout, même pour un graphe de 10^6 arêtes le fichier ne fera que quelques Mo).

[miawaw]

ok

[eyquem]

Rappels

* Dans le message #25 (page 2) , il y a un code entier avec

- la création suivante de la matrice Adj:

Code :

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

1
2
3
4
    Adj = [[0 for j in range(nb_sommet)] for i in range(nb_sommet)]
    for i in range(nb_arete):
        Adj[int(liste1[i])-1][int(liste2[i])-1]=1
        Adj[int(liste2[i])-1][int(liste1[i])-1]=1

- et la fonction matrice_en_liste(Adj)
servant à créer Adj_liste à partir de la matrice Adj.




* Dans le message #41 (page 3) , j’ai proposé de remplacer la fonction matrice_en_liste(Adj) par l’expression

Code :

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

Adj_liste = [ [ j for j in xrange(i+1,nb_sommet) if Adj[i][j] ] for i in range(nb_sommet) ]

* Dans le message #47 (page 3), j’ai signalé que comme conséquence de ce remplacement par une expression dans laquelle il y a xrange(i+1,nb_sommet) , la ligne Adj[int(liste2[i])-1][int(liste1[i])-1]=1 n’était plus nécessaire dans la création de la matrice Adj.





1)

Mais l’élimination de la fonction matrice_en_liste(Adj) ne suffit pas, il faut aussi améliorer en amont la création de la matrice Adj ; au lieu de créer une matrice pleine de zéros dans laquelle on remplace ensuite certains zéros par des chiffres 1 en fonction des liens de sommets exprimés dans le fichier, on fait directement:

Code :

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

1
2
    Adj= [ [1 if [aa+1,bb+1] in liste else 0 for bb in xrange(nb_sommet) ]
           for aa in xrange(nb_sommet) ]

qui doit encore être suivie de

Code :

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

Adj_liste = [ [ j for j in xrange(i+1,nb_sommet) if Adj[i][j] ] for i in range(nb_sommet) ]

2)

On s’aperçoit alors (bienfait de la clarté des codes Python) qu’on peut raccourcir les choses pour obtenir directement Adj_liste sans devoir passer par une matrice Adj:
comme Adj[i][j] a été mis à 1 dans la matrice pour [i+1, j+1] présent dans liste, les deux expressions peuvent être condensées en une seule :

Code :

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

1
2
Adj_liste = [ [j for j in xrange(i+1,nb_sommet) if [i+1, j+1] in liste ]
               for i in xrange(nb_sommet) ]

Remarque:

L’indice “i+1“ des départs des itérateurs xrange(i+1, nb_sommet) provient de la condition and (j not in v) dans la fonction matrice_en_liste(Adj).

Cet indice de départ, tout comme la condition qui en est à l’origine dans la fonction, ont pour conséquence que chaque sous-liste d’indice i de la liste Adj-liste ne contient que des sommets supérieurs à i.

----- EDIT ----- Passage édité car il était incompréhensible —--- :
Dès lors, ainsi que je l’ai rappelé plus haut, il était inutile de remplir de chiffres 1 la moitié de la matrice Adj se trouvant en bas à gauche ( au dessous de la diagonale haut-gauche -> bas-droit de la matrice ) au moyen de la ligne Adj[int(liste2[i])-1][int(liste1[i])-1]=1
Car c’est cette moitié (bas-gauche) de la matrice Adj qui, quand elle contient des 1, permet d’ajouter des sommets inférieurs à l’indice i d’une sous-liste de Adj-liste .

J’écris “était“ car depuis le 2) ci dessus, je considère que la matrice Adj n’est plus nécessaire; on peut obtenir Adj_liste directement à partir des données.
-----

Alors je suis perplexe.

* La présence de la ligne Adj[int(liste2[i])-1][int(liste1[i])-1]=1 dans la création de Adj est elle voulue et correspond elle à la nécessité de grouper dans la liste des sommets liés à un sommet i même ceux qui sont inférieurs à i ?
Auquel cas la condition and (j not in v) dans les premiers codes serait une erreur d’algorithme (?)
Et le code manipulé jusqu’à présent serait donc faux.


* Ou alors est-ce cette ligne qui est une erreur ?
Auquel cas, que faut il comprendre de la volonté de ne prendre pour sommets liés à un sommet i que ceux qui lui sont supérieurs ?



Remarque supplémentaire:

Si on examine les données présentes dans le fichier 20s.txt, on s’aperçoit que ces donnéees sont telles qu’il n’y a pas de sommets liés (2ième colonne) à un sommet i (première colonne) qui soient inférieurs à i.
Soit dit en passant, cette structuration des données rend stériles la ligne Adj[int(liste2[i])-1][int(liste1[i])-1]=1 dans les premiers codes et les réflexions sur l’intérêt de sa présence ou non dans un code.

Cela résulte-t-il de la façon d’obtenir ou de mettre en forme ces données en amont , sans qu’il y ait une signification particulière attachée à ce fait ?
----- EDIT (En relisant, je me comprends mieux. ) :Ce que je veux dire par là, c’est que cette structuration des données dans le fichier serait la façon la plus condensée de les écrire, sans redondance qui poserait ensuite des problèmes pour leur exploitation. Étant entendu que le programme les utilisant devra ensuite faire en sorte que pour une ligne ’3 12 1\n’ , par exemple, il soit considéré que 12 est lié à 3 donc 12 présent dans la liste des sommets liés à 3, ET symétriquement que 3 est lié à 12 donc placé dans la liste des sommets liés à 12.
«Sans signification particulière» voulant donc dire que cette dissymétrie des données n’aurait qu’une importance de présentation et non pas une signification du type de celle qui suit au paragraphe suivant.
-----


Ou bien cette organisation des données représente-t-elle une caractéristique de l’ensemble de sommets, c’est à dire en amont, une caractéristique du sytème modélisé par ces sommets ? Cette dissymétrie des données me donne à penser que les liaisons entre sommets sont orientés: une flèche de 7 vers 18 mais pas de 18 vers 7.
----- EDIT:
En effet, c’est la présence de la ligne Adj[int(liste2[i])-1][int(liste1[i])-1]=1 dans les premiers codes qui rend possible la présence de sommets liés inférieurs à un sommet donné; et cette ligne remplit la moitie bas-gauche de la matrice Adj avec des 1, ce qui correspond manifestement à enregistrer l’existence d’une liaison de j à i quand il y en a une de i à j, c’est à dire une lisison dans les deux sens.
-----
Je pense que cette dissymétrie pourrait représenter une anistropie du milieu modélisé par exemple.



En tous cas il me semble nécessaire de clarifier ces points de base avant de s’engager plus loin vers l’optimisation.

[dividee]

Cela résulte-t-il de la façon d’obtenir ou de mettre en forme ces données en amont , sans qu’il y ait une signification particulière attachée à ce fait ?

Ou bien cette organisation des données représente-t-elle une caractéristique de l’ensemble de sommets, c’est à dire en amont, une caractéristique du sytème modélisé par ces sommets ? Cette disymétrie des données me donne à penser que les liaisons entre sommets sont orientés: une flèche de 7 vers 18 mais pas de 18 vers 7. je pense que cette disymétrie pourrait représenter une anistropie du milieu modélisé par exemple.

Au contraire, ce que tu appelles "dissymétrie" est simplement une exploitation de la symétrie de la matrice d'adjacence d'un graphe non-orienté. Comme c'est symétrique, on n'enregistre que la moitié des données.

Mais je ne comprends pas pourquoi vous vous escrimez à passer par un algo en O(nb_sommets²) pour construire Adj_liste alors qu'on peut la construire directement depuis le fichier:

Code :

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

1
2
3
4
5
6
7
    with open(fname) as f:
        nb_sommets, nb_aretes = map(int,f.readline().split())
        adj_list =[[] for _ in xrange(nb_sommets)]
        for line in f:
            i,j,_ = map(int, line.split())
            adj_list[i-1].append(j-1)
            adj_list[j-1].append(i-1)

Ceci est O(nb_aretes), et dans un graphe épars on a nb_aretes << nb_sommets². Pour la même raison, oubliez la matrice Adj pour de grand graphes...

Je sais que ce n'est pas le cas dans "20s.txt", mais comme le PO a parlé de graphes de 10 000 sommets, j'imagine mal que ces graphes-là soient denses...

[eyquem]

J’ai édité mon message précédent parce qu’il n’était vraiment pas clair en plusieurs passages. Il ressort ainsi mieux que je suis d’accord ou comprends bien ce que tu dis, dividee:

Au contraire, ce que tu appelles "dissymétrie" est simplement une exploitation de la symétrie de la matrice d'adjacence d'un graphe non-orienté. Comme c'est symétrique, on n'enregistre que la moitié des données.

OK.

1) Tu réponds donc yes à la première option de mon interrogation:

Cela résulte-t-il de la façon d’obtenir ou de mettre en forme ces données en amont, sans qu’il y ait une signification particulière attachée à ce fait ?

Je comprends qu'étant donné qu’on peut utiliser la symétrie de la matrice lors de l’inscription, dans cette matrice, de l’information contenue dans les données, on peut se permettre de n’avoir dans le fichier que des données réduites au strict minimum nécessaire.
Et que ce qui détermine si un graphe est orienté ou non, c’est la façon dont on remplit la matrice d’adjacence (càd les deux moitiés ou une seule) et non pas la structuration sous laquelle se présentent les données dans un fichier.

2) J'en déduis aussi que tu considères que la présence de la condition and (j not in v): dans les premiers codes est une erreur. Confirmation par ton code qui produit une adj_list dans laquelle chaque sous-liste d'index i contient aussi des sommets inférieurs à l'index i.






Pour ma part, j'ai voulu prendre les choses dans l’ordre, c’est ce qui fait que j’en suis encore à batailler avec la matrice Adj et la liste Adj_liste, alors que les instructions qui les concernent ne sont exécutées qu’une seule fois, contrairement au cœur du programme auquel tu t’es intéressé en premier. Mais je n’ai pas pu poster avant.

Il me semblait intéressant aussi de montrer de quelle manière, en partant du code initial, on peut le modifier progressivement, en bénéficiant de l’avantage que procure la lisibilité du code Python, pour parvenir à l’objectif qu’on distingue à l’avance. C'est sans doute ce qui a osbcurci ce que j’ai voulu pointer dans le message précédent.

Car je ne tiens pas à garder le passage par la matrice Adj dans l’algorithme. Je suis au contraire bien d’accord avec toi: il faut l’éliminer. C’est bien pourquoi j’avais déjà cherché à raccourcir la création de Adj_liste et étais parvenu à l’instruction que j’ai mise en 2) dans le message précédent.






Tout ceci étant dit, je suis satisfait d'avoir réussi à trouver de mon coté, avant que tu postes, la même façon de lire le fichier que toi. Les précédentes que j’avais utilisées ne me plaisaient pas mais je n’arrivais pas à trouver le truc.
Il faut évidemment lire d’abord la première ligne avec un readline() , puis exploiter le reste du fichier avec un read() ou un readlines() ou, encore mieux, en mettant à profit le caractère d’itérateur de l’objet-ficher. Cela évite des jeux d’indices sur nb et autres machins.
Je me suis acharné à pousser jusqu’au bout l’idée de recourir à des processus d’itérateurs et j’ai fini par trouver ceci:

Code :

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

1
2
3
4
5
with open(fichier,"r") as f:
    nb_sommet,nb_arete = map(int,f.readline().split())
    liste_aretes = [ (int(x)-1,int(y)-1) for x,y,_ in (line.split() for line in f) ]
    Adj_liste = [ [ y for y in xrange(nb_sommet) if (x,y) in liste ]
                       for x in xrange(nb_sommet) ]

Pour ce qui est de la création de liste_aretes:

line for line in f est la lecture itérative du fichier, c'est à dire par activation de la méthode next() de f (c'est bien ça ?)
(line.split() for line in f) est un processus à la volée: la ligne lue est immédiatement transformée en liste par split()
for x,y,_ in (line.split() for line in f) est la poursuite du processus à la volée: la ligne splitée est dépaquetée immédiatement dans un triplet
(int(x)-1,int(y)-1) for x,y,_ in (line.split() for line in f) : c'est à la volée toujours, du fait que c'est une list comprehension: les valeurs du triplet obtenu sont immédiatement utilisées pour agréger un couple à la liste en cours de construction.

De la lecture d’une ligne à l’enregistrement en liste, c’est ainsi un seul processus à la volée, c'est à dire, tel que je le comprends, qu’entre la lecture d’une ligne et l’inscription dans liste_aretes, il n’y a pas d’objet ayant une existence (en mémoire) séparée de la liste construite, durant ne serait ce qu’un court instant: les données contenues dans une ligne lue passent immédiatement dans un tuyau qui les amène directement à être collées à la bonne place dans la zone mémoire dédiée à liste_aretes.





L'ennui est que cette manière comporte encore le passage par liste_aretes, un objet tout ce qu’il y a d’établi et référencé en mémoire. Je pensais bien qu'il devait être possible de s’en passer. Le code de dividee l’a fait avant moi. J’avais une autre idée, mais elle ne marche pas, le code de dividee est la manière la plus simple de faire, je pense.

J’apporterais juste deux petites modifications:

- faire délivrer les données d’une ligne par une expression génératrice: cela évite de passer par un objet line individualisé, ce qui fait donc du passage des données d’une ligne à x,y,_ un processus à la volée (tel que je comprends les choses)

- conférer à adj_list une taille de nb_sommets + 1 de façon à mettre dans la sous-liste d’index i les sommets liés au sommet i, et non plus dans la sous-liste d’index i-1.
Si les sommets sont numérotés à partir de 1, la première sous-liste reste vide. S’ils sont numérotés à partir de 0, c’est la dernière sous-liste qui va rester vide.
Une sous-liste restant vide, ce n’est pas ça qui va peser. L'intérêt étant que cela évite des soustractions de 1 tant pour les index que pour les noms des sommets.

Code :

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

1
2
3
4
5
6
with open('20s.txt') as f:
    nb_sommets, nb_aretes = map(int,f.readline().split())
    adj_list =[[] for _ in xrange(nb_sommets+1)]
    for i,j,_ in ( map(int,line.split()) for line in f ):
        adj_list[i].append(j)
        adj_list[j].append(i)

J'ai testé différentes solutions:

code dividee tref

Code :

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

1
2
3
4
5
adj_list =[[] for _ in xrange(nb_sommets)]
for line in f:
    i,j,_ = map(int, line.split())
    adj_list[i-1].append(j-1)
    adj_list[j-1].append(i-1)

code avec generateur, map(int,...) et i-1,j-1 99,6 % de tref

Code :

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

1
2
3
4
adj_list =[[] for _ in xrange(nb_sommets)]
for i,j,_ in ( map(int,line.split()) for line in f ):
    adj_list[i-1].append(j-1)
    adj_list[j-1].append(i-1)

code avec generateur, map(int,...) et i,j 97,7 % de tref

Code :

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

1
2
3
4
adj_list =[[] for _ in xrange(nb_sommets+1)]
for i,j,_ in ( map(int,line.split()) for line in f ):
    adj_list[i].append(j)
    adj_list[j].append(i)

99,6 % et 97,7 % c’est rien comme différence, je n’y accorde pas plus d’importance que celle d’indiquer que le gain en concision de code ne s’accompagne pas d’un temps d’exécution plus élevé.

Ainsi si on n'utilise pas map(int,...) , le temps est plus long, même avec une itération dans un générateur et usage de i,j , et il est mieux de pouvoir s'en apercevoir par un test:
112,5 % de tref pour

Code :

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

1
2
3
4
adj_list =[[] for _ in xrange(nb_sommets+1)]
for i,j,_ in ( line.split() for line in f ):
    adj_list[int(i)].append(int(j))
    adj_list[int(j)].append(int(i))

-----------------------------------------------------------------------




Bon. Tout ceci fait avancer les choses, mais n’est pas encore le mieux, il faut pousser les choses plus loin.

Dans le code, la ligne adj_list =[[] for _ in xrange(nb_sommets)] est dérangeante, elle traduit la nécessité d’organiser la liste adj_list avant de commencer à la remplir. Ce qu'il y a de gênant est lié au principe de adj_list: repérer les sommets adjacents d’un sommet i par une sous-liste située à l’index i.

En y réfléchissant quelques secondes, on sent bien que cette démarche n’est pas terrible. En fait, une liste n’est pas la meilleure structure de données pour faire catalogue des sommets adjacents.
C’est ce que je croyais te voir signaler, dividee, quand j’ai aperçu l’autre soir ton message dans la liste des files.

Je ne vais pas m’étendre, il faut bien que hyuga cherche un peu quelle autre structure de données est à privilégier.

[dividee]

Et que ce qui détermine si un graphe est orienté ou non, c’est la façon dont on remplit la matrice d’adjacence (càd les deux moitiés ou une seule) et non pas la structuration sous laquelle se présentent les données dans un fichier.

Euh... La matrice d'adjacence est symétrique si le graphe est non-orienté. Cela ne veut pas dire qu'elle ne doit être qu'à moitié remplie. On peut choisir de ne stocker en mémoire, comme dans le fichier, que la moitié de la matrice, cela fait gagner de la mémoire. Mais cela va en général ralentir l'algorithme, vu que pour tester si un arc existe il faudra utiliser soit (i,j) soit (j,i) suivant que i>=j, ce qui ajoute un test qui devra sans doute se faire dans la boucle interne. C'est donc un choix à faire entre réduire l'utilisation mémoire ou accélérer le code.

Pour la représentation sous forme de listes de voisins (adj_liste), le même choix se pose, mais ici un choix est plus judicieux que l'autre: si on ne stocke que les voisins j de i tels que j > i, alors pour trouver par exemple quels sont tous les voisins de i, au lieu de seulement examiner adj_liste[i], on sera obligé de chercher dans tout adj_liste. A éviter donc.

line for line in f est la lecture itérative du fichier, c'est à dire par activation de la méthode next() de f (c'est bien ça ?)

Oui. Je trouve ça élégant et efficace et je préfère utiliser l'itération sur un file object quand c'est possible.

- faire délivrer les données d’une ligne par une expression génératrice: cela évite de passer par un objet line individualisé, ce qui fait donc du passage des données d’une ligne à x,y,_ un processus à la volée (tel que je comprends les choses)

Dans le code donné ensuite, à mon sens l'objet "line" apparait toujours, même si c'est dans une list comprehension, ça ne change rien. Itérer dans une list comprehension plutôt que dans une boucle "for" est légèrement plus efficace, comme tu l'as mesuré, mais la différence est tellement insignifiante dans ce cas-ci que je préfère garder la boucle explicite que je trouve plus facile à lire.

- conférer à adj_list une taille de nb_sommets + 1 de façon à mettre dans la sous-liste d’index i les sommets liés au sommet i, et non plus dans la sous-liste d’index i-1.
Si les sommets sont numérotés à partir de 1, la première sous-liste reste vide. S’ils sont numérotés à partir de 0, c’est la dernière sous-liste qui va rester vide.
Une sous-liste restant vide, ce n’est pas ça qui va peser. L'intérêt étant que cela évite des soustractions de 1 tant pour les index que pour les noms des sommets.

Je préfère que mes listes commencent à l'indice 0 Les goûts et les couleurs...

En langage C, par exemple, je le ferais peut-être, car pour itérer sur un tableau en C il faut de toute façon passer par les indices et écrire for(i=0;i<nb_sommets;i++) ou for (i=1;i<=nb_sommets;i++) revient au même. Mais comme en Python le "for" est en fait un "foreach", c'est moins pratique.

for e in liste traitera la liste vide; il vaut vérifier que ça ne perturbe pas l'algo
for e in liste[1:] copie la liste, très mauvais.
for i in xrange(1, len(liste)) bof bof bof... pq itérer sur les indices si on n'en a pas besoin.

Dans le code, la ligne adj_list =[[] for _ in xrange(nb_sommets)] est dérangeante, elle traduit la nécessité d’organiser la liste adj_list avant de commencer à la remplir. Ce qu'il y a de gênant est lié au principe de adj_list: repérer les sommets adjacents d’un sommet i par une sous-liste située à l’index i.

En y réfléchissant quelques secondes, on sent bien que cette démarche n’est pas terrible. En fait, une liste n’est pas la meilleure structure de données pour faire catalogue des sommets adjacents.
C’est ce que je croyais te voir signaler, dividee, quand j’ai aperçu l’autre soir ton message dans la liste des files.

Je ne suis pas certain que pour l'algo dont il est question on y gagne quelque chose à utiliser une autre structure de données.

Pourquoi une liste et pas un dictionnaire ? Les sommets sont déjà numérotés de 1 à nb_sommets. Ce n'est pas dit explicitement, mais le format du fichier le laisse supposer. On n'a donc rien à y gagner à utiliser un dictionnaire. A part peut-être éviter le débat sur le "- 1" et l'initialisation de la liste. Mais l'overhead d'un dictionnaire est supérieur, et cela peut même compliquer les choses dans certains cas. Si par exemple un sommet n'a pas de voisins, il ne sera pas dans le dictionnaire, mais si on itère sur les sommets (s), écrire adj_dico[s] lèvera une exception et on devra écrire adj_dico.get(s) par exemple.

Pourquoi une liste de listes et pas une liste d'ensembles (sets) ?
Effectivement, c'est probablement une liste d'ensembles que j'aurais utilisé à priori, mais cela dépend de la façon dont on écrit l'algo. Si on n'a besoin que d'itérer sur ces ensembles, on ne gagne rien. Si on doit tester l'appartenance d'un sommet à l'ensemble, là on va gagner énormément. Pour l'algo qui nous occupe, il est sans doute plus efficace d'itérer sur les voisins et de tester l'appartenance à l'une ou l'autre partition (qui elles gagnent à être des ensembles, mais ça tu l'as déjà fait) que de faire l'inverse. Donc garder la liste de listes est un choix tout à fait valable.