L'algorithme Thêta (n ** 2) et Thêta (n * lgn) ne fonctionnent pas correctement

Question

Je suis en train de lire l'introduction aux algorithmes et d'essayer de terminer l'exercice dans le livre.

Dans l'exercice 4.1-3

4.1-3 Mettre en œuvre à la fois la force brute et les algorithmes récursifs pour le problème maximal sur votre propre sous-tableau ordinateur. Quelle taille de problème n0 donne le point de croisement auquel l'algorithme récursif bat l'algorithme de force brute? Ensuite, changez le cas de base de l'algorithme récursif pour utiliser l'algorithme de force brute chaque fois que la taille du problème est inférieure à n0. Cela change-t-il le point de croisement?

j'ai écrit les deux algorithmes selon pseudo-code du livre. Cependant, il doit y avoir quelque chose qui ne va pas avec mon code parce que le second, qui est conçu pour être Theta (n * lgn) et supposé courir plus vite, est toujours plus lent que le premier Theta (n ** 2). Mes codes sont indiqués ci-dessous.

 

def find_maximum_subarray_bf(a):  #bf for brute force 
    p1 = 0 
    l = 0   # l for left 
    r = 0   # r for right 
    max_sum = 0 
    for p1 in range(len(a)-1): 
     sub_sum = 0 
     for p2 in range(p1, len(a)): 
      sub_sum += a[p2] 
      if sub_sum > max_sum: 
       max_sum = sub_sum 
       l = p1 
       r = p2 
    return l, r, max_sum 

def find_maximum_subarray_dc(a):  #dc for divide and conquer 

    # subfunction 
    # given an arrary and three indics which can split the array into a[l:m] 
    # and a[m+1:r], find out a subarray a[i:j] where l \leq i \less m \less j \leq r". 
    # according to the definition above, the target subarray must 
    # be combined by two subarray, a[i:m] and a[m+1:j] 
    # Growing Rate: theta(n) 

    def find_crossing_max(a, l, r, m): 

     # left side 
     # ls_r and ls_l indicate the right and left bound of the left subarray. 
     # l_max_sum indicates the max sum of the left subarray 
     # sub_sum indicates the sum of the current computing subarray  
     ls_l = 0 
     ls_r = m-1 
     l_max_sum = None 
     sub_sum = 0 
     for j in range(m+1)[::-1]:  # adding elements from right to left 
      sub_sum += a[j] 
      if sub_sum > l_max_sum: 
       l_max_sum = sub_sum 
       ls_l = j 

     # right side 
     # rs_r and rs_l indicate the right and left bound of the left subarray. 
     # r_max_sum indicates the max sum of the left subarray 
     # sub_sum indicates the sum of the current computing subarray     
     rs_l = m+1 
     rs_r = 0 
     r_max_sum = None 
     sub_sum = 0 
     for j in range(m+1,len(a)): 
      sub_sum += a[j] 
      if sub_sum > r_max_sum: 
       r_max_sum = sub_sum 
       rs_r = j 

     #combine 
     return (ls_l, rs_r, l_max_sum+r_max_sum) 

    # subfunction 
    # Growing Rate: should be theta(nlgn), but there is something wrong 
    def recursion(a,l,r):   # T(n) 
     if r == l: 
      return (l,r,a[l]) 
     else: 
      m = (l+r)//2     # theta(1) 
      left = recursion(a,l,m)   # T(n/2) 
      right = recursion(a,m+1,r)  # T(n/2) 
      crossing = find_crossing_max(a,l,r,m) # theta(n) 

      if left[2]>=right[2] and left[2]>=crossing[2]: 
       return left 
      elif right[2]>=left[2] and right[2]>=crossing[2]: 
       return right 
      else: 
       return crossing 

    #back to master function 
    l = 0 
    r = len(a)-1 
    return recursion(a,l,r) 

if __name__ == "__main__": 

    from time import time 

    a = [100,-10,1,2,-1,4,-6,2,5] 
    a *= 2**10 

    time0 = time() 
    find_maximum_subarray_bf(a) 
    time1 = time() 
    find_maximum_subarray_dc(a) 
    time2 = time() 
    print "function 1:", time1-time0 
    print "function 2:", time2-time1 
    print "ratio:", (time1-time0)/(time2-time1) 

Answer 1

D'abord, une erreur dans la force brute:

for p1 in range(len(a)-1): 

qui devrait être range(len(a)) [ou xrange], tel qu'il est, il ne trouverait pas le sous-tableau maximum de [-12,10].

Maintenant, la récursion:

def find_crossing_max(a, l, r, m): 

    # left side 
    # ls_r and ls_l indicate the right and left bound of the left subarray. 
    # l_max_sum indicates the max sum of the left subarray 
    # sub_sum indicates the sum of the current computing subarray  
    ls_l = 0 
    ls_r = m-1 
    l_max_sum = None 
    sub_sum = 0 
    for j in range(m+1)[::-1]:  # adding elements from right to left 

Vous regardez tous les indices à 0, mais vous ne devriez vérifier les indices à l. Au lieu de construire la liste range et d'inverser, utilisez xrange(m,l-1,-1)

 sub_sum += a[j] 
     if sub_sum > l_max_sum: 
      l_max_sum = sub_sum 
      ls_l = j 

Pour la somme à droite, l'analogue de paiement, vous ne devriez vérifier les indices à r, donc xrange(m+1,r+1).

En outre, vos valeurs initiales pour les sommes resp. les indices pour le sous-tableau maximum sont douteux pour la partie gauche, et faux pour la partie droite.

Pour la partie gauche, nous commençons avec une somme vide mais doit inclure a[m]. Cela peut être fait en définissant initialement l_max_sum = None ou en définissant l_max_sum = a[m] et en laissant j omettre l'index m. De toute façon, la valeur initiale pour ls_l ne devrait pas être 0, et pour ls_r, elle ne devrait pas être m-1. ls_r doit être m et ls_l devrait commencer m+1 si la valeur initiale est l_max_sumNone, et comme m si l_max_sum commence comme a[m].

Pour la partie droite, r_max_sum doit commencer par 0, et rs_r devrait commencer par m (bien que ce ne soit pas vraiment important, cela ne vous donnerait que les mauvais index). Si aucune des sommes à droite n'est jamais négative, la bonne somme doit être 0 et non la plus grande des sommes négatives.

En recursion, nous avons un peu de double emploi dans

left = recursion(a,l,m)   # T(n/2) 

les sommes dont a[m] ont déjà été traités ou majorée dans find_crossing_max, de sorte que pourrait être

left = recursion(a,l,m-1) 

Mais il faudrait pour traiter également la possibilité r < l en recursion, et la répétition est petite, donc je vais laisser cela.

Étant donné que vous parcourez toujours la totalité de la liste dans find_crossing_max, et que vous l'appelez O(n) fois, votre implémentation de diviser pour régner est en réalité O(n²).

Si la plage cochée dans find_crossing_max est limitée à [l,r], comme il devrait être, vous avez (environ) 2^k appels sur les plages de longueur n/2^k, 0 <= k <= log_2 n, pour un coût total de O(n*log n).

Avec ces changements (et une génération de réseau aléatoire),

def find_maximum_subarray_bf(a):  #bf for brute force 
    p1 = 0 
    l = 0   # l for left 
    r = 0   # r for right 
    max_sum = 0 
    for p1 in xrange(len(a)): 
     sub_sum = 0 
     for p2 in xrange(p1, len(a)): 
      sub_sum += a[p2] 
      if sub_sum > max_sum: 
       max_sum = sub_sum 
       l = p1 
       r = p2 
    return l, r, max_sum 

def find_maximum_subarray_dc(a):  #dc for divide and conquer 

    # subfunction 
    # given an arrary and three indices which can split the array into a[l:m] 
    # and a[m+1:r], find out a subarray a[i:j] where l \leq i \less m \less j \leq r". 
    # according to the definition above, the target subarray must 
    # be combined by two subarray, a[i:m] and a[m+1:j] 
    # Growing Rate: theta(n) 

    def find_crossing_max(a, l, r, m): 

     # left side 
     # ls_r and ls_l indicate the right and left bound of the left subarray. 
     # l_max_sum indicates the max sum of the left subarray 
     # sub_sum indicates the sum of the current computing subarray  
     ls_l = m+1 
     ls_r = m 
     l_max_sum = None 
     sub_sum = 0 
     for j in xrange(m,l-1,-1):  # adding elements from right to left 
      sub_sum += a[j] 
      if sub_sum > l_max_sum: 
       l_max_sum = sub_sum 
       ls_l = j 

     # right side 
     # rs_r and rs_l indicate the right and left bound of the left subarray. 
     # r_max_sum indicates the max sum of the left subarray 
     # sub_sum indicates the sum of the current computing subarray     
     rs_l = m+1 
     rs_r = m 
     r_max_sum = 0 
     sub_sum = 0 
     for j in range(m+1,r+1): 
      sub_sum += a[j] 
      if sub_sum > r_max_sum: 
       r_max_sum = sub_sum 
       rs_r = j 

     #combine 
     return (ls_l, rs_r, l_max_sum+r_max_sum) 

    # subfunction 
    # Growing Rate: theta(nlgn) 
    def recursion(a,l,r):   # T(n) 
     if r == l: 
      return (l,r,a[l]) 
     else: 
      m = (l+r)//2     # theta(1) 
      left = recursion(a,l,m)   # T(n/2) 
      right = recursion(a,m+1,r)  # T(n/2) 
      crossing = find_crossing_max(a,l,r,m) # theta(r-l+1) 

      if left[2]>=right[2] and left[2]>=crossing[2]: 
       return left 
      elif right[2]>=left[2] and right[2]>=crossing[2]: 
       return right 
      else: 
       return crossing 

    #back to master function 
    l = 0 
    r = len(a)-1 
    return recursion(a,l,r) 

if __name__ == "__main__": 

    from time import time 
    from sys import argv 
    from random import randint 
    alen = 100 
    if len(argv) > 1: 
     alen = int(argv[1]) 
    a = [randint(-100,100) for i in xrange(alen)] 

    time0 = time() 
    print find_maximum_subarray_bf(a) 
    time1 = time() 
    print find_maximum_subarray_dc(a) 
    time2 = time() 
    print "function 1:", time1-time0 
    print "function 2:", time2-time1 
    print "ratio:", (time1-time0)/(time2-time1) 

Nous obtenons quelque chose comme nous devrions nous attendre:

$ python subarrays.py 50 
(3, 48, 1131) 
(3, 48, 1131) 
function 1: 0.000184059143066 
function 2: 0.00020382 
ratio: 0.902923976608 
$ python subarrays.py 100 
(29, 61, 429) 
(29, 61, 429) 
function 1: 0.000745058059692 
function 2: 0.000561952590942 
ratio: 1.32583792957 
$ python subarrays.py 500 
(35, 350, 3049) 
(35, 350, 3049) 
function 1: 0.0115859508514 
function 2: 0.00170588493347 
ratio: 6.79175401817 
$ python subarrays.py 1000 
(313, 572, 3585) 
(313, 572, 3585) 
function 1: 0.0537149906158 
function 2: 0.00334000587463 
ratio: 16.082304233 
$ python osubarrays.py 10000 
(901, 2055, 4441) 
(901, 2055, 4441) 
function 1: 4.20316505432 
function 2: 0.0381460189819 
ratio: 110.186204655