如何在大量數據上使用合併排序時防止堆棧溢出？

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

如果你想使用遞歸，最好試着用尾部調用的形式來表達它（這樣在遞歸調用返回之外的任何事情都不會返回）。這樣，大多數編譯器會將尾部調用優化爲簡單的跳轉，而不是使用任何堆棧空間。爲了您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

這個最簡單的答案是不使用遞歸。但是，如果您使用遞歸的方式已經死了，您可以通過將函數中使用的臨時變量移到函數的作用域之外或者聲明它們以便可以重用它們而不是製作它們來限制堆棧上的內容每次調用合併時都會給它們一個空間（如果您對多線程應用程序感興趣，可能會產生不利影響）。它看起來並不像你有任何可以安全執行此操作的變量。

您也可以封裝與其他結構參數，使您不必在三個指針傳遞到新的堆棧調用，IE，一個參數佔用小於空間3.

喜歡的東西：

struct IntList* Merge(struct mergeData* data) 

也有adjusting the stack size的方法，以便您的應用程序可以處理您所期望的數據集。總的來說，這是遞歸的限制。如果你處理資源有限的嵌入式系統（比如我），那麼你通常會避免它。