.. _exerciceplusgrandesommerst: =============================================== 1A.algo - La sous-séquence de plus grande somme =============================================== .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/1a/exercice_plus_grande_somme.ipynb|*` Ce problème est connu sur le nom de `Maximum subarray problem `__. Notion abordée : programmation dynamique. .. code:: ipython3 %matplotlib inline .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: Enoncé ~~~~~~ On suppose qu’on a une liste :math:`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 :math:`(i^*,j^*)` tels que : :math:`\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 :math:`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équence ``l[i:j]`` (coût de la fonction : :math:`O(n)`) - ``plus_grande_sous_liste`` : passe en revue toutes les sous-séquences et retourne la meilleure (coût de la fonction :math:`O(n^2)`) Le coût de cet algorithme est en :math:`O(n^3)`. .. code:: ipython3 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 .. parsed-literal:: [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. :math:`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 :math:`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 : :math:`\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. .. code:: ipython3 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 .. parsed-literal:: [7, -1, 8] [78, 9, 7, 7] .. parsed-literal:: [7, -1, 8] Solution dichotomique ~~~~~~~~~~~~~~~~~~~~~ Il existe une dernière version plus rapide encore. Si on considère la liste :math:`L=(l_1, ..., l_n)` dont on cherche à extraire la sous-séquence de somme maximale. Supposons que :math:`l_a` appartienne à cette sous-séquence. On construit la fonction suivante : :math:`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 :math:`k_1` et :math:`k_2` telles que : :math:`\begin{array}{rcl} f(a,k_1) &=& \max_{ka} f(a,k) \end{array}` La sous-séquence de somme maximale cherchée est :math:`[k_1,k_2]` avec :math:`a` dans cet intervalle et le coût de cette recherche est en :math:`O(n)`. Mais ceci n’est vrai que si on sait que :math:`l_a` appartient à la sous-séquence de somme maximale. Autre considération : pour deux listes :math:`l_1` et :math:`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. .. code:: ipython3 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 .. parsed-literal:: [7, -1, 8] [78, 9, 7, 7] .. parsed-literal:: [7, -1, 8] Le coût de cette fonction est au pire en :math:`O(n \ln n)`. A chaque itération, on effectue trois calculs : - meilleure séquence à droite : :math:`f(n/2)` - meilleure séquence à gauche : :math:`f(n/2)` - meilleure séquence incluant :math:`a` : :math:`n` Le coût de l’iteration :math:`n` est :math:`f(n)=n + 2f(n/2)` avec :math:`f(1)=0`. On calcule les premières termes : .. code:: ipython3 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)) .. parsed-literal:: 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 :math:`f(2^n)=n2^n \Leftrightarrow f(n) = n \ln_2 n`. Il suffit de vérifier cela avec la récurrence : :math:`\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 : :math:`\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 :math:`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. .. code:: ipython3 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"); .. image:: exercice_plus_grande_somme_15_0.png 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 :math:`i`, il suffit juste de revenir en arrière et de trouver le minimum de la courbe cumulée avant la position :math:`i`. Pour :math:`i=5`, le point le plus bas qui précède est le point :math:`k=3`. Au point :math:`i=3`, on sait qu’il n’existe pas de sous-séquence positive précédent :math:`i=3`. On découpe la courbe en segments :math:`[[i,j]]` vérifiant :math:`l_{i-1} < 0 \leqslant l_i` et :math:`\sum_{k=1}^{j} l_k < 0` et :math:`l_{j+1} \geqslant 0`. .. code:: ipython3 from IPython.core.display import Image Image("sommemax.png") .. image:: exercice_plus_grande_somme_17_0.png 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 :math:`x,Cumul2(x)` d’un tronçon, le minimum de la courbe cumulée précédent :math:`x` est nécessairement le premier élément du tronçon. .. code:: ipython3 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 .. parsed-literal:: [7, -1, 8] [78, 9, 7, 7] .. parsed-literal:: [7, -1, 8] Comparaison des temps de calcul ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ On effectue cela sur une liste de nombres aléatoire négatifs et positifs. .. code:: ipython3 import random li100 = [random.randint(-10, 50) for i in range(0,100)] Coût en :math:`O(n^3)` : .. code:: ipython3 %timeit plus_grande_sous_liste(li100) .. parsed-literal:: 14.4 ms ± 1.12 ms per loop (mean ± std. dev. of 7 runs, 100 loops each) Coût en :math:`O(n^2)` : .. code:: ipython3 %timeit plus_grande_sous_liste_n2(li100) .. parsed-literal:: 519 µs ± 58 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) Coût en :math:`O(n \ln^2 n)` : .. code:: ipython3 %timeit plus_grande_sous_liste_nlnn2(li100) .. parsed-literal:: 146 µs ± 16.9 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) Coût en :math:`O(n)` : .. code:: ipython3 %timeit plus_grande_sous_liste_n(li100) .. parsed-literal:: 68.2 µs ± 8.44 µs per loop (mean ± std. dev. of 7 runs, 10000 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.