La sous-séquence de plus grande somme¶
Ce problème est connu sur le nom de Maximum subarray problem. Notion abordée : programmation dynamique.
[1]:
%matplotlib inline
Enoncé¶
On suppose qu’on a une liste \(L=( l_1, l_2, ..., l_n)\). On souhaite trouver la sous-séquence de plus grande somme. En d’autres termes, on veut trouver \((i^*,j^*)\) tels que :
\(\sum_{k=i^*}^{j^*} l_k = \max_{i,j} \sum_{k=i}^{j} l_k\)
Solution naïve¶
La première solution consiste à calculer les sommes de toutes les sous-séquences et de garder les \(i,j\) qui ont permis d’obtenir la meilleure sous-séquence. On divise le programme en deux fonctions :
somme_partielle
: calcule la somme de la sous-séquencel[i:j]
(coût de la fonction : \(O(n)\))plus_grande_sous_liste
: passe en revue toutes les sous-séquences et retourne la meilleure (coût de la fonction \(O(n^2)\))
Le coût de cet algorithme est en \(O(n^3)\).
[2]:
def somme_partielle(li, i, j):
r = 0
for a in range(i, j):
r += li[a]
return r
# on pourrait juste écrire
# return sum(li[i:j])
def plus_grande_sous_liste(li):
meilleur = min(li) # ligne A
im, jm = -1, -1
for i in range(0, len(li)):
for j in range(i + 1, len(li) + 1): # ne pas oublier +1 car sinon
# le dernier élément n'est jamais pris en compte
s = somme_partielle(li, i, j)
if s > meilleur:
meilleur = s
im, jm = i, j
return li[im:jm]
# si li ne contient que des valeurs positives, la solution est évidemment la liste entière
# c'est pourquoi il faut tester cette fonction avec des valeurs négatives
li = [4, -6, 7, -1, 8, -50, 3]
m = plus_grande_sous_liste(li)
m
[2]:
[7, -1, 8]
La ligne A contient l’instruction meilleur = min(li)
. Pour une liste où tous les nombres sont négatifs, la meilleure sous-liste est constitué du plus petit élément de la liste. Remplacer cette instruction par meilleur = 0
a pour conséquence de retourner une liste vide dans ce cas précis.
\(cout(n) = \sum_{i=0}^n \sum_{j=i+1}^n j-i = \sum_{i=0}^n \sum_{j=0}^i j = \sum_{i=0}^n \frac{i(i+1)}{2} \sim O(n^3)\)
Solution plus rapide¶
Il est possible de modifier cette fonction de telle sorte que le coût soit en \(O(n^2)\) car on évite la répétition de certains calculs lors du calcul de la somme des sous-séquences. On peut écrire :
\(\sum_{k=i}^{j+1} l_k = l_j + \sum_{k=i}^{j} l_k\)
Dans la seconde boucle, il suffit d’ajouter l’élément li[j]
à la somme précédente.
[3]:
def plus_grande_sous_liste_n2(li):
meilleur = 0
im, jm = -1, -1
for i in range(0, len(li)):
s = 0
for j in range(i, len(li)):
s += li[j]
if s > meilleur:
meilleur = s
im, jm = i, j + 1
return li[im:jm]
li = [4, -6, 7, -1, 8, -50, 3]
m = plus_grande_sous_liste_n2(li)
print(m)
li = [1, 2, 3, 4, 5, -98, 78, 9, 7, 7]
m = plus_grande_sous_liste_n2(li)
print(m)
li = [0, 2, 4, -7, -2, 7, -1, 8, -10, 3]
m = plus_grande_sous_liste_n2(li)
m
[7, -1, 8]
[78, 9, 7, 7]
[3]:
[7, -1, 8]
Solution dichotomique¶
Il existe une dernière version plus rapide encore. Si on considère la liste \(L=(l_1, ..., l_n)\) dont on cherche à extraire la sous-séquence de somme maximale. Supposons que \(l_a\) appartienne à cette sous-séquence. On construit la fonction suivante :
\(f(a,k) =\left \{ \begin{array}{ll} \sum_{i=a}^{k} l_i &si \; k > a \\ \sum_{i=k}^{a} l_i &si \; k < a \end{array} \right .\)
On cherche alors les valeurs \(k_1\) et \(k_2\) telles que :
\(\begin{array}{rcl} f(a,k_1) &=& \max_{k<a} f(a,k) \\ f(a,k_2) &=& \max_{k>a} f(a,k) \end{array}\)
La sous-séquence de somme maximale cherchée est \([k_1,k_2]\) avec \(a\) dans cet intervalle et le coût de cette recherche est en \(O(n)\). Mais ceci n’est vrai que si on sait que \(l_a\) appartient à la sous-séquence de somme maximale.
Autre considération : pour deux listes \(l_1\) et \(l_2\), la séquence maximale de la réunion des deux appartient soit à l’une, soit à l’autre, soit elle inclut le point de jonction.
Ces deux idées mises bout à bout donne l’algorithme suivant construit de façon récursive. On coupe la liste en deux parties de longueur égale :
On calcule la meilleure séquence sur la première sous-séquence.
On calcule la meilleure séquence sur la seconde sous-séquence.
On calcule la meilleure séquence en suppose que l’élément du milieu appartient à cette séquence.
La meilleure séquence est nécessairement l’une des trois.
[4]:
def plus_grande_sous_liste_nlnn2_r(li, i, j):
if i == j:
return 0
elif i + 1 == j:
return li[i], i, i + 1
milieu = (i + j) // 2
# on coupe le problème deux
ma, ia, ja = plus_grande_sous_liste_nlnn2_r(li, i, milieu)
mb, ib, jb = plus_grande_sous_liste_nlnn2_r(li, milieu, j)
# pour aller encore plus vite dans un cas précis
if ja == ib:
total = ma + mb
im, jm = ia, jb
else:
# on étudie la jonction
im, jm = milieu, milieu + 1
meilleur = li[milieu]
s = meilleur
for k in range(milieu + 1, j):
s += li[k]
if s > meilleur:
meilleur = s
jm = k + 1
total = meilleur
meilleur = li[milieu]
s = meilleur
for k in range(milieu - 1, i - 1, -1):
s += li[k]
if s > meilleur:
meilleur = s
im = k
total += meilleur - li[milieu]
if ma >= max(mb, total):
return ma, ia, ja
elif mb >= max(ma, total):
return mb, ib, jb
else:
return total, im, jm
def plus_grande_sous_liste_nlnn2(li):
m, i, j = plus_grande_sous_liste_nlnn2_r(li, 0, len(li))
return li[i:j]
li = [4, -6, 7, -1, 8, -50, 3]
m = plus_grande_sous_liste_nlnn2(li)
print(m)
li = [1, 2, 3, 4, 5, -98, 78, 9, 7, 7]
m = plus_grande_sous_liste_nlnn2(li)
print(m)
li = [0, 2, 4, -7, -2, 7, -1, 8, -10, 3]
m = plus_grande_sous_liste_nlnn2(li)
m
[7, -1, 8]
[78, 9, 7, 7]
[4]:
[7, -1, 8]
Le coût de cette fonction est au pire en \(O(n \ln n)\). A chaque itération, on effectue trois calculs :
meilleure séquence à droite : \(f(n/2)\)
meilleure séquence à gauche : \(f(n/2)\)
meilleure séquence incluant \(a\) : \(n\)
Le coût de l’iteration \(n\) est \(f(n)=n + 2f(n/2)\) avec \(f(1)=0\). On calcule les premières termes :
[5]:
cout = lambda n: 0 if n == 1 else n + 2 * cout(n // 2)
for i in range(1, 10):
print("f({0})={1} --> f({0})/{0} = {2}".format(2**i, cout(2**i), cout(2**i) / 2**i))
f(2)=2 --> f(2)/2 = 1.0
f(4)=8 --> f(4)/4 = 2.0
f(8)=24 --> f(8)/8 = 3.0
f(16)=64 --> f(16)/16 = 4.0
f(32)=160 --> f(32)/32 = 5.0
f(64)=384 --> f(64)/64 = 6.0
f(128)=896 --> f(128)/128 = 7.0
f(256)=2048 --> f(256)/256 = 8.0
f(512)=4608 --> f(512)/512 = 9.0
On suppose que \(f(2^n)=n2^n \Leftrightarrow f(n) = n \ln_2 n\). Il suffit de vérifier cela avec la récurrence :
\(\begin{array}{rcl} f(n) &=& n + 2f(\frac{n}{2}) = n + 2 \frac{n}{2} \ln_2(\frac{n}{2}) \\ &=& n + n \ln_2(n) - n\ln_2(2) = n + n\ln_2(n) - n = n\ln_2 n\end{array}\)
C’est le coût d’une itération. Comme à chaque itération on coupe le problème en deux, le coût total de l’algorithme est :
\(\begin{array}{rcl} C(2^n) &=& f(2^n) + 2f(2^{n-1}) + 4f(2^{n-2}) + ... + 2^{n-1}f(2) = \sum_{k=1}^{n} 2^{n-k} f(2^k) \\ &=& \sum_{k=1}^n 2^{n-k} 2^k k = \sum_{k=1}^n 2^n k = 2^{n-1}n(n-1) \leqslant 2^{n-1} n^2 \end{array}\)
Par conséquent, le coût est en \(C(n) \sim O(n \ln^2 n)\).
Solution linéaire¶
La dernière solution est la plus rapide. Elle consiste à parcourir la liste dans le sens croissant des indices et à construire la série cumulée.
[6]:
import matplotlib.pyplot as plt
li = [0, 2, 4, -7, -2, 7, -1, 8, -10, 3]
cumul = [li[0]]
for i in li[1:]:
cumul.append(cumul[-1] + i)
cumul2 = [li[0]]
for i in li[1:]:
cumul2.append(max(cumul2[-1] + i, 0))
plt.plot(cumul, label="cumul")
plt.plot(cumul2, label="cumul2")
plt.plot([0 for c in cumul])
plt.legend()
plt.title("somme cumulée");
La courbe devient négative au quatrième nombre. L’astuce consiste à dire qu’on peut traiter les deux ensembles séparément et que la meilleure sous-séquence n’inclura pas ce nombre en quatrième position. Si on cherche la meilleure sous-séquence se terminant à la position \(i\), il suffit juste de revenir en arrière et de trouver le minimum de la courbe cumulée avant la position \(i\). Pour \(i=5\), le point le plus bas qui précède est le point \(k=3\). Au point \(i=3\), on sait qu’il n’existe pas de sous-séquence positive précédent \(i=3\).
On découpe la courbe en segments \([[i,j]]\) vérifiant \(l_{i-1} < 0 \leqslant l_i\) et \(\sum_{k=1}^{j} l_k < 0\) et \(l_{j+1} \geqslant 0\).
[7]:
from IPython.core.display import Image
Image("sommemax.png")
[7]:
On parcourt la série cumulée. A chaque fois qu’on passe sous zéro, au premier nombre positif suivant, on redémarre à zéro. La sous-séquence de somme maximale est forcément dans un de ces tronçons, elle a pour point de départ le premier élément et pour point d’arrivée le maximum obtenu sur le tronçon en question : pour chaque point \(x,Cumul2(x)\) d’un tronçon, le minimum de la courbe cumulée précédent \(x\) est nécessairement le premier élément du tronçon.
[8]:
def plus_grande_sous_liste_n(li):
meilleur = [None for i in li]
somme = [None for i in li]
best = None
for i, el in enumerate(li):
if el >= 0:
if i > 0:
somme[i] = max(somme[i - 1], 0) + el
meilleur[i] = meilleur[i - 1] if somme[i - 1] >= 0 else i
else:
somme[i] = el
meilleur[i] = i
if best is None or somme[i] > somme[best]:
best = i
else:
somme[i] = (somme[i - 1] + el) if i > 0 else el
if somme[i] >= 0:
meilleur[i] = meilleur[i - 1]
i, j = meilleur[best], best + 1
return li[i:j]
li = [4, -6, 7, -1, 8, -10, 3]
m = plus_grande_sous_liste_n(li)
print(m) # affiche [7, -1, 8]
li = [1, 2, 3, 4, 5, -98, 78, 9, 7, 7]
m = plus_grande_sous_liste_n(li)
print(m)
li = [0, 2, 4, -7, -2, 7, -1, 8, -10, 3]
m = plus_grande_sous_liste_n(li)
m
[7, -1, 8]
[78, 9, 7, 7]
[8]:
[7, -1, 8]
Comparaison des temps de calcul¶
On effectue cela sur une liste de nombres aléatoire négatifs et positifs.
[9]:
import random
li100 = [random.randint(-10, 50) for i in range(0, 100)]
Coût en \(O(n^3)\) :
[10]:
%timeit plus_grande_sous_liste(li100)
15.6 ms ± 1.19 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)
Coût en \(O(n^2)\) :
[11]:
%timeit plus_grande_sous_liste_n2(li100)
565 µs ± 33.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
Coût en \(O(n \ln^2 n)\) :
[12]:
%timeit plus_grande_sous_liste_nlnn2(li100)
134 µs ± 12.9 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Coût en \(O(n)\) :
[13]:
%timeit plus_grande_sous_liste_n(li100)
70.9 µs ± 3.32 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Application¶
Le drawdown est un indicateur de performance pour les systèmes de trading. Il mesure la perte maximale enregistrée sur une période. En d’autres, il correspond à la sous-séquence de somme minimale. On vient de montrer qu’il n’est pas plus long à calculer qu’une moyenne.
[ ]: