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 :

optimiser programme récursif nombres premiers


Sujet :

Calcul scientifique Python

  1. #1
    Membre régulier
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2010
    Messages
    406
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hautes Pyrénées (Midi Pyrénées)

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2010
    Messages : 406
    Points : 92
    Points
    92
    Par défaut optimiser programme récursif nombres premiers
    salut à tous
    j'ai écrit ceci qui marche bien :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def liste_premiers(n):
        N={x for x in range(1,n+1)}
        r=int(sqrt(n))
        if (r<=10):
            N={2,3,5,7}
        else:
            for i in liste_premiers(r):
                x=0
                while (x<=n): #Crible d'Eratosthene
                    if (x in N): N.remove(x)
                    x+=i
        L=[x for x in N]
        return(L)
    je me demande si c'est optimal et si on peut l'améliorer en termes de rapidité ou de fluidité
    Vincent

  2. #2
    Expert éminent

    Homme Profil pro
    Inscrit en
    Octobre 2008
    Messages
    4 298
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2008
    Messages : 4 298
    Points : 6 778
    Points
    6 778
    Par défaut
    Salut,

    Si je comprend bien, tu vérifies aussi les nombres pairs ?

    C'est une obligation la méthode récursive ?

  3. #3
    Expert éminent
    Avatar de tyrtamos
    Homme Profil pro
    Retraité
    Inscrit en
    Décembre 2007
    Messages
    4 461
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : Décembre 2007
    Messages : 4 461
    Points : 9 248
    Points
    9 248
    Billets dans le blog
    6
    Par défaut
    Bonjour,

    Le problème de la récursion avec Python, c'est qu'on est assez rapidement limité par la taille de la pile. Dans les cas "désespérés", on peut essayer de l'augmenter (sys.setrecursionlimit(...)), mais c'est un pis-aller.

    Il existe bien des problèmes qui se résolvent de façon très élégante avec la récursion. Par exemple, le parcours dans un arbre. Mais ici pour le crible d’Ératosthène, une bonne boucle est largement suffisante.

    Donc, à mon avis, et dans la mesure où il ne s'agit pas d'une étude portant sur la récursion, une bonne amélioration du code proposé est de supprimer la récursion...

    Il existe par ailleurs de nombreuses astuces pour accélérer les calculs, et surtout pour supporter de monter très haut dans les nombres avant d'avoir des problèmes de mémoire.

    Je me suis un peu amusé à ça il y a quelques temps, et, sans prétendre être au top, j'ai réussi à calculer les 455052511 nombres premiers inférieurs à 10 milliard en une heure environ. Il faut bien se rendre compte de ce que représentent une telle quantité de nombres: enregistrés sur disque, ils nécessitent un fichier de plus de 5 Go...
    Un expert est une personne qui a fait toutes les erreurs qui peuvent être faites, dans un domaine étroit... (Niels Bohr)
    Mes recettes python: http://www.jpvweb.com

  4. #4
    Membre régulier Avatar de fifafou
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Janvier 2016
    Messages
    173
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 22
    Localisation : France, Seine Maritime (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Janvier 2016
    Messages : 173
    Points : 92
    Points
    92
    Par défaut
    N={x for x in range(1,n+1)} peut être remplacé par N=range(1,n+1)}

  5. #5
    Expert éminent
    Avatar de tyrtamos
    Homme Profil pro
    Retraité
    Inscrit en
    Décembre 2007
    Messages
    4 461
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : Décembre 2007
    Messages : 4 461
    Points : 9 248
    Points
    9 248
    Billets dans le blog
    6
    Par défaut
    Bonjour,

    Sous Python 3, range est un itérateur. On peut donc obtenir la liste complète avec:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    N=list(range(1,11))
    print(N)
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    Un expert est une personne qui a fait toutes les erreurs qui peuvent être faites, dans un domaine étroit... (Niels Bohr)
    Mes recettes python: http://www.jpvweb.com

  6. #6
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 241
    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 241
    Points : 36 698
    Points
    36 698
    Par défaut
    La construction N={x for x in range(1,n+1)} fabrique un "set".
    On peut le remplacer par set(range(1, n + 1)).
    nota, mais pour savoir si c'est "mieux", il faut quand même mesurer.

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

  7. #7
    Membre régulier Avatar de fifafou
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Janvier 2016
    Messages
    173
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 22
    Localisation : France, Seine Maritime (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Janvier 2016
    Messages : 173
    Points : 92
    Points
    92
    Par défaut
    Citation Envoyé par VinsS Voir le message
    Salut,
    Si je comprend bien, tu vérifies aussi les nombres pairs ?
    je pense aussi que les nombres pairs allant de deux en deux,il doit y avoir une moyen d'optimiser le code de ce coté là.

  8. #8
    Membre expérimenté
    Homme Profil pro
    Inscrit en
    Mars 2007
    Messages
    941
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2007
    Messages : 941
    Points : 1 384
    Points
    1 384
    Par défaut
    Au sujet de la récursion, dans le cas présent, je ne pense pas que ça apportera beaucoup de la supprimer.

    La profondeur des appels récursifs ne croît que très lentement avec n. Si n = 10512 on n'aura que 9 ou 10 appels récursifs, mais il est bien sûr impossible d'aller jusque là avec un crible.

    Idem au niveau du temps de calcul; même si on va recalculer plusieurs fois les premiers nombres premiers à cause de l'implémentation récursive, la quantité de "recalculs" est à peine supérieure à la racine carrée de n ce qui est négligeable (moins de 32000 pour n = 109).

    pyprimes contient quelques implémentations intéressantes de cribles, dont notamment une implémentation récursive assez élégante du crible d'Eratosthène (le générateur sieve() dans sieve.py)

  9. #9
    Membre régulier
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2010
    Messages
    406
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hautes Pyrénées (Midi Pyrénées)

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2010
    Messages : 406
    Points : 92
    Points
    92
    Par défaut
    Citation Envoyé par fifafou Voir le message
    N={x for x in range(1,n+1)} peut être remplacé par N=range(1,n+1)}
    bonjour
    pouvez vous préciser ?
    voulez vous dire ?
    chez moi ça ne marche pas

  10. #10
    Membre régulier
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2010
    Messages
    406
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hautes Pyrénées (Midi Pyrénées)

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2010
    Messages : 406
    Points : 92
    Points
    92
    Par défaut
    Citation Envoyé par VinsS Voir le message
    Salut,

    Si je comprend bien, tu vérifies aussi les nombres pairs ?

    C'est une obligation la méthode récursive ?
    salut
    c'est pour le plaisir la méthode récursive
    je voualis juste voir si j'étais capable de faire ce truc des nombres premiers en méthode récursive

  11. #11
    Membre régulier
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2010
    Messages
    406
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hautes Pyrénées (Midi Pyrénées)

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2010
    Messages : 406
    Points : 92
    Points
    92
    Par défaut
    Citation Envoyé par tyrtamos Voir le message
    Bonjour,

    Sous Python 3, range est un itérateur. On peut donc obtenir la liste complète avec:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    N=list(range(1,11))
    print(N)
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    salut
    dans mon programme tel que je l'ai imaginé, N doit être un set et non pas une list
    car je sais faire set.remove mais je ne sais pas enlever un élément situé "en plein milieu" d'une liste

    d'autre part je ne vois pas la différence entre
    et
    peux tu m'éclairer ?

  12. #12
    Membre régulier
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2010
    Messages
    406
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hautes Pyrénées (Midi Pyrénées)

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2010
    Messages : 406
    Points : 92
    Points
    92
    Par défaut
    Citation Envoyé par wiztricks Voir le message
    La construction N={x for x in range(1,n+1)} fabrique un "set".
    On peut le remplacer par set(range(1, n + 1)).
    nota, mais pour savoir si c'est "mieux", il faut quand même mesurer.

    - W
    ok merci de l'info

  13. #13
    Membre régulier
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2010
    Messages
    406
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hautes Pyrénées (Midi Pyrénées)

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2010
    Messages : 406
    Points : 92
    Points
    92
    Par défaut
    Citation Envoyé par dividee Voir le message

    pyprimes contient quelques implémentations intéressantes de cribles, dont notamment une implémentation récursive assez élégante du crible d'Eratosthène (le générateur sieve() dans sieve.py)

    meric de l'info je vais regarder en détail de ce côté là
    Vincent

Discussions similaires

  1. Réponses: 5
    Dernier message: 13/03/2012, 11h32
  2. programme récursif, calcul de nombres binaires
    Par Jasmine80 dans le forum Langage
    Réponses: 4
    Dernier message: 20/01/2009, 17h02
  3. Programme détectant les nombres premiers
    Par frankthechamp dans le forum Windows Forms
    Réponses: 8
    Dernier message: 04/12/2008, 23h41
  4. Réponses: 2
    Dernier message: 20/02/2008, 23h44

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