La fonction all et les expressions génératrices

vendredi 29 mars 2019
par  Sébastien HOARAU

Le but de cette fiche est de montrer la puissance de la fonction all associée aux expressions génératrices. Puissance à la fois dans la forme (le code résultat est concis et proche du langage naturel) que dans le fond (la rapidité d’exécution est aussi bonne que d’autres solutions). Les tests sont fait sous l’interprète interactif ipython

L’exercice prétexte : la fonction is_prime

Cette fonction prend un entier n positif ou nul en entrée et retourne True si et seulement si n est un nombre premier.

Définition d’un nombre premier

Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs : 1 et lui-même.

En partant de cette définition, on serait tenté, pour coder en python une fonction is_prime testant la primalité d’un entier d’énumérer tous les diviseurs du nombre et constater qu’il y en a exactement deux. Ce n’est en général pas ce qu’on fait.

On peut aussi remarquer que n est premier si et seulement si n est supérieur ou égal à 2 et qu’aucun entier entre 2 et n-1 ne divise n. Ci-dessous une première définition sur ce principe :

  1. def is_prime(n):
  2.     """retourne True ssi n est un nombre premier"""
  3.     n_is_prime = True
  4.     if n < 2:
  5.         n_is_prime = False
  6.     else:
  7.         for d in range(2, n):
  8.             if n % d == 0:
  9.                 n_is_prime = False
  10.     return n_is_prime

Télécharger

Quelques appels à is_prime

  1. >>> some_int = [11, 8, 2, 0, -1, 151]
  2. >>>for n in some_int:
  3.       ...print(f'{n:3d} est-il premier ? {is_prime(n)}')
  4.  11 est-il premier ? True
  5.   8 est-il premier ? False
  6.   2 est-il premier ? True
  7.   0 est-il premier ? False
  8.  -1 est-il premier ? False
  9. 151 est-il premier ? True

Télécharger

Et l’efficacité ?

Dans un interprète ipython, on peut utiliser %timeit pour mesurer le temps d’exécution d’une instruction.

  1. >>> pair = 79991172
  2. >>> %timeit is_prime(pair)
  3. 5.41 s ± 178 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Télécharger

On constate un très long temps de réponse alors que le nombre est pair. Bien sûr cela est dû à la boucle for : alors même que l’on détecte immédiatement que 2 divise pair, la boucle poursuit jusqu’à la fin. Il convient donc de s’arrêter dès la détection d’un diviseur. Voici une autre version tenant compte de cette remarque :

  1. def is_prime(n):
  2.     """retourne True ssi n est un nombre premier"""
  3.     n_is_prime = True
  4.     if n < 2:
  5.         n_is_prime = False
  6.     else:
  7.         d = 2
  8.         while n_is_prime and d < n:
  9.             if n % d == 0:
  10.                 n_is_prime = False
  11.             d += 1
  12.     return n_is_prime

Télécharger

  1. >>> %timeit is_prime(pair)
  2. 230 ns ± 1.88 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Télécharger

Voilà qui est mieux. Testons cette fois avec un nombre premier.

  1. >>> grand = 79991173
  2. >>> %timeit is_prime(grand)
  3. 8.74 s ± 9.64 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Télécharger

Comme on le constate, le temps de calcul est important pour détecter la primalité d’un entier de l’ordre de la dizaine de millions ; ça ne semble pas très efficace. On peut améliorer les choses en constatant que la recherche d’un diviseur potentiel peut s’arrêter à int(sqrt(n))+1 :

  1. from math import sqrt
  2.  
  3. def is_prime(n):
  4.     """retourne True ssi n est un nombre premier"""
  5.     n_is_prime = True
  6.     if n < 2:
  7.         n_is_prime = False
  8.     else:
  9.         d = 2
  10.         while n_is_prime and d < int(sqrt(n)) + 1:
  11.             if n % d == 0:
  12.                 n_is_prime = False
  13.             d += 1
  14.     return n_is_prime

Télécharger

  1. >>> %timeit is_prime(grand)
  2. 3.11 ms ± 67.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Télécharger

Nous voilà avec un temps de réponse acceptable.

Mais quid de la clarté ?

Clairement ce code n’est pas très proche de la définition en langage courant, dont on rappelle qu’elle est :
n est premier ssi n > 1 et pour tout les entiers d entre 2 et racine carrée de n, d ne divise pas n. La clarté du code précédent pourrait amélioré en revenant à une boucle for et l’utilisation de plusieurs instructions return

  1. def is_prime(n):
  2.     """retourne True ssi n est un nombre premier"""
  3.     if n < 2:
  4.         return False
  5.     else:
  6.         for d in range(2,int(sqrt(n)) + 1):
  7.             if n % d == 0:
  8.                 return False
  9.         return True

Télécharger

  1. >>> %timeit is_prime(grand)
  2. 596 µs ± 4.82 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Télécharger

On constate, en plus d’avoir un code plus court, et probablement plus lisible, un gain en temps de réponse.Mais cela reste perfectible : l’utilisation de plusieurs return peut ne pas plaire. Et même si on opte pour cette version :

  1. def is_prime(n):
  2.     """retourne True ssi n est un nombre premier"""
  3.     n_is_prime = True
  4.     if n < 2:
  5.         n_is_prime = False
  6.     else:
  7.         for d in range(2,int(sqrt(n)) + 1):
  8.             if n % d == 0:
  9.                 n_is_prime = False
  10.                 break
  11.     return n_is_prime

Télécharger

La fonction all

all est une fonction prédéfinie python qui prend un iterable comme paramètre et retourne True si chaque élément de l’iterable est évalué à True ou si l’itérable est vide. Ci-dessous quelques exemples :

  1. >>> all([True, True])
  2. True
  3. >>> all('hello')
  4. True
  5. >>> all('')
  6. True
  7. >>> all((3 > 2, is_prime(5)))
  8. True

Télécharger

  1. >>> all([is_prime(n) for n in range(10)])
  2. False

Télécharger

Dans les exemples ci-dessus nous avons des itérables très classiques : listes, chaînes de caractères, tuples. Dans le dernier exemple nous utilisons une liste en compréhension. Cette idée peux être améliorée : un itérable peut être un itérateur, ici par exemple obtenu grâce à une expression génératrice.

Associons une expression génératrice

  1. >>> all(is_prime(n) for n in [2, 3, 5, 7, 11])
  2. True

Télécharger

Une expression génératrice est une expression de la forme :

(f(x) for x in iterateur)

Cette expression produit un itérateur. L’avantage principal d’un itérateur par rapport à un autre itérable comme les séquences, c’est qu’aucune structure n’est créée et donc un gain en mémoire appréciable. Ci-dessous quelques exemples de l’utilisation des expressions génératices :

  1. >>> sum(x ** 2 for x in range(10))
  2. 285

Télécharger

  1. >>> phrase = """Tu te jugeras donc toi-même, lui répondit le roi. C’ est le plus difficile. Il est bien plus difficile de se juger soi-même que de juger autrui"""
  2. >>> s = set(mot.lower() for mot in phrase.split())
  3. >>> print(s)
  4. {'donc', 'soi-même', 'le', 'toi-même,', 'juger', 'il', 'bien', 'difficile.', 'lui', 'roi.', 'plus', 'se', 'autrui', 'de', 'te', 'jugeras', 'tu', 'est', 'que', 'difficile', 'répondit', 'c’'}

Télécharger

  1. >>> phrase = phrase.lower()
  2. >>> d = dict((c, phrase.count(c)) for c in phrase if 'a' <= c <= 'z')
  3. >>> print(d)
  4. {'t': 7, 'u': 10, 'e': 17, 'j': 3, 'g': 3, 'r': 6, 'a': 2, 's': 7, 'd': 6, 'o': 5, 'n': 3, 'c': 4, 'i': 14, 'm': 4, 'l': 8, 'p': 3, 'f': 4, 'b': 1, 'q': 1}

Télécharger

Nouvelle définition de is_prime

  1. def is_prime(n):
  2.     return n > 1 and all(n % d != 0 for d in range(2, int(sqrt(n))+1))

Télécharger

Notons que nous retrouvons la clarté de la définition en langage naturel. Il nous reste à vérifier que le temps de réponse est au moins aussi bon qu’avant :

  1. >>> %timeit is_prime(grand)
  2. 915 µs ± 3.94 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Télécharger

Dernier point à vérifier : est-ce que la découverte d’un diviseur stoppe l’itération ?

Première vérification

  1. >>> %timeit is_prime(pair)
  2. 1.16 µs ± 1.82 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Télécharger

Deuxième vérification

Elle s’appuie sur la propriété suivante : un itérateur ne peut être utilisé qu’une fois.

  1. >>> it = (x {{ 2 for x in range(5))
  2. >>>
  3. >>> # Première utilisation
  4. >>> for n in it:
  5.        ... print(n)
  6. 0
  7. 1
  8. 4
  9. 9
  10. 16
  11. >>>

Télécharger

  1. >>> # deuxième utilisation
  2. >>> for n in it:
  3.        ... print(n)
  4. >>>

Télécharger

Comme on le constate, la deuxième itération ne produit rien : l’itérateur ayant servi une fois, il est vide la seconde fois.

  1. >>> it2 = (d for d in range(2, int(sqrt(pair))+1))
  2. >>> all(pair % d for d in it2)
  3. False

Télécharger

  1. >>>for d in it2:
  2.       ... if d < 6:
  3.       ... ... print(d)
  4.       ... else:
  5.       ... ... break
  6. 3
  7. 4
  8. 5

Télécharger

it2 est donc un itérateur des entiers de 2 à la racine carrée de notre grand nombre pair. La première fois nous l’utilisons dans la fonction all puis une seconde fois pour afficher quelques unes des valeurs. On constate que it2 n’a été utilisée par la fonction all que pour la première valeur (2) et donc la deuxième utilisation commence à 3.

Conclusion

Mal connue, la fonction all associée aux expressions génératrices offre à la fois une concision et une simplicité d’écriture proche du langage naturel sans perdre en performance. Elle mérite donc de figurer dans les concepts à enseigner même aux débutants. A noter que la fonction any propose les mêmes avantages.


Commentaires

Logo de Alain BUSSER
jeudi 20 juin 2019 à 03h23 - par  Alain BUSSER

Dans cet article est proposé un autre test de primalité, totalement inefficace mais basé sur une définition moins calculatoire des nombres premiers : Un nombre est premier si et seulement s’il admet exactement 2 diviseurs.

Logo de Alain BUSSER
jeudi 20 juin 2019 à 03h17 - par  Alain BUSSER

Bien que très éloignée de la langue courante (n’expliquant pas ce qu’est un nombre premier par exemple), cette version est très rapide, parce qu’elle utilise une subtilité de la fonction return qui agit comme break :

  1. def is_prime(n):
  2.     if n<2:
  3.         return False
  4.     else:
  5.         for d in range(2,int(sqrt(n)+1)):
  6.             if n%d==0:
  7.                 return False
  8.     return True

Télécharger

Navigation

Articles de la rubrique