Contenu | Rechercher | Menus

Annonce

Si vous avez des soucis pour rester connecté, déconnectez-vous puis reconnectez-vous depuis ce lien en cochant la case
Me connecter automatiquement lors de mes prochaines visites.

À propos de l'équipe du forum.

Pages : 1 2

#1 Le 11/03/2016, à 19:10

msg21

RESOLU ET PUBLIE Test d'un code python (SVP)

Bonjour,

N'ayant pas assez de mémoire, quelqu'un peut me tester ce code pour m'afficher les 3 dernières lignes affichés,  et me dire le temps pris pour les afficher, merci

Voici le code :

from scipy import *
import numpy as np	

# Le code de Feynman en langage Python : 
# ecrit par sgh le 13 mars 2016 a 09:28.
# ce code permet de trouver la matrice de Feynman et 
# les cycles hamiltoniens s il existent.

# On definit la fonction F de Feynman.

def F(j, T):
	
	l= len(T)
	U=[l+1]
	U=[0]*(l+1)
	U[0]=T[0]-1
	for i in range(1,l):
		U[i+1]=T[i]
	U[1]=j
	return U
def R(j, T):
	del T[j]
	return T	
	
	

# On construit le Grpahe G de particules :
			

print ("Entrez un entier non nul > 1") 
n= int(input())  



G=np.eye(n,n)

for i in range(n):
	for j in range(n):
		print ("Entrez G(i,j)",i,j) # G(i,j)= 0 si i=j
		G[i][j] = int(input())       

for i in range(n):
	for j in range(n):
		if i==j:
			G[i][j] = 0
		else:
			G[i][j] = 1


	

# On construit la matrice de Feynman au point 0...


d={}

d[0]=[[n,0]]
print d[0]

for j in range(n) :
	if j==0:
		d[0]=[[n,0]]
	else :	
		d[j]=[[0,j]]
	
	
if G[0][j]==1 and 0!=j :
		d[j]=[[n-1,j,0]]
		##print d[j]
else :
				d[j]=[[0,j]]
				##print d[j]

			


L=[]
H=[]
for k in range(0,n**2) : 
	print k 
	print "En cours de la recherche des cycles hamiltoniens..."
 	
 	if k%n==0:
		
		d[0]=[]	
		print "Voici les premiers cycles hamiltoniens...."
		print H		
				
	elif k%n!=0:
				for T in d[k%n]  :
			
					if  len(T)-len(set(T))<2  and T[0]!=0:
							for j in range(n):
								if G[k%n][j]==1 and (k%n)!=j and j!=0 :
											
											if  T[0] > 0 :
												d[j]+=[F(j,T)]
												#print d[j]
											else:
												pass	
								
								if G[k%n][j]==1 and (k%n)!=j  and j==0:
								
															
										for h in d[k%n]:
											if len(h)== n+1  and h[0]==1  and h[n]==0:
												if len(set(F(0,h)))== n :
													#print F(0,h)
													L.append(F(0,h))
													H.append(R(0,F(0,h)))
													#print "Voici les premiers cycles hamiltoniens...."
													#print H
												else:
												    pass				
											else:
												pass
														
								else :
									pass
					else :
							pass	
								
			
				d[k%n]=[]
								
# Matrice de Feynman au point 0
	
print("Matrice de Feynman au point 0 :")

#print L
	
	
# Cycles Hamiltoniens :
	
	
print("Cycles Hamiltoniens :")
#print H

	

# Fin du code

# Fin du code

Dernière modification par msg21 (Le 23/03/2016, à 22:13)

Hors ligne

#2 Le 11/03/2016, à 19:58

Oni_Shadow

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

J'allais te faire cela, mais... c'est du python2, je n'utilise que le 3 (et ne compte pas installer de lib pour 2) sad sorry

Rouillé

Hors ligne

#3 Le 11/03/2016, à 20:03

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Merci quand même

Hors ligne

#4 Le 11/03/2016, à 20:57

grigouille

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Si c'est long à exécuter, utilise plutôt un langage compilé.

Debian (xfce) 12
HP LaserJet M1132 MFP

Hors ligne

#5 Le 11/03/2016, à 21:03

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

grigouille a écrit :

Si c'est long à exécuter, utilise plutôt un langage compilé.

Comment convertir le code ci-dessus en langage C ?

Hors ligne

#6 Le 11/03/2016, à 21:07

grigouille

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Je confirme, c'est hyper long. Le compteur est bloqué à 19 depuis un moment.
S'il faut aller jusqu'à 399, on n'est pas rendu.

La conversion du code en langage C se fait à la main.

Debian (xfce) 12
HP LaserJet M1132 MFP

Hors ligne

#7 Le 11/03/2016, à 21:10

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

grigouille a écrit :

Je confirme, c'est hyper long. Le compteur est bloqué à 19 depuis un moment.
S'il faut aller jusqu'à 399, on n'est pas rendu.

La conversion du code en langage C se fait à la main.

ça n'a rien avec la mémoire ?, vous pensez qu'avec C ça peut aller vite?

Dernière modification par msg21 (Le 11/03/2016, à 21:10)

Hors ligne

#8 Le 11/03/2016, à 21:14

Oni_Shadow

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

convertir en c n'est pas forcement une bonne idée (ni très facile) il me semble. Matlab/octave peut peut-être faire mieux, mais si son soucis c'est la mémoire, dans tout les cas ća restera un probleme.

Rouillé

Hors ligne

#9 Le 11/03/2016, à 21:14

grigouille

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Le C (C++, Fortran, etc) sera forcément plus rapide. Comme ton code n'est pas long, cela vaut la peine d'essayer.

Debian (xfce) 12
HP LaserJet M1132 MFP

Hors ligne

#10 Le 11/03/2016, à 21:16

grigouille

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Oni_Shadow a raison. Si ton programme utilise trop de mémoire, tu mettras par terre n'importe quelle machine.

Debian (xfce) 12
HP LaserJet M1132 MFP

Hors ligne

#11 Le 11/03/2016, à 21:19

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

grigouille a écrit :

Oni_Shadow a raison. Si ton programme utilise trop de mémoire, tu mettras par terre n'importe quelle machine.

Bien que l'algorithme est polynomiale ( un O(n^4)) ?

Hors ligne

#12 Le 11/03/2016, à 21:38

grigouille

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Passage à 20. Mémoire à 3000MB.

Debian (xfce) 12
HP LaserJet M1132 MFP

Hors ligne

#13 Le 11/03/2016, à 22:01

grigouille

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Toujours à 20. Le programme utilise maintenant 70% de la mémoire. Je l'arrête avant que ma machine ne plante.

Debian (xfce) 12
HP LaserJet M1132 MFP

Hors ligne

#14 Le 11/03/2016, à 22:07

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

grigouille a écrit :

Toujours à 20. Le programme utilise maintenant 70% de la mémoire. Je l'arrête avant que ma machine ne plante.

ok merci, c est pareille pour moi

Hors ligne

#15 Le 11/03/2016, à 22:26

pingouinux

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Bonsoir,
J'ai lancé des tests en python3 (après avoir corrigé 2 print). Voici les temps de calcul pour les premières valeurs de n. Le temps de calcul augmente très vite avec n.

n=1
real    0m0.325s
user    0m0.301s
sys     0m0.024s

n=2
real    0m0.326s
user    0m0.273s
sys     0m0.052s

n=3
real    0m0.324s
user    0m0.287s
sys     0m0.036s

n=4
real    0m0.375s
user    0m0.335s
sys     0m0.040s

n=5
real    0m2.450s
user    0m2.354s
sys     0m0.092s

n=6
real    5m16.476s
user    5m13.836s
sys     0m0.679s

n=7
Tourne depuis 45 minutes

Hors ligne

#16 Le 11/03/2016, à 23:45

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

ok, merci à vous tous.

Hors ligne

#17 Le 12/03/2016, à 07:30

pingouinux

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Pour n=20, voici le temps (en secondes) des premières itérations :

  0     0.000153
  1     0.000250
  2     0.000466
  3     0.000936
  4     0.001834
  5     0.004024
  6     0.008477
  7     0.018598
  8     0.033412
  9     0.071505
 10     0.138938
 11     0.301781
 12     0.694713
 13     1.636919
 14     4.345124
 15    14.560653
 16    73.124033
 17   323.555977

J'ai simplifié la fonction F, mais le gain de temps est minime (environ 7 secondes sur l'itération 17).

def F(j, T):
        U=[T[0]-1,j]
        U.extend(T[1:])
        return U

Hors ligne

#18 Le 12/03/2016, à 11:02

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Merci pengouinux. Mais pourquoi ca devient lent?

Hors ligne

#19 Le 12/03/2016, à 13:04

pingouinux

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

msg21 #18 a écrit :

Mais pourquoi ca devient lent?

Déjà, le nombre d'itérations de la boucle la plus interne à celle commençant par

for k in range(0,n**2) : #ici

augmente rapidement avec k.

N'y a-t-il pas une erreur (ou du moins une opération inutile) à la ligne 71 du script que tu montres en #1 ?

                                                d[j]=d[j]

Hors ligne

#20 Le 12/03/2016, à 13:59

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

J essayerai de voir....

Hors ligne

#21 Le 12/03/2016, à 14:27

pingouinux

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Tu calcules i à la ligne 62, et tu ne l'utilises pas dans la boucle.

                i=d[k%n].index(T)

Hors ligne

#22 Le 12/03/2016, à 15:08

grigouille

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Il faudrait avoir la formulation originale du problème pour bien comprendre.

Debian (xfce) 12
HP LaserJet M1132 MFP

Hors ligne

#23 Le 12/03/2016, à 15:56

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

grigouille a écrit :

Il faudrait avoir la formulation originale du problème pour bien comprendre.

Tout a fait, mais le code marche bien pour les petits n

Dernière modification par msg21 (Le 12/03/2016, à 16:05)

Hors ligne

#24 Le 12/03/2016, à 16:07

grigouille

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Il ne fonctionne pas si bien que cela car pour n=10 le programme bloque déjà à l'itération 18.
On est loin de l'itération 99.

Debian (xfce) 12
HP LaserJet M1132 MFP

Hors ligne

#25 Le 12/03/2016, à 17:38

pingouinux

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

msg21 a écrit :

Tout a fait, mais le code marche bien pour les petits n

Oui si petit<=5 (à la rigueur 6) smile

Hors ligne

Pages : 1 2