Comment empêcher le débordement de la pile lors de l'utilisation du tri par fusion sur de grandes quantités de données?

Question

J'ai l'algorithme de tri de fusion suivant qui fonctionne lorsque je teste avec 100, 1000 ou 10000 longues listes chaînées. Toutefois, il renvoie une erreur de segmentation sur la ligne contenant Node->Next=Merge(Front,Back->Next,Type); lors de l'utilisation de 100 000 ou des listes liées long 1000000. Cela m'a amené à croire que c'est un débordement de pile plutôt qu'un défaut de segmentation. Selon gdb au moment de l'erreur, la pile est extraordinairement pleine. Je ne peux pas trouver un moyen d'examiner exactement combien d'éléments sont dans la pile d'appels pour donner un chiffre exact. Toute aide avec le tri de fusion de retravailler pour gérer de grandes quantités de données serait grandement appréciée.

struct IntList 
{ 
int Value; 
int Frequency; 
struct IntList* Next; 
struct IntList* Prev; 
};//Struct for Integer Linked List 
void SortList(struct IntList** Values,enum SortBy Type) 
{ 
    struct IntList* Head = *Values; 
    if(Head==NULL||Head->Next==NULL) 
    { 
     return; 
    }//If Base Case 
    struct IntList* Front; 
    struct IntList* Back; 
    Split(Head,&Front,&Back);//Splits Linked List 
    SortList(&Front,Type); 
    SortList(&Back,Type);//Recursively Sorts 
    *Values=Merge(Front,Back,Type);//Merges Halves 
    return; 
} 

void Split(struct IntList* Head,struct IntList** Front,struct IntList** Back) 
{ 
    struct IntList* Fast; 
    struct IntList* Slow; 
    if (Head==NULL||Head->Next==NULL) 
    { 
     *Front=Head; 
     *Back=NULL; 
    }//If Length <2 
    else 
    { 
     Slow=Head; 
     Fast=Head->Next; 
    } 
    while(Fast!=NULL) 
    { 
     Fast=Fast->Next; 
     if(Fast!=NULL) 
     { 
      Fast=Fast->Next; 
      Slow=Slow->Next; 
     } 
    }//Find Midpoint 
    *Front=Head; 
    *Back=Slow->Next; 
    Slow->Next=NULL;//Breaks Link 
    return; 
} 


struct IntList* Merge(struct IntList* Front,struct IntList* Back,enum SortBy Type) 
{ 
    if(Front==NULL) 
    { 
     return Back; 
    } 
    if (Back==NULL) 
    { 
     return Front; 
    }//Base Cases 

    struct IntList* Node; 
    if(Type==DATA) 
    { 
     if(Front->Value <= Back->Value) 
     { 
      Node=Front; 
      Node->Next=Merge(Front->Next,Back,Type); 
     } 
     else 
     { 
      Node=Back; 
      Node->Next=Merge(Front,Back->Next,Type); 
     }//Takes Greatest Value for Sorted List 
    }//If Sorting by Data 
    if(Type==FREQUENCY) 
    { 
     if(Front->Frequency < Back->Frequency) 
     { 
      Node=Front; 
      Node->Next=Merge(Front->Next,Back,Type); 
     } 
     else 
     { 
      Node=Back; 
      Node->Next=Merge(Front,Back->Next,Type); 
     }//Takes Greatest Frequency for Sorted List 
    }//If Sorting by Frequency 
    return(Node); 

Answer 1

Si vous souhaitez utiliser la récursivité, il est préférable d'essayer de l'exprimer sous la forme d'un appel de fin (de sorte que rien ne soit fait après l'appel récursif autre qu'un retour). De cette façon, la plupart des compilateurs optimisent l'appel de queue dans un simple saut et n'utilisent pas d'espace de pile. Pour votre fonction Merge, il devient quelque chose comme:

void Merge(struct IntList **merged, struct IntList* Front,struct IntList* Back,enum SortBy Type) 
{ 
    if(Front==NULL) { 
     *merged = Back; 
    } else if (Back==NULL) { 
     *merged = Front; 
    } else if(Type==DATA) { 
     if(Front->Value <= Back->Value) { 
      *merged = Front; 
      Merge(&Front->Next, Front->Next, Back, Type); 
     } else { 
      *merged = Back; 
      Merge(&Back->Next, Front, Back->Next,Type); 
     }//Takes Greatest Value for Sorted List if Sorting by Value 
    } else if(Type==FREQUENCY) { 
     if(Front->Frequency < Back->Frequency) { 
      *merged = Front; 
      Merge(&Front->next, Front->Next, Back, Type); 
     } else { 
      *merged = Back; 
      Merge(&Back->Next, Front, Back->Next, Type); 
     }//Takes Greatest Frequency for Sorted List 
    }//If Sorting by Frequency 
} 

Si votre compilateur ne prend pas en charge l'optimisation de récursion arrière, vous pouvez le faire vous-même en faisant le corps de la fonction boucle:

void Merge(struct IntList **merged, struct IntList* Front,struct IntList* Back,enum SortBy Type) 
{ 
    while(Front || Back) { 
    if(Front==NULL) { 
     *merged = Back; 
     Back = NULL; 
    } else if (Back==NULL) { 
     *merged = Front; 
     Front = NULL 
    } else if(Type==DATA) { 
     if(Front->Value <= Back->Value) { 
      *merged = Front; 
      merged = &Front->Next; 
      Front = Front->Next; 
     } else { 
      *merged = Back; 
      merged = &Back->Next; 
      Back = Back->Next; 
     }//Takes Greatest Value for Sorted List if Sorting by Value 
    } else if(Type==FREQUENCY) { 
     if(Front->Frequency < Back->Frequency) { 
      *merged = Front; 
      merged = &Front->Next; 
      Front = Front->Next; 
     } else { 
      *merged = Back; 
      merged = &Back->Next; 
      Back = Back->Next; 
     }//Takes Greatest Frequency for Sorted List 
    }//If Sorting by Frequency 
    } 
} 

Answer 2

Cette réponse la plus simple est de ne pas utiliser la récursivité. Toutefois, si vous êtes décidé à utiliser la récursivité, vous pouvez limiter ce qui se passe sur la pile en déplaçant les variables temporaires utilisées dans la fonction en dehors de la portée de la fonction ou en les déclarant static afin qu'elles puissent être réutilisées plutôt que de faire espace pour eux chaque fois que la fusion est appelée (peut avoir des effets négatifs si vous êtes intéressant dans les applications multi-thread). Il ne semble pas que vous ayez des variables qui seraient sûres de le faire avec.

Vous pouvez également encapsuler les paramètres avec une autre structure afin que vous ne devez pas passer trois pointeurs sur le nouvel appel de la pile, IE, un paramètre prend moins de place que 3.

Quelque chose comme:

struct IntList* Merge(struct mergeData* data) 

Il existe également des moyens de adjusting the stack size afin que votre application puisse gérer les ensembles de données que vous attendez.

Dans l'ensemble, il s'agit d'une limitation de la récursivité. Si vous traitez avec des systèmes embarqués qui ont des ressources limitées (comme moi), alors vous l'évitez généralement.