Table des matières

Objectifs du TP1

Le travail réalisé au cours de cette séance TP de 1h30 a pour objectifs:

1. De permettre aux étudiants de programmer des algorithmes pour:
   • trouver les éléments dupliqués dans une liste à l'aide de listes
   • trouver les éléments dupliqués dans une liste à l'aide de dictionnaires
   • comparer la complexité entre les listes et les dictionnaires dans un cas de parcours de graphe
   • effectuer des mesures concrètes de rapidité d'exécution
2. D'utiliser un environnement et des outils de travail pour la résolution du problème:
   • génération de jeux d'entrées aléatoires
   • définitions de métriques et réalisation de benchmarks
   • affichage des entrées et des sorties

Listes et dictionnaires

Ceci est un problème classique et relativement simple, mais il permet d'illustrer la différence de complexité entre les listes et les dictionnaires.

Trouver les éléments dupliqués dans une liste

• Entrées : une liste d'éléments
• Sortie : une liste des éléments qui apparaissent plus d'une fois dans la liste d'entrée

Le problème décisionnel associé est le suivant :

• Entrées : une liste d'éléments
• Sortie : un booléen indiquant si la liste contient des éléments dupliqués

Nous allons envisager différentes solutions et analyser leur complexité spatiale et leur complexité temporelle. Pour ce faire, vous pourrez vous aider de la documentation sur la complexité des opérations sur les structures de données de Python.

import random

n = 20000
# Génération de n entiers aléatoires entre 0 et n//10
data = [ random.randint(0, n//10) for _ in range(n) ]
dup1 = find_duplicates_list(data)
dup2 = find_duplicates_sort(data)
dup3 = find_duplicates_dict(data)
assert (sorted(dup1) == dup2 == sorted(dup3))

Benchmark

Le module Python timeit permet de mesurer le temps d’exécution d'une fonction python passée en paramètre et lancée number fois. En utilisant le code suivant, comparez les temps d'exécution des trois versions.

import itertools

def generate_all_strings(n):
    alphabet=[chr(c) for c in range(97, 123)]
    res=list(itertools.product(alphabet, repeat=n))
    res = ["".join(i) for i in res]
    return res

import random, timeit
import matplotlib.pyplot as plt
import copy

def Q2_benchmark():

    # Il y a 26 lettres dans l'alphabet, donc 26^5 = 11881376 possibilités
    all_strings = generate_all_strings(5)

    n_values = [100, 200, 500, 1000, 2000, 5000, 10000, 20000
                # , 50000, 100000, 200000, 500000, 1000000
                ]
    timings_list = [0 for _ in n_values]
    timings_sort = [0 for _ in n_values]
    timings_dict = [0 for _ in n_values]
    for i, n in enumerate(n_values):
        print(f'i={i}, n={n}')
        data1 = all_strings[:n//2]
        data2 = copy.copy(data1)
        random.shuffle(data1)
        random.shuffle(data2)
        data = data1 + data2
        timings_list[i] = timeit.timeit(lambda: find_duplicates_list(data), number=1)
        timings_sort[i] = timeit.timeit(lambda: find_duplicates_sort(data), number=1)
        timings_dict[i] = timeit.timeit(lambda: find_duplicates_dict(data), number=1)
    plt.plot(n_values, timings_list, color='red', marker='o')
    plt.plot(n_values, timings_sort, color='blue', marker='x')
    plt.plot(n_values, timings_dict, color='green', marker='+')
    # Plot with a log/log scale
    plt.xscale('log')
    plt.yscale('log')
    plt.title('Timings')
    plt.show()

Listes d'ajacence versus matrices d'adjacence

Nous représentons une relation binaire comme un sous-ensemble du produit cartésien de l'ensemble des entiers de 0 à 𝑛−1 avec lui-même. Cette relation binaire est également un graphe orienté dont les sommets sont les entiers de 0 à 𝑛−1 et les arcs sont les couples de la relation.

Dans un premier temps, nous générons une relation binaire à l'aide du modèle Erdos-Renyi (ER).

Principe : extraction aléatoire d'un sous-ensemble de cardinalité fixée parmi l'ensemble des couples possibles.

import random

def genere_relation_binaire(n, m):
    return random.sample([(x, y) for x in range(n) for y in range(n)], m)

Représentation

Nous pouvons envisager différentes représentations d'une relation binaire :

• liste d'adjacence : liste de dictionnaires ou d'ensembles
• matrice d'adjacence : liste de listes

Nous écrivons une fonction de conversion vers chacune de ces représentations. Nous ajoutons également une fonction retournant le voisinage d'un point.

def convertit_liste_adjacence(relation, n):
    """
    Convertit une relation binaire en liste d'adjacence
    """
    liste_adjacence = [[] for _ in range(n)]
    for x, y in relation:
        liste_adjacence[x].append(y)
    return liste_adjacence

def voisinage_liste_adjacence(liste_adjacence, u):
    """
    Renvoie le voisinage de x dans la relation binaire
    """
    return liste_adjacence[u]

Parcours en profondeur d'un graphe

On utilise la méthode itérative qui repose sur l'utilisation d'une pile.

Tous les noeuds sont parcourus : lorsque l'algorithme a épuisé une composante connexe, on passe à un prochain noeud non encore visité.

L'algorithme reçoit un graphe sous l'une des formes suivantes ainsi que la fonction de voisinage appropriée:

• matrice d'adjacence
• liste d'adjacence

Remarque : le parcours en profondeur à partir du noeud 𝑢 visite tous les noeuds accessibles depuis 𝑢 .

def sparse_factor(n):
    return int(1.05*n)

def dense_factor(n):
    return int(0.95 * n * n)

def validation_dfs(n):

    r_dense = genere_relation_binaire(n, dense_factor(n))
    r_sparse = genere_relation_binaire(n, sparse_factor(n))

    for r in [r_dense, r_sparse]:
        assert depth_first_search(convertit_liste_adjacence(r, n), n, voisinage_liste_adjacence) == depth_first_search(convertit_matrice_adjacence(r, n), n, voisinage_matrice_adjacence)

validation_dfs(1000)

Benchmark

# We need to pass them to the timeit function via globals()

def Q5_benchemark():
    global liste_adjacence, matrice_adjacence

    timings = {}
    timings['listes_adjacence'] = {}
    timings['matrice_adjacence'] = {}
    # Nombre de fois où l'on répète la mesure
    number = 1
    for n in [10, 20, 50, 100, 200, 500, 1000
              , 2000, 5000
              ]:

        timings['listes_adjacence'][n] = {}
        timings['matrice_adjacence'][n] = {}
        r_dense = genere_relation_binaire(n, dense_factor(n))
        r_sparse = genere_relation_binaire(n, sparse_factor(n))
        for i, r in enumerate([r_sparse, r_dense]):
            liste_adjacence = convertit_liste_adjacence(r, n)
            matrice_adjacence = convertit_matrice_adjacence(r, n)
            timings['listes_adjacence'][n][i] = timeit.timeit(f"depth_first_search(liste_adjacence, {n}, voisinage_liste_adjacence)",number=number,globals=globals())

            timings['matrice_adjacence'][n][i] = timeit.timeit(f"depth_first_search(matrice_adjacence, {n}, voisinage_matrice_adjacence)",number=number,globals=globals())

    # Define colors for representations and shapes for graph types: 
    # red for listes_adjacence and blue for matrice_adjacence
    # o for sparse graphs and * for dense graphs
    colors = ['red', 'blue']
    marks=['o', '*']
    for i, representation in enumerate(['listes_adjacence', 'matrice_adjacence']):
        for n in timings[representation]:
            for p in timings[representation][n]:
                plt.plot(n, timings[representation][n][p], color=colors[i], marker=marks[p])

    plt.xscale('log')
    plt.yscale('log')
    plt.title('Timings')
    plt.show()