Alléger le code

Version imprimable

Alléger le code

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:

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

10/11/2010, 09h54
josmiley

pour commencer ...

Citation:

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

Code:

def isprime(n): return n&1

ou bien

Code:

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:

[(i,i*2) for i in range(1,10001)]
10/11/2010, 12h08
LabChNe

désolé

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

Citation:

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:

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.

10/11/2010, 15h18
LabChNe

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
11/11/2010, 08h33
LabChNe

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 ???
11/11/2010, 12h51
tyrtamos

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
11/11/2010, 15h21
VinsS

Citation:

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.

Salut à tous,

Code:

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

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:

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.

12/11/2010, 14h12
LabChNe

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