Quelqu'un peut-il me dire pourquoi je reçois un défaut de segmentation dans ce code

Question

Je le teste pour diverses distributions et j'obtiens un défaut de segmentation quand un tableau trié inversé (descendant) est donné en entrée. Parfois cela fonctionne bien même pour un tableau trié inversé et parfois je reçois une erreur de segmentation en particulier sur un grand tableau trié inversé (> 100000). Est-ce en raison d'un appel récursif très profond? Alors, quelle est la limite de la profondeur d'appel récursif, sur quels facteurs cela dépend et quelles précautions doivent être prises en compte lors de l'écriture de programmes récursifs.

Answer 1

Vous avez une erreur de segmentation en raison d'un débordement de pile . Un tableau trié inversement est le pire des cas pour votre schéma de partition: vous recourez n-1 fois sur un tableau d'éléments n.

Vous pouvez essayer d'améliorer le schéma de partition pour éviter ce cas pathologique, mais il existe un moyen d'éviter la récursion profonde dans la fonction quick_sort: sur recurse sur la plus petite moitié et boucle sur la plus grande. Le cas pathologique sera juste très lent mais ne s'écrase plus.

Voici le code:

#include <stdio.h> 
#include <time.h> 

int partition(double *a, int lower, int upper) { 
    /* assuming lower < upper */ 
    int i = lower, j = upper; 
    double t = a[lower], temp; 
    while (i <= j) { 
     while (i <= upper && a[i] <= t) 
      i++; 
     while (a[j] > t) 
      j--; 
     if (i < j) { 
      temp = a[i]; 
      a[i] = a[j]; 
      a[j] = temp; 
     } 
    } 
    temp = a[lower]; 
    a[lower] = a[j]; 
    a[j] = temp; 
    return j; 
} 

void quick_sort(double *a, int lower, int upper) { 
    while (lower < upper) { 
     int j = partition(a, lower, upper); 
     if (j - lower < upper - j) { 
      if (lower < j - 1) { 
       quick_sort(a, lower, j - 1); 
      } 
      lower = j + 1; 
     } else { 
      if (j + 1 < upper) { 
       quick_sort(a, j + 1, upper); 
      } 
      upper = j - 1; 
     } 
    } 
} 

int main(void) { 
    double a[65536]; 
    for (int n = 2; n <= (int)(sizeof(a)/sizeof(*a)); n += n) { 
     for (int i = 0; i < n; i++) { 
      a[i] = n - i; 
     } 
     clock_t t = clock(); 
     quick_sort(a, 0, n - 1); 
     t = clock() - t; 
     for (int i = 1; i < n; i++) { 
      if (a[i - 1] > a[i]) { 
       printf("out of order at %d: %f > %f\n", i - 1, a[i - 1], a[i]); 
       return 1; 
      } 
     } 
     printf("a[%d] sorted in %.3f msec\n", n, (double)t * 1000.0/CLOCKS_PER_SEC); 
    } 
    return 0; 
} 

Sortie:

a[2] sorted in 0.002 msec 
a[4] sorted in 0.001 msec 
a[8] sorted in 0.001 msec 
a[16] sorted in 0.001 msec 
a[32] sorted in 0.000 msec 
a[64] sorted in 0.002 msec 
a[128] sorted in 0.006 msec 
a[256] sorted in 0.021 msec 
a[512] sorted in 0.074 msec 
a[1024] sorted in 0.287 msec 
a[2048] sorted in 1.185 msec 
a[4096] sorted in 5.104 msec 
a[8192] sorted in 19.497 msec 
a[16384] sorted in 78.140 msec 
a[32768] sorted in 297.297 msec 
a[65536] sorted in 1175.032 msec 

En ce qui concerne votre deuxième question, quels facteurs dépend-il et quelles précautions doivent être prises lors de l'écriture des programmes récursifs? il n'y a pas de réponse définitive:

• Les limites de l'espace de la pile (s'il y a un tel concept) sont la mise en œuvre des systèmes spécifiques, différents ont des limites très différentes: de quelques kilo-octets sur les petits systèmes embarqués à plusieurs méga-octets sur de grands systèmes.

• Récurer des milliers de fois est risqué, tout comme la définition de grandes baies avec stockage automatique. Dans le code ci-dessus, je définis un tableau de 64K double, ce n'est pas un problème sur les ordinateurs modernes à usage général, mais pourrait être trop sur un petit capteur numérique. Le niveau de récursivité maximale avec la recurse sur la plus petite moitié approche est délimitée par log (N), qui est seulement 16 pour N=65536, devrait être OK pour tous les systèmes.

Answer 2

Oui, la segmentation est due à des récursions trop profondes.

Lorsque vous avez un tableau inversé pour être rapide triée dans votre fonction, la t dans la fonction partation serait toujours la plus grande ou la plus petite valeur dans le domaine que vous utilisez toujours a[lower] comme la valeur de t. Cela signifie que la valeur de retour de partation sera toujours égale à upper ou «inférieure» lorsque le tableau est inversé. Cela conduit à un nombre total de récursions (supérieures - inférieures) et entraînerait sûrement une erreur. Pour éviter cela, utilisez une valeur aléatoire entre upper et lower au lieu d'utiliser toujours a[lower] comme valeur de t

#include <stdlib.h> 
#include <time.h> 

int partation(double *a, int lower, int upper) 
{ 
    int i = lower, j = upper; 
    double t = a[rand() % (upper - lower) + lower], temp; 
    while (i <= j) 
    { 
     while (i <= upper&&a[i] <= t) i++; 
     while (a[j]>t) j--; 
     if (i <= j) 
     { 
      temp = a[i]; a[i] = a[j]; a[j] = temp; 
     } 
    } 
    temp = a[lower]; 
    a[lower] = a[j]; 
    a[j] = temp; 
    return j; 

} 

void quick_sort(double *a, int lower, int upper) 
{ 
    int j; 
    if (lower >= upper) return; 
    else 
    { 
     j = partation(a, lower, upper); 
     quick_sort(a, lower, j - 1); 
     quick_sort(a, j + 1, upper); 
    } 
} 

int main() 
{ 
    srand(time(0)); 
    /*input the value of a here*/ 
    /*double a[10000]; 
    for (int i = 10000 - 1, index = 0; --i;++index) 
    { 
     a[index] = i; 
    }*/ 
    quick_sort(a, 0, 9999); 
    return 0; 
}