1A.algo - la plus grande sous-séquence croissante - correction#
Links: notebook
, html, python
, slides, GitHub
Un exercice classique : trouver la plus grande sous-séquence croissante. Celle-ci n’est pas nécessairement un bloc contigü de la liste initiale mais les entiers apparaissent dans le même ordre.
from jyquickhelper import add_notebook_menu
add_notebook_menu()
L’algorithme optimal est exposé en dernier, la correction propose un cheminement jusqu’à cette solution en introduisant au fur et à mesure les idées qui aboutissent à cette solution. A partir de la première solution, on élague peu à peu :
ce qu’il n’est pas nécessaire de faire car mathématiquement inutile et ne changeant pas la solution,
ce qu’il n’est pas nécessaire de conserver d’une itération à l’autre car cette information peut être reconstruite et qu’il coûte plus cher de la stocker que de la reconstruire.
,
désignent l’élément d’indice
de
l’ensemble
. Sauf précision contraire, il est tenu compte de
l’ordre de tous les éléments dans l’ensemble auxquels ils appartiennent.
Solution simple#
Prenons un tableau quelconque :
E = [10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9]
E
[10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9]
Avant de passer à l’algorithme dichotomique, on va d’abord suivre un
chemin plus facile et plus lent. Supposons qu’on connaît la meilleure
séquence croissante de longueur .
On découpe cette séquence en deux et
. On est sûr que la séquence
est la plus grande séquence croissante
incluant l’élément
. Dans le cas contraire, on aurait trouvé
un moyen de fabriquer une plus longue séquence croissante sur
.
Et c’est contradictoire avec l’hypothèse de départ.
A chaque indice , il existe une meilleure séquence
se terminant à la position
:
est le dernier
élément de la séquence. On suppose que toutes les meilleures séquences
croissantes se terminant à la position
pour
. Comment calculer la meilleure séquence croissante
pour la position
? D’après ce qui précède, il suffit de
l’ajouter à toutes les séquences qui précèdent puis de choisir la
meilleure. Une fois qu’on a obtenu toutes les meilleures séquences se
terminant aux positions
, il suffit de prendre la plus longue.
def plus_grande_sequence_position_k(E, k=None):
if k is None:
k = len(E)-1
if k == 0:
return [[0]]
else :
S = plus_grande_sequence_position_k(E, k-1)
best = []
for j,s in enumerate(S):
if len(s) > len(best) and E[k] >= E [s[-1]]:
best = s
best = best + [k]
S.append(best)
return S
def plus_grande_sequence(E):
if len(E) == 0:
return E
S = plus_grande_sequence_position_k(E)
best = []
for s in S:
if len(s) > len(best):
best = s
return best
b = plus_grande_sequence(E)
"E",E,"indice:",b, "valeurs:", [ E[i] for i in b ]
('E',
[10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9],
'indice:',
[4, 5, 6, 9, 10, 13],
'valeurs:',
[2, 5, 7, 9, 15, 15])
Le coût de cet algorithme est en . L’énoncé de l’exercice
suggère qu’on peut faire mieux en utilisant la dichotomie. En coupant
l’ensemble
en deux,
et
, soit la plus grande séquence croissante
est dans
, soit dans
, soit elle commence avant la
position
et se termine après. Les deux premiers cas sont très
simples à traiter par récurrence. Le dernier l’est moins mais on sait
deux choses : on cherche la séquence
avec
et la recherche de cette séquence doit
avant un coût en
sinon le nouvel algorithme ne sera pas
plus rapide que le précédent.
Solution simple améliorée#
Est-il nécessaire de garder l’historique des séquences ? Pour chaque
position , on conserve toute la meilleure séquence se terminant
à la position
. Toutefois, il est possible de ne retenir que
l’élément précédent :
car la meilleure séquence
peut être décomposée en
. Cette
amélioration rentre dans la catégorie 2 : l’algorithme conserve une
information non indispensable.
La fonction est plus simple à implémenter de façon non récursive. Elle se sert de deux tableaux :
: conserve la longueur de la meilleure séquence se terminant à la position
: conserve la position de l’élément précédent dans la meilleure séquence se terminant à la position
(donc précédent
).
def plus_grande_sequence_2(E):
if len(E) == 0:
return E
precedent = [-1 for e in E]
longueur = [0 for e in E]
longueur[0] = 1
for k in range(1, len(E)):
bestL = 1
bestP = -1
for j in range(0,k) :
if E[k] >= E [ j ] and longueur[j]+1 > bestL:
bestL = longueur [j]+1
bestP = j
precedent[k] = bestP
longueur[k] = bestL
# on récupère la longueur de la plus grande séquence
maxiL = 0
for i,l in enumerate(longueur):
if l > longueur[maxiL]:
maxiL = i
# on récupère la plus grande séquence
seq = [maxiL]
while precedent[seq[-1]] != -1:
p = precedent[seq[-1]]
seq.append(p)
seq.reverse()
return seq
E = [10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9]
b = plus_grande_sequence_2(E)
"E",E,"indice:",b, "valeurs:", [ E[i] for i in b ]
('E',
[10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9],
'indice:',
[4, 5, 6, 9, 10, 13],
'valeurs:',
[2, 5, 7, 9, 15, 15])
On compare les coûts. La seconde fonction est un peu plus rapide à un
facteur multiplicatif près. Le coût des deux fonctions est
.
import random
for n in (20,50,100,200) :
E = [ random.randint(0,n) for i in range(n) ]
print("n=",n)
%timeit plus_grande_sequence(E)
%timeit plus_grande_sequence_2(E)
n= 20
89.9 µs ± 18.2 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
38.8 µs ± 3.08 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
n= 50
324 µs ± 41.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
186 µs ± 21.5 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
n= 100
1.18 ms ± 94 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
653 µs ± 125 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
n= 200
4.86 ms ± 715 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
2.24 ms ± 148 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Un peu plus près de la solution optimale#
La fonction précédente se termine par deux boucles. La première
détermine la longueur de la plus longue séquence, la seconde reconstruit
la séquence. Pour chaque , on conserve la meilleure séquence
croissante se terminant à la position
. Mais supposons que nous
sommes à l’itération
, et pour les positions
,
et que les deux meilleures séquences se terminant aux positions
et
ont même longueur et que
,
est-il vraiment nécessaire de conserver une seconde séquence aussi
longue mais dont le dernier élément est plus grand ?
La réponse est évidemment non. Par extension, à la position ,
on peut classer toutes les séquences se terminant avant :
par longueur décroissante
par dernier élément croissant
Pour chaque longueur, on va conserver le plus petit dernier élément possible parmi toutes les séquences de cette longueur. L’optimisation est deux types : l’algorithme est plus rapide (son coût est plus faible), il stocke moins d’information.
def plus_grande_sequence_2L(E):
if len(E) == 0:
return E
dernier = [0]
precedent = [-1 for e in E]
for k in range(1,len(E)):
if E[k] >= E [dernier [-1]]:
# on ajoute à la dernière séquence
precedent[k] = dernier[-1]
dernier.append( k )
else :
# on s'en sert pour améliorer une séquence existante
for j in range(len(dernier)-1, -1, -1):
if E[k] < E [dernier[j]]:
if precedent[dernier[j]] == -1:
dernier [j] = k
elif E[k] >= E[dernier[j-1]]:
if j == 0:
break
precedent[k] = dernier[j-1]
# ce n'est pas exactement precedent[dernier[j]],
# mais cette valeur est admissible par construction
dernier[j] = k
break # car il ne sert à rien d'aller plus loin
# on récupère la plus grande séquence
seq = [dernier[-1]]
while precedent[seq[-1]] != -1:
p = precedent[seq[-1]]
seq.append(p)
seq.reverse()
return seq
E = [10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9]
b = plus_grande_sequence_2L(E)
"E",E,"indice:",b, "valeurs:", [ E[i] for i in b ]
('E',
[10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9],
'indice:',
[4, 5, 6, 9, 15, 17],
'valeurs:',
[2, 5, 7, 9, 11, 14])
On compare les coûts. La seconde fonction est un peu plus rapide à un
facteur multiplicatif près. Le coût de la première fonction est en
. La seconde est en
où
est la
longueur de la plus longueur séquence. On majore ce coût par
mais dans les faits, c’est plus court.
import random
for n in (20,50,100,200) :
E = [random.randint(0,n) for i in range(n)]
%timeit plus_grande_sequence_2(E)
%timeit plus_grande_sequence_2L(E)
37.9 µs ± 5.51 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
19.3 µs ± 2.62 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
162 µs ± 8.65 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
76.5 µs ± 4.98 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
568 µs ± 25.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
137 µs ± 2.8 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
2.27 ms ± 192 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
357 µs ± 57.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Solution optimale#
Enfin, la solution proposée sur la page wikipedia. Elle consiste simplement à remplacer la boucle imbriquée par une recherche dichotomique. En effet, on cherche le premier élément plus petit qu’un autre dans un tableau trié. Cela peut être aisément remplacé par une recherche dichotomique. Les paragraphes qui suivent reprennent l’explication depuis le début avec les notations de l’article wikipedia.
L’idée consiste à parcourir le tableau de gauche à droite en conservant
à chaque itération des séquences optimales de longueur à
en s’assurant que chaque séquence se termine par le plus petit
entier possible.
L’implémentation s’appuie sur un tableau . La
variable
mémorise la longueur de la plus grande séquence
connue jusque là. A l’itération
,
contient
l’indice du dernier élément de la meilleure séquence croissante de
longueur
dans l’ensemble
.
pour
contient l’indice du
dernier élément d’une séquence de
nombre compris entre les
indices
et
.
A chaque itération , on met à jour le tableau
en
considérant l’élément
. Tout d’abord, si
, cela veut dire qu’on peut ajouter
l’élément
à la plus grande séquence connue, elle sera
nécessairement la plus grande. Si maintenant
,
il n’y aura pas de meilleure séquence. Pour autant, cet élément
remplacera le dernier élément d’une séquence de longueur moindre s’il
est plus petit. On peut aisément comprendre cela : si deux séquences ont
même longueur, celle se terminant par le plus petit élément a plus de
chance de s’agrandir par la suite.
L’algorithme repose sur une propriété du tableau : la suite
est croissante entre
et
. On peut
dire cela autrement : il existe une séquence de longueur
dont le dernier élément est nécessaire plus petit que le dernier élément
de la meilleure séquence de longueur
. Il suffit que prend les
premiers éléments de la meilleure séquence de longueur
.
def plus_grande_sequence_wikipedia(E):
P = [-1 for _ in E]
M = [-1 for _ in E]
L = 0
for i in range(0, len(E)):
lo = 1
hi = L
while lo <= hi:
mid = (lo + hi) // 2
if E[M[mid]] < E[i]:
lo = mid + 1
else:
hi = mid - 1
newL = lo
P[i] = M[newL - 1]
if newL > L:
M[newL] = i
L = newL
elif E[i] < E[M[newL]]:
M[newL] = i
S = [-1 for i in range(L)]
k = M[L]
for i in range(L-1, -1, -1) :
S[i] = k
k = P[k]
return S
E = [10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9]
b = plus_grande_sequence_wikipedia(E)
"E",E,"...","indice:",b, "valeurs:", [ E[i] for i in b ]
('E',
[10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9],
'...',
'indice:',
[4, 5, 6, 9, 15, 17],
'valeurs:',
[2, 5, 7, 9, 11, 14])
On compare avec la version précédente et on vérifie qu’elle est plus rapide.
import random
for n in (20,50,100,200) :
E = [ random.randint(0,n) for i in range(n) ]
print("n=",n)
%timeit plus_grande_sequence_2L(E)
%timeit plus_grande_sequence_wikipedia(E)
n= 20
21.9 µs ± 1.46 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
15.8 µs ± 877 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
n= 50
60.3 µs ± 4.66 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
42.9 µs ± 3.38 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
n= 100
127 µs ± 4.52 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
102 µs ± 9.96 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
n= 200
411 µs ± 42.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
228 µs ± 15 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)