# -*- coding: utf-8 -*-
import random
import timeit
import matplotlib.pyplot as plt
################## Question 1 #################
# Cette solution est simple mais pas optimale !
# Sa complexité en temps est bien O(n^3)
def find_duplicates_list(L):
"""Return a list of duplicates in L.
"""
# Create a list of duplicates
duplicates = []
# For each element in L
for i in range(len(L)):
# If the element is not in duplicates
for j in range(i+1, len(L)):
if L[i] == L[j] and L[i] not in duplicates:
duplicates.append(L[i])
# Return the list of duplicates
return duplicates
# Version avec complexité temporelle en O(n^2)
def find_duplicates_list_2(L):
"""Return a list of duplicates in L
"""
# Create a list of duplicates
duplicates = []
# For each element in L
for i in range(len(L)-1):
# If the element is not in duplicates
if L[i] in L[i+1:] and L[i] not in duplicates:
duplicates.append(L[i])
# Return the list of duplicates
return duplicates
def find_duplicates_sort(L):
"""Return a list of duplicates in L.
"""
# Sort L
L.sort()
# Create a list of duplicates
duplicates = []
# For each element in L
for i in range(len(L)-1):
# If the element is not in duplicates
if L[i] == L[i+1] and (len(duplicates)==0 or L[i] != duplicates[-1]):
duplicates.append(L[i])
# Return the list of duplicates
return duplicates
def find_duplicates_dict(L):
"""Return a list of duplicates in L.
"""
# Create a dictionary of duplicates
duplicates = {}
# For each element in L
for e in L:
# If the element is not in duplicates
if e not in duplicates:
duplicates[e] = 1
else:
duplicates[e] += 1
# Return the list of duplicates
return [e for e in duplicates if duplicates[e] > 1]
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 == dup3)
################## Question 2 #################
'''
Réponse:
- find_duplicates_list(L):
Dans ce cas, la complexité spatiale devient 𝑂(𝑛) , car on alloue
une liste de taille n pour la liste des éléments dupliqués.
La complexité temporelle est 𝑂(𝑛^3) , car on parcourt la liste
une fois pour chaque élément de la liste en comparant avec les
autres. En plus, on doit tester chaque fois s'il appartient ou non
à la liste des éléments dupliqués (opération in pour la liste).
La seconde version de la fonction find_duplicates_list_2(L) a une
complexité temporelle de 𝑂(𝑛^2) , car on parcourt la liste une fois
pour chaque élément de la liste en comparant avec les autres.
Attention: si les élèves utilisent un dictionnaire ou un set pour
"duplicates", la complexité d'opération in est constante.
- find_duplicates_sort(L):
La complexité spatiale est O(n) , car on alloue une liste de taille 𝑛
pour la liste des éléments dupliqués en plus de la complexité spatiale
du classement en place ($O(1)).
La complexité temporelle devient O(nlogn) , l'opération de trier devient
dominante car si l'élément est dans la liste des duplicata,
il est le dernier élément de la liste. Donc il suffit de le comparer avec
ce dernier.
- find_duplicates_dict(L):
Complexité spatiale : la complexité spatiale est 𝑂(𝑛) ,
car on alloue un dictionnaire dont la taille pourra croître jusqu'à 𝑛 .
Complexité temporelle : la complexité temporelle est 𝑂(𝑛) ,
car on parcourt la liste une fois, et pour chaque élément,
on teste si il est présent dans le dictionnaire à l'aide de l'opération
in, ce qui se fait en temps constant. Le filtrage de la liste pour
trouver les éléments dupliqués se fait en temps linéaire également.
'''
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
#print (len(generate_all_strings(5)))
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()
Q2_benchmark()
'''
Réponse (suite):
Pour construire un pire cas, il faut choisir une liste où tous les éléments
sont dupliqués. On peut donc la fabriquer en concaténant deux listes de
taille 𝑛/2 , dont tous les éléments sont distincts.
---Pour le benchmark, la différence de pente entre la courbe rouge (list) et les
deux autres est bien marquée.
---Il sera plus difficile d'observer la différence due au log𝑛 entre les
courbes vert et bleu. Ce facteur log𝑛 ne deviendra marquant que
pour des valeurs de 𝑛 très grandes.
'''
################## Question 3 #################
def genere_relation_binaire(n, m):
return random.sample([(x, y) for x in range(n) for y in range(n)], m)
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]
def convertit_matrice_adjacence(relation, n):
"""
Convertit une relation binaire en matrice d'adjacence
"""
matrice_adjacence = [[0 for _ in range(n)] for _ in range(n)]
for x, y in relation:
matrice_adjacence[x][y] = 1
return matrice_adjacence
def voisinage_matrice_adjacence(matrice_adjacence, u):
"""
Renvoie le voisinage de x dans la relation binaire
"""
return [v for v in range(len(matrice_adjacence)) if matrice_adjacence[u][v] == 1]
'''
Réponse:
-Complexité de la fonction de voisinage dans le cas d'une liste d'adjacence : 𝑂(1) .
On a immédiatement les sommets 𝑣 en relation avec 𝑢 . La complexité du parcours
de cette liste est en 𝑂(𝑑𝑒𝑔(𝑢)) .
-Complexité de la fonction de voisinage dans le cas d'une matrice d'adjacence : 𝑂(𝑛) .
On doit parcourir la ligne 𝑢 de la matrice. La complexité du parcours de
cette liste est toujours en 𝑂(𝑑𝑒𝑔(𝑢)) .
'''
################## Question 4 #################
def depth_first_search(graph, n, voisinage):
visited = set()
# print(f'graph: {graph}')
def dfs_visit(start):
# print(f'visiting from {start}')
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
for v in voisinage(graph, vertex):
if v not in visited:
stack.append(v)
for i in range(n):
if i not in visited:
dfs_visit(i)
return visited
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)
'''
Attention : les fonctions de voisinage ne retournent pas les sommets dans le même ordre. L'ordre de parcours des sommets n'est pas déterminé. Cela reste un parcours en profondeur, mais l'ordre des sommets visités peut varier.
'''
################## Question 5 #################
# On a besoin de les passer à la fonction timeit par le biais de globals()
def Q5_benchmark():
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.legend()
plt.xscale('log')
plt.yscale('log')
plt.title('Timings')
plt.show()
Q5_benchmark()
'''
Réponse:
--La complexité de cet algorithme est en 𝑂(𝑛+𝑚) si on utilise les listes
d'adjacence ( 𝑚=|𝐸| désignant le nombre d'arêtes du graphe).
--Si on utilise les matrices d'adjacence, la complexité est en 𝑂(𝑛^2) .
--La différence sera visible et importante
pour les graphes creux ('o'). Elle sera négligeable pour les graphes denses ('*).
'''
TP1Corrige