Exercices sur la complexité algorithmique

1. Calcul du nombre d'opérations

1.1 Calculs simples

Ci-dessous vous trouverez trois implémentations de conversion d'un nombre de secondes en heures, minutes, secondes. Pour rappel, la fonction divmod() calcule la division entière et le reste en même temps.

Calculez pour chacune d'entre elles

• le nombre d'affectations
• le nombre d'opérations élémentaires
• le coût d'exécution total

Quelle implémentation est la plus efficace selon vous ?

def convertisseurA(n):
    h = n // 3600
    m = (n - 3600*h) // 60
    s = n % 60
    return h,m,s

def convertisseurB(n):
    h = n // 3600
    m = (n % 3600) // 60
    s = n % 60
    return h,m,s

def convertisseurC(n):
    h, n = divmod(n, 3600)
    m, s = divmod(n, 60)
    return h,m,s

Python permet de calculer le temps passé à exécuter du code de plusieurs façons. Nous allons utiliser la bibliothèque cProfile.

Testez les temps d'exécution avec le code ci-dessous.

Est-ce que les temps d'exécution sont conformes à vos calculs précédents ? Que peut-on conclure sur le coût de la fonction divmod ?

import cProfile

def test(p):
    for n in range(1,p):
        h1,s1,m1 = convertisseurA(n)
        h2,s2,m2 = convertisseurB(n)
        h3,s3,m3 = convertisseurC(n)

    return h1+h2+h3, m1+m2+m3, s1+s2+s3

if __name__ == '__main__':
    final = (0, 0, 0)
    cProfile.run('final = test(1_000_000)')

    print(f'{final[0]} h {final[1]} min {final[2]} sec.')

L'inconvénient de cProfile telle que nous l'utilisons ici est que l'API ne fournit que des données cumulées sur une exécution. L'intérêt principal de l'analyse de complexité est de pouvoir observer l'évolution des temps d'exécution avec la taille des données.

Pour cela, nous avons préparé une classe ProfileRunner qui permet d'afficher des profils de façon graphique. Téléchargez-le ici

Vérifier (avec l'exemple précédent) que le code suivant fonctionne bien.

from ProfileRunner import ProfileRunner
from matplotlib import pyplot as plt

if __name__ == '__main__':
    pr = ProfileRunner(name="Conversion heures, minutes, secondes")
    pr.addFunction(convertisseurA)
    pr.addFunction(convertisseurB)
    pr.addFunction(convertisseurC)

    pr.runProfiler(range(10, 50_000, 500))
    pr.plotResults(title='Données brutes')

    plt.show()

Prenez le temps de lire et de comprendre le fonctionnement de la classe PlotPerf.ProfileRunner.

2. Efficacité en Python sur des opérations classiques

2.1 Coût d'une boucle

Voici deux façons de parcourir une boucle. L'une avec for, l'autre avec while.

def boucleFor(t: int) -> int:
    res = 0
    for i in range(t):
        res = i/(t-i)
    return res

def boucleWhile(t: int) -> int:
    i = 0
    res = 0

    while i < t:
        res = i/(t-i)
        i += 1
    return res

Question 1

Que font les fonctions boucleFor et boucleWhile?

Question 2

Calculez le coût d'exécution en opérations et affectations de chacune des fonctions boucleFor et boucleWhile.

Question 3

Laquelle des fonctions boucleFor ou boucleWhile a le coût d'exécution en opérations et affectations la moins élevée ?

Observation

Observez maintenant les temps d'exécution effectifs avec le code suivant.

if __name__ == '__main__':
    t = 1_000_000

    pr = ProfileRunner('Test boucles')
    pr.addFunction(boucleFor)
    pr.addFunction(boucleWhile)

    pr.runProfiler(range(10, t, t//100))
    pr.plotResults(title='Données brutes')

    plt.show()

Qu'observez-vous ? Quelle fonction est la plus rapide ? Saurez-vous l'expliquer ?

2.2 Coût d'un test vs. coût d'une exception

On définit maintenant la fonction boucleExceptionSimple.

def boucleExceptionSimple(t: int) -> int:
    i = 0
    res = 0

    try:
        while True:
            res = i/(t-i)
            i += 1
    except ZeroDivisionError:
        pass

    return res

Question 1

Calculez son coût en opérations et affectations et comparez-le à celui précédemment calculé pour la fonction boucleWhile. Vous pourrez faire l'approximation que l'entrée dans un bloc try - except a un coût d'une affectation et que l'occurrence d'une exception a un coût d'opération élémentaire.

Observation

Observez maintenant les temps d'exécution effectifs en adaptant le code fourni précédemment.

Qu'observez-vous ? Quelle fonction est la plus rapide ? Saurez-vous l'expliquer ?

Question 2

Faites la même chose que précédemment avec la fonction boucleExceptionImbriquee.

def boucleExceptionImbriquee(t: int) -> int:
    i = 0
    res = 0

    while True:
        try:
            res = i/(t-i)
            i += 1
        except ZeroDivisionError:
            break

    return res

Pouvez-vous en déduire le coût observé de l'entrée dans un bloc try - except ? Est-il conforme à l'approximation faite dans la question précédente ?

Vous devriez observer un comportement comme illustré ci-dessous.

2.3 Coût des opérations de calcul élémentaires

Les opérations arithmétiques ont un coût de calcul différent selon les opérations et selon le type des opérandes.

Mise en garde : les expériences et les observations attendues ici sont propres à Python et ne se généralisent pas à d'autres langages (notamment des langages compilés). Les résultats peuvent aussi beaucoup varier en fonction des caractéristiques de l'architecture matérielle sur laquelle le code est exécuté.

Question 1

Concevez pour chaque opérateur élémentaire (+, -, *, /) une expérimentation similaire pour mesurer son temps d'exécution et ceci pour les types int et float. Adaptez l'expérimentation aussi pour les bool et les opérations AND, OR et XOR.

Question 2

Quels sont les opérateurs les plus efficaces pour chaque type (une fois de plus, les conclusions ne sont valables que pour Python) ?

Question 3

Comparez vos résultats à ceux attendus ci-dessous.

2.4 Opérations efficaces sur des str

Question 1

Combien de méthodes différentes êtes-vous capables d'imaginer pour :

1. générer une chaîne de caractères (str) aléatoire composée de 0 et de 1 d'une longueur donnée ;
2. générer une chaîne de caractères (str) composée des n premiers entiers naturels, n donnée.

Question 2

Estimez le coût théorique de chacune de ces méthodes et déduisez-en celle qui vous semble la plus efficace.

Observation

Validez expérimentalement et expliquez les résultats ci-dessous.

2.5 Opérations efficaces sur les list

Question 1

Trouvez quatre méthodes en Python pour créer une liste de n éléments, chaque élément ayant la même valeur (p.ex. 0)

Question 2

Evaluez le coût de chaque méthode et mesurez son temps effectif.

Conclusion

Quelle méthode est la plus efficace ? Comparez avec le graphe ci-dessous.

Question 3

Adaptez les quatre méthodes précédentes pour qu'elles génèrent maintenant des listes où chaque élément est aléatoirement tiré avec la fonction random().

Mesurez à nouveau les temps d'exécution.

Est-ce que les conclusions précédentes d'efficacité tiennent toujours ? Comment l'expliqueriez-vous ?

Comparez avec le graphe ci-dessous.

2.6 Les structures élémentaires

Python fournit de façon standard quatre types permettant de stocker des collections : les tuple (tuples), list (tableaux), dict (dictionnaires) et set (ensembles).

Coût de création des structures élémentaires

Évaluez le temps d'exécution pour la création d'une collection contenant les n premiers entiers [0, 1, 2, 3, 4 ...]. On considèrera que dans le cas du dictionnaire on ait, comme dans le cas des tuples ou des tableaux coll[i]==i.

Quelles structures sont les moins coûteuses à construire ? Lesquelles sont les plus coûteuses ? Pouvez-vous fournir une explication plausible ?

Comparez avec les résultats ci-dessous.

Coût d'énumération directe des structures élémentaires

Toutes les collections peuvent être énumérées avec l'instruction for e in c:. Est-ce qu'une énumération de cette façon a le même coût quelle que soit la structure de la collection ?

Comparez avec les résultats ci-dessous.

Coût d'énumération indirecte des structures élémentaires

Les tuples, tableaux et dictionnaires peuvent être énumérés à partir de leurs indices ou clés d'indexation en utilisant la notation c[i]. Peut-on observer une différence de coût d'énumération entre les structures ? Peut-on observer une différence de coût d'énumération avec celui de l'exercice précédent ?

Comparez avec les résultats ci-dessous.

Coût de recherche

Toutes les collections permettent de savoir si un élément donné en fait parti avec l'opération in. Est-ce que les coûts de recherche sont équivalents quelle que soit la structure ?

Comparez avec les résultats ci-dessous.

Indicateurs de complexité algorithmique

Prélevez les temps d'exécution de l'ensemble des exercices sur les structures élémentaires pour des structures de 10_000, 50_000, 100_000, 500_000, 1_000_000 et 2_000_000 d'éléments et tracez les courbes. Quels types d'ordre de complexité observez-vous pour chaque structure et pour chaque opération ?