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

Quelques appels à is_prime

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

Et l’efficacité ?

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

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

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
>>> %timeit is_prime(pair)
230 ns ± 1.88 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

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

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

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. def is_prime(n):
  3.     """retourne True ssi n est un nombre premier"""
  4.     n_is_prime = True
  5.     if n < 2:
  6.         n_is_prime = False
  7.     else:
  8.         d = 2
  9.         while n_is_prime and d < int(sqrt(n)) + 1:
  10.             if n % d == 0:
  11.                 n_is_prime = False
  12.             d += 1
  13.     return n_is_prime
>>> %timeit is_prime(grand)
3.11 ms ± 67.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

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
>>> %timeit is_prime(grand)
596 µs ± 4.82 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

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

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 :

>>> all([True, True])
True
>>> all('hello')
True
>>> all('')
True
>>> all((3 > 2, is_prime(5)))
True
>>> all([is_prime(n) for n in range(10)])
False

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

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

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 :

>>> sum(x ** 2 for x in range(10))
285
>>> 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"""
>>> s = set(mot.lower() for mot in phrase.split())
>>> print(s)
{'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’'}
>>> phrase = phrase.lower()
>>> d = dict((c, phrase.count(c)) for c in phrase if 'a' <= c <= 'z')
>>> print(d)
{'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}

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))

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 :

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

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

Première vérification

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

Deuxième vérification

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

>>> it = (x {{ 2 for x in range(5))
>>>
>>> # Première utilisation
>>> for n in it:
       ... print(n)
0
1
4
9
16
>>>
>>> # deuxième utilisation
>>> for n in it:
       ... print(n)
>>>

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.

>>> it2 = (d for d in range(2, int(sqrt(pair))+1))
>>> all(pair % d for d in it2)
False
>>>for d in it2:
      ... if d < 6:
      ... ... print(d)
      ... else:
      ... ... break
3
4
5

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 :

def is_prime(n):
    if n<2:
        return False
    else:
        for d in range(2,int(sqrt(n)+1)):
            if n%d==0:
                return False
    return True

Navigation

Articles de la rubrique

  • La fonction all et les expressions génératrices

Annonces

Prochains rendez-vous de l’IREM

Assemblée générale de l’APMEP-Réunion

- Mercredi 21 aout à 14h, lycée Évariste-de-Parny, saint-Paul.

Réunion de rentrée de l’IREM

- Mercredi 11 septembre 2019, 14h-18h, salle S23.6, PTU, Saint-Denis.

Séminaire de l’IREM

- Mercredi 9 octobre 2019, 14h-18h : campus du Tampon.
- Mercredi 6 novembre 2019, 14h-18h : salle S23.6, PTU, Saint-Denis.
- Mercredi 27 novembre 2019, 14h-18h : campus du Tampon.
- Mercredi 5 février 2020, 14h-18h : salle S23.6, PTU, Saint-Denis.
- Mercredi 4 mars 2020, 14h-18h : campus du Tampon.
- Mercredi 8 avril 2020, 14h-18h : salle S23.6, PTU, Saint-Denis.


Brèves

Python au bac 2019

vendredi 31 mai

C’est une brève de MathemaTICE

La question 4b de l’exercice 3 du bac S Amérique du Nord ne pouvait être résolue sans utiliser Python.

Elwyn Berlekamp

jeudi 18 avril

Elwyn Berlekamp, connu des lecteurs de ce site pour son jeu des interrupteurs, était un spécialiste du jeu de Go ainsi que de la Pipopipette, d’Édouard Lucas que Berlekamp admirait énormément.

Notation au bac

lundi 11 décembre 2017

Une nouvelle notation sera pratiquée à partir de la session 2018 pour les algorithmes au bac. Elle est décrite avec de nombreux exemples, ici.

Décès de Roger Mohr

mardi 27 juin 2017

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Statistiques

Dernière mise à jour

mercredi 21 août 2019

Publication

845 Articles
Aucun album photo
140 Brèves
11 Sites Web
145 Auteurs

Visites

590 aujourd'hui
722 hier
2905599 depuis le début
30 visiteurs actuellement connectés