Alléger le code

**LabChNe** · 10/11/2010, 09h44

Bonjour,
Je reviens à vous, de nouveau, pour une demande concernant python.
Je suis très débutant, donc je suis ouvert à toutes suggéstions et remarques.
J'ai développé quelque chose sous python 2.5 en important psyco pour augmenter la vitesse d'exécution mais l'exécution est très lente.
Je crois qu'en allégeant le code, l'exécution peut être axélérée.
Le code est le suivant:

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
from math import sqrt
from array import array
import psyco
psyco.full()
def isprime(n):
    if n==1:
        return False
    else:
        if n<4:
                return True
        elif n%2==0:
                return False
        elif n<9:
            return True
        elif n%3==0:
            return False
        else:
            r=int(sqrt(n))
            f=5
            while f<=r:
                if n%f==0:
                    return False
                    break
                elif n%(f+2)==0:
                    return False
                    break
                else:
                    f+=6
            return True
 
tableau=array('i')
c=0
i=2
while c<=10000:
    if isprime(i):
        tableau.insert(c+1,i)
        c+=1
    i+=1
 
facto3=[[0,0,0,-1,0,-1,1,0,0,0],
        [1,1,-1,0,0,1,-1,0,0,0],
        [0,-1,0,0,0,0,-1,1,0,0],
        [-1,0,0,0,0,0,0,-1,1,0],
        [0,-1,0,0,-1,0,0,0,0,1],
        [0,0,0,1,1,0,0,0,0,-1],
        [0,0,1,0,0,0,0,1,-1,0],
        [0,0,0,1,1,0,0,-1,0,0],
        [0,0,0,0,0,0,-1,0,0,0],
        [0,0,0,0,1,-1,0,0,0,0],
        [0,0,0,0,-1,1,0,0,0,0],
        [-1,1,1,0,0,0,0,0,0,0],
        [0,0,0,-1,0,0,0,0,0,0],
        [0,0,1,0,1,0,0,0,0,0]]
 
var1=[1,0,0,0,0,0,0,0,0,0]
print var1
c=2
k=0
cont=0
while k<=100:
    cont+=1
    for i in range(0,14,1):
        f1=[m+n for m,n in zip(var1,facto3[i])]
        if min(f1)>=0:
            var1=f1
            if var1[1:10].count(0)==9 and var1[0]==tableau[k]:
                print str(cont) + ' : ' + str(var1[0])
                k+=1
            break

Je définie tout d'abord une fonction isprime qui retourne vrai ou faux selon le nombre est pair ou impair.
Après, j'ai crée un tableau de 10000 valeurs.
Ensuite, j'ai défini une liste (14*10).
A la fin, j'exécute le programme dans la fonction while qui calcule la somme entre deux liste terme par terme et affiche le résultat dès qu'une condition est vérifiée.

Si vous avez plus de questions sur le principe du code, n'hésitez pas.
Merci d'avance.

+++
LabChNe

**josmiley** · 10/11/2010, 09h54

pour commencer ...

Je définie tout d'abord une fonction isprime qui retourne vrai ou faux selon le nombre est pair ou impair.

Code :

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

def isprime(n): return n&1

ou bien

Code :

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

isprime = lambda n: n&1

j'ai dans l'idée que tu cherche à faire une liste genre [(1,2),(2,4),(3,6) ...]

Code :

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

[(i,i*2) for i in range(1,10001)]

**LabChNe** · 10/11/2010, 12h08

Merci josmiley,
la fonction définit si le nombre est primaire ou non, je me suis gouré dsl.

**VinsS** · 10/11/2010, 15h09

Envoyé par LabChNe

Merci josmiley,
la fonction définit si le nombre est primaire ou non, je me suis gouré dsl.

Moi, j'ai plutôt l'impression que ta fonction isprime cherche les nombres premiers

Si tu partais d'une liste des premiers nombres premiers que quiconque pourrait citer de mémoire, tu te simplifieras la vie, parce que c'est franchement tordu, ton code.

exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
nbPrem = [5, 3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
ls = 10000    # Disons une limite supérieure
val = 49       # On connait déjà les précédents
while val <= ls :
    for n in nbPrem :
	if val%n == 0 :
		val += 2		#on ne vérifie que les nombres impairs
		break
	elif n >= sqrt(val) :		#inutile au-delà de la racine carrée
		nbPrem.append(val)
		val += 2
		break

Pour la suite de ton code, je vais essayer de deviner ce qu'il fait.

**LabChNe** · 10/11/2010, 15h18

VinsS,

J'ai essayé, l'affectation du tableau des nombres premiers ne pronds même pas 3 secondes, par contre le reste est super long.
Je ne précise pas les termes directement parceque le tableau va jusqu'à 104743 de tête et je n'apprends pas par coeur les nombres premiers jusqu'à ce chiffre.
J'ai l'impression que la dernière boucle while ralentit l'exécution même en important psyco.

+++
LabChNe

**LabChNe** · 11/11/2010, 08h33

J'ai modifié le code en créant une fonction qui me retourne le résultat et en utilisant la fonction psyco.bind(), c'est toujours aussi lent.
Je ne sais pas si psyco joue bien son rôle???

D'autres suggestions ???

**tyrtamos** · 11/11/2010, 12h51

Bonjour,

Plutôt que de recalculer à chaque fois une liste de nombres premiers, tu peux prendre la liste qui se trouve sur mon site (nb premiers < 65536):

http://python.jpvweb.com/mesrecettes...liste_premiers

Il existe aussi des sites qui en contiennent plus, comme celui-ci (jusqu'à 1 000 000 000), mais il faut construire un petit code pour les récupérer dans Python:

http://nombrespremiersliste.free.fr/

Pour chercher plus rapidement dedans, on peut même chercher par dicchotomie:

http://python.jpvweb.com/mesrecettes...?id=dichotomie

Pour le reste, je ne comprends rien à ton code: pourrais-tu donner plus d'explications: facto3? var1?, etc...

Sinon, j'ai déjà remarqué que psyco ne faisait pas gagner grand chose dans les calculs en nombres entiers. Il vaut mieux travailler l'algorithme et son codage.

Tyrtamos

**VinsS** · 11/11/2010, 15h21

Envoyé par tyrtamos

Pour le reste, je ne comprends rien à ton code: pourrais-tu donner plus d'explications: facto3? var1?, etc...
Tyrtamos

Voila qui me rassure.

Pour tout dire, je n'avais pas été attentif au fait que le code relançait
isprim pour chaque nombre, ce qui déjà expliquerait le temps de travail.

Avec mon code j'arrive à tes 10.000 premiers nombres premiers en 0.66 sec, ensuite ton code ne devrait plus qu'itérer dans la liste obtenue.

Histoire de fermer une porte.

**LabChNe** · 12/11/2010, 09h22

Salut à tous,

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
from math import sqrt
from array import array
import psyco
psyco.full()
def isprime(n):
    if n==1:
        return False
    else:
        if n<4:
                return True
        elif n%2==0:
                return False
        elif n<9:
            return True
        elif n%3==0:
            return False
        else:
            r=int(sqrt(n))
            f=5
            while f<=r:
                if n%f==0:
                    return False
                    break
                elif n%(f+2)==0:
                    return False
                    break
                else:
                    f+=6
            return True
 
tableau=array('i')
c=0
i=2
while c<=10000:
    if isprime(i):
        tableau.insert(c+1,i)
        c+=1
    i+=1
 
facto3=[[0,0,0,-1,0,-1,1,0,0,0],
        [1,1,-1,0,0,1,-1,0,0,0],
        [0,-1,0,0,0,0,-1,1,0,0],
        [-1,0,0,0,0,0,0,-1,1,0],
        [0,-1,0,0,-1,0,0,0,0,1],
        [0,0,0,1,1,0,0,0,0,-1],
        [0,0,1,0,0,0,0,1,-1,0],
        [0,0,0,1,1,0,0,-1,0,0],
        [0,0,0,0,0,0,-1,0,0,0],
        [0,0,0,0,1,-1,0,0,0,0],
        [0,0,0,0,-1,1,0,0,0,0],
        [-1,1,1,0,0,0,0,0,0,0],
        [0,0,0,-1,0,0,0,0,0,0],
        [0,0,1,0,1,0,0,0,0,0]]
 
var1=[1,0,0,0,0,0,0,0,0,0]
print var1
c=2
k=0
cont=0
while k<=100:
    cont+=1
    for i in range(0,14,1):
        f1=[m+n for m,n in zip(var1,facto3[i])]
        if min(f1)>=0:
            var1=f1
            if var1[1:10].count(0)==9 and var1[0]==tableau[k]:
                print str(cont) + ' : ' + str(var1[0])
                k+=1
            break

Je m'exuse du retard.
Il s'agit de la résolution d'un problème mathématique connu sous le non de fractran http://en.wikipedia.org/wiki/FRACTRAN.
Après la création d'un tableau de 10000 nombres premiers, j'ai crée une liste qui ne représente que le chiffre 2.
En effet je représente les chiffres par leur puissance 2=2^1 d'où la liste [1,0,0,0,0,0,0,0,0,0].
Je multiplie 2 par une fraction de la liste facto3 et je m'arrête dès que le résultat donne un nombre entier.
Je refais le même exercice et je tombre régulièrement sur des chiffres de la forme 2^nombre primaire(2,3,5,7,11,...)
Voilà l'explication du reste.
Je programmais sur d'autres langages comme c,vba et je débute sur python.
J'ai entendu qu'il est rapide et convivial pour les calculs scientifiques, apparement il n'est pas si rapide que ca.

Merci pour tous.

+++
LabChNe

**dividee** · 12/11/2010, 10h53

Générer les nombres premiers avec ce programme FRACTAN est une curiosité, c'est pas vraiment fait pour être efficace.

Je pense que tu passes à côté de quelque chose en représentant les instructions sous forme de listes d'exposants de facteurs premiers. Une instruction c'est un nombre rationnel. Son exécution est simple: si le nombre en entrée est un multiple du dénominateur de l'instruction, multiplier le nombre par l'instruction.

Voici une implémentation partielle, à toi de compléter:

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
from fractions import Fraction
 
primes_program = map(Fraction, [
    "17/91", "78/85", "19/51", "23/38", "29/33", "77/29", "95/23",
    "77/19", "1/17", "11/13", "13/11", "15/2", "1/7", "55" ])
 
def run_fractan(program, num):
    while True:
        for instr in program:
            if num % instr.denominator == 0:
                num *= instr
                yield num
                break
        else:
            break

Il faut au moins Python 2.6 pour le module fractions.

**LabChNe** · 12/11/2010, 14h12

Le temps d'implémenter, je te redis.
Merci.

Alléger le code

Python

Discussions similaires

Partager

Partager