Le fonctionnement d'une boucle for

Si l'iterable iterée change dans la boucle

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Salut à tous,

j'étais en train de coder le crible d'Ératosthenes en python et j'en suis arrivé à ce code (qui ne fonctionne absolument pas)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def is_divisor_of(x, y):
    """Return True if y is a divisor of x else return False"""
    return True if x%y == 0 else False

def sieve_of_eratosthenes(limit=100):
    """Return every prime number lower than limit in a list"""
    result = range(1, limit)    # Store all the number from 1 to limit
    for i in result:
        # Remove the multiple of i
        result = filter(lambda x: not is_divisor_of(x, i), result)
    return list(result)

Ce que je me dis c'est que je ne comprends pas bien le fonctionnement de la boucle for, puisque je ne croit pas qu'elle prend en considération les changement effectués sur result.

Ma question est donc là comment marche la boucle for et comment pourrait-je écrire ce code de manière élégante (avec un while sans doute mais j'ai pas l'impression que c'est ce qu'il y a de mieux)

Je vous remercie d'avance pour votre aide :D

« La Nature est un livre écrit en langage mathématique », Galilée

+0 -0

Cette réponse a aidé l'auteur du sujet

Déjà, modifier une liste en cours d'itération est une mauvaise pratique car risque de donner des comportements inattendus (ça se passera globalement bien si des éléments sont ajoutés en fin de liste, mais si tu essaies d'en insérer au début c'est la cata).

Maintenant, pour ton code en particulier, tu ne modifies pas la liste, tu en crées une nouvelle, à laquelle tu donnes le même nom que la précédente. Sauf que cette nouvelle liste n'a plus rien à voir avec celle utilisée ligne 8, donc n'est pas prise en compte lors de l'itération. La ligne du for (ligne 8) n'est évaluée qu'une fois avant de commencer à itérer, elle ne fait pas partie du corps de la boucle.

Édité par entwanne

Cette réponse a aidé l'auteur du sujet

La ligne du for n'est évaluée qu'une fois avant de commencer à itérer, elle ne fait pas partie du corps de la boucle.

S'il fallait une preuve de plus que ce qu'Antoine avance est correct, la voici:

1
2
3
for i in range(1, 10):
 print(i)
i+=1

Comportement totalement contre-intuitif assuré pour celui qui, comme moi, réfléchit avant tout en Java, PHP et C++. Mais en y réfléchissant mieux, c'est tout à fait logique étant donné le fonctionnement objet de python.

Par contre python se protège quand même des modifications concurrentes un minimum, tu ne peux pas faire n'importe quoi n'importe comment non plus; et heureusement, le résultat serait sans doute aléatoire. Ce code provoque une erreur par exemple:

1
2
3
4
5
d = { 'a':1, 'b': 2, 'c': 3}
for k in d:
 v = d[k]
 d[k+k]=v+v
 print(k+'='+str(v))

Ma plateforme avec 23 jeux de société classiques en 6 langues et 13000 joueurs: http://qcsalon.net/ | Apprenez à faire des sites web accessibles http://www.openweb.eu.org/

+0 -0
Auteur du sujet

Ok merci de vos réponses :)

Donc avec une boucle while ça donne ça

1
2
3
4
5
6
7
8
9
def sieve_of_eratosthenes(limit=100):
    """Return every prime number lower than limit in a list"""
    result = range(1, limit)    # Store all the number from 1 to limit
    i = 1
    while i < len(result):
        # Remove the multiple of i
        result = list(filter(lambda x: not is_divisor_of(x, result[i]), result))
        i += 1
    return list(result)

C'est propre ou je devrait écrire certaines choses autrement ?

« La Nature est un livre écrit en langage mathématique », Galilée

+0 -0
Staff

Comportement totalement contre-intuitif assuré pour celui qui, comme moi, réfléchit avant tout en Java, PHP et C++. Mais en y réfléchissant mieux, c'est tout à fait logique étant donné le fonctionnement objet de python.

Ça n'a pas tant à voir avec le fonctionnement objet de Python qu'avec le fait que la boucle for ne crée pas de nouveau scope en Python.

I was a llama before it was cool

+0 -0
Staff

Cette réponse a aidé l'auteur du sujet

1
2
3
def is_divisor_of(x, y):
    """Return True if y is a divisor of x else return False"""
    return True if x%y == 0 else False

LudoBike

N'écrit jamais ça. Remplace le par ça :

1
2
3
def is_divisor_of(x, y):
    """Return True if y is a divisor of x else return False"""
    return x%y == 0

La structure que tu utilises revient à dire : « si c'est vrai, retourne vrai, si c'est faux, retourne faux », autant retourner directement vrai ou faux. Ta structure appartient au musée des horreurs.

+2 -0

Cette réponse a aidé l'auteur du sujet

1
2
3
4
5
6
7
8
9
def sieve_of_eratosthenes(limit=100):
    """Return every prime number lower than limit in a list"""
    result = range(1, limit)    # Store all the number from 1 to limit
    i = 1
    while i < len(result):
        # Remove the multiple of i
        result = list(filter(lambda x: not is_divisor_of(x, result[i]), result))
        i += 1
    return list(result)

C'est propre ou je devrait écrire certaines choses autrement ?

LudoBike

Mon Python est un peu vieux et il y a suffisamment d'autres personnes ici pour les conseils de style, mais en termes d'algorithmique, c'est pas le crible d'Eratosthène que tu as écrit là. L'idée du crible, c'est de dire que pour éliminer tous les multiples de $n$, on met False dans les cases du tableau de $n$ en $n$ (donc on utilise result comme un tableau, avec des accès immédiats, pas en le parcourant avec un for comme si c'était une liste). Là, pour chaque $n$, tu parcours tout le tableau qui reste et pour chaque case tu fais un test is_divisor.

Edit : en plus, ton code a l'air faux : chez moi, il oublie plein de nombres premiers.

Voilà un peu en vrac ton code, une version correcte, un benchmark à l'arrache et les résultats :

 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
#! /usr/bin/env python
import itertools
import time
import sys

def sieve_of_eratosthenes(limit=100):
    """Return every prime number lower than limit in a list"""
    result = range(1, limit)    # Store all the number from 1 to limit
    i = 1
    while i < len(result):
        # Remove the multiple of i
        result = list(filter(lambda x: x % result[i] != 0, result))
        i += 1
    return list(result)

def sieve(limit):
    is_prime = [True] * (limit + 1)
    for i in range(2, limit + 1):
        if is_prime[i]:
            # On peut s'arrêter à sqrt(limit) si on sait la calculer
            for j in range(2 * i, limit + 1, i):
                is_prime[j] = False
    # On garde 0 et 1 parce que la flemme de les enlever
    return list(itertools.compress(range(limit + 1), is_prime))

n = int(sys.argv[1])
x = time.time()
sieve_of_eratosthenes(n)
y = time.time()
sieve(n)
z = time.time()
print("%d %f %f" % (n, y - x, z - y))
1
2
$ ./primes.py 50000
50000 4.733370 0.009205

Pour les maniaques de la microseconde et les tortionnaires de mouche du coin, je précise quand même : il est évidemment possible d'optimiser le code que j'ai écrit (d'ailleurs le compress pour avoir le même format de retour est un peu laid), et je ne serais même pas surpris si quelqu'un arrivait avec une version tunée du code original qui batte la mienne. Je ne cherche ni à faire un concours de qui dure le moins longtemps, ni même à proposer quelque chose d'efficace sinon je ferais pas ça en python mais à montrer pourquoi l'algorithme du PO n'est pas le bon. Ceci étant dit, que ça ne vous empêche pas de jouer aux micro-optimisations, mais moi je m'arrête là :-)

Édité par Eusèbe

+2 -0
Auteur du sujet

La structure que tu utilises revient à dire : « si c'est vrai, retourne vrai, si c'est faux, retourne faux », autant retourner directement vrai ou faux. Ta structure appartient au musée des horreurs.

Aabu

Effectivement ça n'a vraiment aucun sens, je crois que je vais encadrer cette fonction et la mettre devant ma porte pour effrayer (edit) les voleurs les esprits (ça rend mieux) :D

Édité par LudoBike

« La Nature est un livre écrit en langage mathématique », Galilée

+0 -0
Staff

Cette réponse a aidé l'auteur du sujet

Moi j'aime les drosophiles. En particulier quand je suis invité de façon aussi méprisante à ne pas les torturer. :}

Blague à part, le code d'Eusèbe peut être rendu plus concis et intuitif en remplaçant la seconde boucle par une slice.

Et accessoirement plus rapide, même si ça n'a qu'un intérêt purement académique sur cette fonction.

1
2
3
4
5
6
7
def sieve(limit):
    is_prime = [True] * (limit + 1)
    false = [False] * (limit + 1)
    for i in range(2, limit + 1):
        if is_prime[i]:
            is_prime[2*i::i] = false[2*i::i]
    return list(itertools.compress(range(limit + 1), is_prime))

Édité par nohar

I was a llama before it was cool

+1 -0
Auteur du sujet

Moi j'aime les drosophiles. En particulier quand je suis invité de façon aussi méprisante à ne pas les torturer. :}

nohar

J'ai pas compris tu peux expliquer ?

« La Nature est un livre écrit en langage mathématique », Galilée

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte