Exercice - niveau avancé

itérateurs et générateurs¶

Tous les exercices de ce notebook vous demandent d’écrire des fonctions qui construisent des itérateurs.

import itertools

1. Nombres premiers¶

On vous demande d’écrire un générateur qui énumère les nombres premiers.

Naturellement il existe de nombreuses biliothèques pour cela, mais on vous demande ici d’écrire votre propre algorithme, même s’il est naïf.

from corrections.gen_primes import exo_primes
exo_primes.example()

Le générateur ne s’arrête donc jamais, c’est un générateur infini comme itertools.count(). Le système de correction automatique est capable d’extraire certaines parties du flux du générateur, avec une convention voisine de range() et/ou du slicing.

Ainsi par exemple le deuxième jeu de test, sous-titré 1 → 5 / 2, va retenir les éléments énumérés par le générateur aux itérations 1, 3 et 5 - en commençant bien sûr à compter à 0.

NOTES

• Évidemment, il vous faut retourner un itérateur, et la correction automatique vérifiera ce point.

• Notez aussi que, lorsqu’on cherche à déterminer si $n$ est entier, on a nécessairement déjà fait ce travail sur tous les entiers plus petits que $n$. Il est donc tentant, et fortement recommandé, de profiter de cette information pour accélérer l’algorithme.

• Si votre algorithme est très lent ou faux, vous pouvez perdre le kernel (en français noyau), c’est-à-dire qu’il calcule pendant très longtemps (ou pour toujours) ; dans ces cas-là, la marge gauche indique In [*]: et l’étoile n’est jamais remplacée par un chiffre. Il vous faut alors interrompre votre kernel ; pour cela utilisez le menu Kernel qui a des options pour interrompre ou redémarrer le kernel courant ; les raccourcis clavier i i et 0 0 permettent aussi d’interrompre et redémarrer le noyau.

# à vous de jouer

def primes():
    # vous DEVEZ retourner un itérateur
    # bien sûr count() n'est pas une bonne réponse...
    return itertools.count()

# pour corriger votre code
exo_primes.correction(primes)

zone de debug¶

# à toutes fins utiles

MAX = 10

iterator = primes()

for index, prime in enumerate(itertools.islice(iterator, MAX)):
    print(f"{index} -> {prime}")

0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 4
5 -> 5
6 -> 6
7 -> 7
8 -> 8
9 -> 9

2. Les carrés des nombres premiers¶

On veut à présent énumérer les carrés des nombres premiers

NOTE il y a au moins deux façons triviales de parvenir au résultat.

from corrections.gen_primes import exo_prime_squares
exo_prime_squares.example()

# à vous

def prime_squares():
    ...

exo_prime_squares.correction(prime_squares)

3. Combinaisons d’itérateurs¶

On vous demande d’écrire un itérateur qui énumère des couples :

• en première position, on veut trouver les nombres premiers, mais avec un décalage :
  les cinq premiers tuples contiennent 1, puis le sixième contient 2, et à partir de là les nombres premiers ;

• en deuxième position, les carrés des nombres premiers, sans décalage :

NOTE
Il peut être tentant de créer deux instances de l’itérateur primes() ; toutefois c’est cet objet qui demande le plus de temps de calcul, aussi on vous suggère de réfléchir, en option, à une solution qui ne crée qu’un seul exemplaire de cet itérateur.

from corrections.gen_primes import exo_prime_legos
exo_prime_legos.example()

# à vous de jouer

def prime_legos():
    ...

exo_prime_legos.correction(prime_legos)

zone de benchmarking¶

un ordre de grandeur: pour le code suivant, ma solution prend environ 60ms
la cellule, qui fait le calcul 5 * 5 fois, prend environ 2s à afficher le résultat

%%timeit -n 5 -r 5

N = 10_000

P = prime_legos()
for x in range(N): 
    next(P)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[12], line 1
----> 1 get_ipython().run_cell_magic('timeit', '-n 5 -r 5', '\nN = 10_000\n\nP = prime_legos()\nfor x in range(N): \n    next(P)\n')

File /__w/course/course/venv/lib/python3.12/site-packages/IPython/core/interactiveshell.py:2572, in InteractiveShell.run_cell_magic(self, magic_name, line, cell)
   2570 with self.builtin_trap:
   2571     args = (magic_arg_s, cell)
-> 2572     result = fn(*args, **kwargs)
   2574 # The code below prevents the output from being displayed
   2575 # when using magics with decorator @output_can_be_silenced
   2576 # when the last Python token in the expression is a ';'.
   2577 if getattr(fn, magic.MAGIC_OUTPUT_CAN_BE_SILENCED, False):

File /__w/course/course/venv/lib/python3.12/site-packages/IPython/core/magics/execution.py:1226, in ExecutionMagics.timeit(self, line, cell, local_ns)
   1223         if time_number >= 0.2:
   1224             break
-> 1226 all_runs = timer.repeat(repeat, number)
   1227 best = min(all_runs) / number
   1228 worst = max(all_runs) / number

File /usr/lib/python3.12/timeit.py:208, in Timer.repeat(self, repeat, number)
    206 r = []
    207 for i in range(repeat):
--> 208     t = self.timeit(number)
    209     r.append(t)
    210 return r

File /__w/course/course/venv/lib/python3.12/site-packages/IPython/core/magics/execution.py:184, in Timer.timeit(self, number)
    182 gc.disable()
    183 try:
--> 184     timing = self.inner(it, self.timer)
    185 finally:
    186     if gcold:

File <magic-timeit>:5, in inner(_it, _timer)

TypeError: 'NoneType' object is not an iterator

4. Les $n$-ièmes nombres premiers, avec $n$ premier¶

On vous demande d’implémenter un itérateur qui renvoie les $n$-ièmes nombres premiers, mais seulement pour $n$ premier.

Ainsi comme primes() retourne la suite

on veut que prime_th_primes retourne la suite

# ce qui est illustré sur cet exemple calculé, qui va un peu plus loin

from corrections.gen_primes import exo_prime_th_primes
exo_prime_th_primes.example()

# À vous de jouer

def prime_th_primes():
    # souvenez-vous que vous devez retourner un itérateur
    return itertools.count()

# pour corriger votre code
exo_prime_th_primes.correction(prime_th_primes)

zone de benchmarking¶

un ordre de grandeur: pour le code suivant, ma solution prend environ 150ms
la cellule, qui fait le calcul 3 * 3 fois, prend environ 1.5s à afficher le résultat

%%timeit -n 3 -r 3

N = 2_000

P = prime_th_primes()
for x in range(N): next(P)

294 μs ± 22.5 μs per loop (mean ± std. dev. of 3 runs, 3 loops each)