大量のデータに対してマージソートを使用すると、スタックオーバーフローを防ぐ方法を教えてください。

Question

私は100、1000、または10000の長いリンクリストでテストするときに動作する次のマージソートアルゴリズムを持っています。ただし、100000または1000000の長いリンクリストを使用すると、Node->Next=Merge(Front,Back->Next,Type);を含む行にセグメンテーション違反が返されます。これは、セグメント化エラーではなくスタックオーバーフローであると私に信じさせてくれました。エラー時のgdbによると、スタックは非常に満杯です。正確な数字を与えるためにコールスタックにあるアイテムの数を正確に調べる方法は見つけられません。大量のデータを処理するマージソートのリワークに関する助けがあれば、大歓迎です。

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

再帰を使用する場合は、末尾呼び出し形式で表現することをお勧めします（戻り値以外の再帰呼び出しが返された後は何も行われないようにする）。そうすれば、ほとんどのコンパイラはテールコールを単純なジャンプに最適化し、スタック領域を使いません。あなたのコンパイラが末尾再帰の最適化をサポートしていない場合は、関数の本体ループを作ることによってそれを自分で行うことができます

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 
} 

：あなたのMerge機能のために、それは次のようになり

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

この最も単純な答えは、再帰を使用しないことです。

しかし、再帰を使用してデッドセットされている場合、関数内で使用されている一時変数を関数の範囲外に移動するか、staticと宣言することでスタックの内容を制限することができます。マージが呼び出されるたびにそれらの部屋があります（マルチスレッドアプリケーションで面白いと悪影響を与える可能性があります）。これを行うには安全な変数があるようには見えません。あなたは新しいスタックコールに3つのポインタを渡す必要がないようにあなたはまた、別の構造体とパラメータをカプセル化することができます

は、IEは、1つのパラメータがより少ないスペースを占有3.

のような何か：

struct IntList* Merge(struct mergeData* data) 

adjusting the stack sizeの方法でも、アプリケーションが期待するデータセットを処理できるようになります。

全体的に、これは再帰の制限です。リソースが限られている組み込みシステム（自分のような）に対処するなら、通常は避けてください。