对大量数据使用合并排序时如何防止堆栈溢出？

Question

当我测试 100、1000 或 10000 个长链接列表时，我有以下合并排序算法。但是，当使用 100000 或 1000000 长链表时，它 returns 在包含 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

这个最简单的答案是不使用递归。

但是，如果您对使用递归死心塌地，则可以通过将函数中使用的临时变量移动到函数范围之外或声明它们 static 来限制堆栈中的内容，以便它们可以重用而不是每次调用合并时为它们腾出空间（如果您对多线程应用程序感兴趣，可能会产生不利影响）。您似乎没有任何可以安全地执行此操作的变量。

您还可以用另一个结构封装参数，这样您就不必将三个指针传递给新的堆栈调用，即，一个参数占用的空间 space 少于 3.

类似于：

struct IntList* Merge(struct mergeData* data)

还有一些方法adjusting the stack size让您的应用程序可以处理您期望的数据集。

总的来说，这是递归的一个局限性。如果你处理资源有限的嵌入式系统（比如我自己），那么你通常会避免使用它。

Answer 2

如果要使用递归，最好尝试用尾调用形式来表达（这样在递归调用returns之后除了一个return什么都不做） .这样，大多数编译器会将尾调用优化为简单的跳转，而不使用任何堆栈 space。对于您的 Merge 函数，它变成类似：

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
}

如果你的编译器不支持尾递归优化，你可以自己做，将函数体做成一个循环：

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
  }
}

对大量数据使用合并排序时如何防止堆栈溢出？

How do I prevent stack overflow when using merge sort on large amounts of data?

c

stack-overflow

mergesort