C 合并排序算法中的分段故障

Question

我试图在一个相当大的C语言双链表的键上合并排序a，该表有大约10万个元素。 下面是DLL元素的结构。

struct Pore {
    int ns;    /* voxel number */
    int radius;  /* effective radius of porosity surrounding a pore */
    struct Pore *next;
    struct Pore *prev;
};

在搜索了一下算法之后 我发现最常用的算法包括三个函数： mergeSort, merge和 split. 我在这里把它们包括在内......请原谅我的多处。printf在 merge 函数，因为我一直在尝试调试4097592-第4097592个递归条目时发生的分段故障。merge 功能。Recur01 和 Recur02 是我定义的全局变量，以帮助调试。

void mergeSort(struct Pore **head)
{
    Recur01++;

    /* Base case: 0 or 1 pore */
    if ((*head) == NULL) {
        printf("\nEnter mergeSort %ld, list head is NULL ",Recur01);
        fflush(stdout);
        return;
    }
    if ((*head)->next == NULL) {
        printf("\nEnter mergeSort %ld, list head next is NULL ",Recur01);
        fflush(stdout);
        return;
    }

    printf("\nEnter mergeSort %ld",Recur01);
    fflush(stdout);
    /* Split head into 'a' and 'b' sublists */
    struct Pore *a = *head;
    struct Pore *b = NULL;
    split(*head, &a, &b);

    /* Recursively sort the sublists */
    mergeSort(&a);
    mergeSort(&b);

    /* Merge the two sorted halves */
    *head = merge(a,b);

    printf("\nExit mergeSort %ld",Recur01);
    fflush(stdout);
    return;
}

void split(struct Pore *head, struct Pore **a, struct Pore **b)
{
    int count = 0;
    int lngth = 1;
    struct Pore *slow = head;
    struct Pore *fast = head->next;
    struct Pore *temp;

    temp = head;
    while (temp->next != NULL) {
        lngth++;
        /*
        printf("\n    Length = %d",lngth);
        fflush(stdout);
        */
        if (temp->next) {
            temp = temp->next;
        }
    }

    while (fast != NULL) {
        printf("\nCount = %d",count);
        fflush(stdout);
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
        count++;
    }

    printf("\nDone with while loop, final count = %d",count);
    fflush(stdout);

    *b = slow->next;
    slow->next = NULL;
    printf("\nExit split");
    fflush(stdout);
    return;
}

struct Pore *merge(struct Pore *a, struct Pore *b)
{
    Recur02++;

    if (Recur02 >= 4097591) {
        printf("\nEnter merge %ld",Recur02);
        fflush(stdout);
    }

    /** If first linked list is empty, return the second list */

    /* Base cases */
    if (a == NULL) return b;

    if (b == NULL) return a;

    if (Recur02 >= 4097591) {
        printf("\n    Made it 01");
        fflush(stdout);
    }

    /* Pick the larger key */

    if (a->radius > b->radius) {
        if (Recur02 >= 4097591) {
            printf("\n    Made it 02 a is bigger, Recur02 = %ld",Recur02);
            fflush(stdout);
            printf("      a->next->ns = %d",a->next->ns);
            fflush(stdout);
            printf("      b->ns = %d",b->ns);
            fflush(stdout);
        }
        a->next = merge(a->next,b);
        a->next->prev = a;
        a->prev = NULL;
        if (Recur02 >= 4097591) {
            printf("\nExit merge a %ld",Recur02);
            fflush(stdout);
        }
        return a;
    } else {
        if (Recur02 >= 4097591) {
            printf("\n    Made it 02 b is bigger, Recur02 = %ld",Recur02);
            fflush(stdout);
            printf("      b->next->ns = %d",b->next->ns);
            fflush(stdout);
            printf("      a->ns = %d",a->ns);
            fflush(stdout);
        }
        b->next = merge(a,b->next);
        b->next->prev = b;
        b->prev = NULL;
        if (Recur02 >= 4097591) {
            printf("\nExit merge b %ld",Recur02);
            fflush(stdout);
        }
        return b;
    }
}

像我说的那样，运行代码可以工作，直到我进入4097592-第4097592个条目，进入 merge. 我把一个 printf 在函数调用前，立即调用另一个函数。 我还 printf 函数参数中元素的键，它们似乎也没问题。 我不知道还可以尝试什么方法来解决这个问题。 下面是最后几十行的输出。

Exit mergeSort 529095
Exit mergeSort 529095
Enter merge 4097591
    Made it 01
    Made it 02 a is bigger, Recur02 = 4097591      a->next->ns = 156692      b->ns = 20
Enter merge 4097591
Enter merge 4097592
    Made it 01
    Made it 02 a is bigger, Recur02 = 4097592      a->next->ns = 156693      b->ns = 20

这是在分段故障之前从缓冲区中清除的最后一行。 我对如何调试这个问题已经没有办法了，所以希望得到任何建议。

Answer 1

分段故障是由于使用了递归合并，每合并一个节点就调用自己。主代码自上而下是可以的，因为这样会有O(log2(n))的堆栈空间复杂度，但合并函数需要迭代。

最常用的

std::list::sort()的原始实现是一个链接列表的自下而上的合并排序，它使用一个小的列表数组（25到32个）（或指向列表的第一个节点的指针或迭代器）。

https:/en.wikipedia.orgwikiMerge_sort#Bottom-up_implementation_using_lists。

可能在Visual Studio 2015之前，大多数std::list::sort的实现都是自下而上的，Visual Studio 2015从使用列表数组转为使用迭代器（以避免没有默认分配器等问题并提供异常安全）。这个问题在之前的一个线程中出现过，一开始我只是假设切换到迭代器需要改成自上而下，就接受了这个变化。后来又出现了这个问题，所以我研究了一下，确定没有必要切换到自上而下的合并排序。我的主要遗憾是没有从原来的问题中去研究这个问题。我确实更新了我的答案，显示了基于自下而上合并排序的独立迭代器，以及VS2019 include文件中std::list::sort的replament。

`std::list<>::sort()`--为什么突然改成自上而下的策略？

在大多数情况下，只要有足够的内存，将列表复制到一个数组（或向量），对数组进行排序，然后创建一个新的排序列表会更快。如果一个大的链接列表中的节点是随机分散的，那几乎每访问一个节点就会转化为缓存遗漏。通过将列表移动到数组，在数组中运行时通过合并排序的顺序访问，对缓存更加友好。这就是Java对链接列表的原生排序的实现方式，尽管部分原因是由于对包括链接列表在内的多种容器类型使用了通用的collections.sort()，而C++标准库std::list是一个独立的容器类型，它有特定于列表的成员函数。

Answer 2

@VladfromMoscow建议使用非递归的排序算法，因为递归的算法不适合长列表。 因此，我试着为我的双链接列表改编了一个迭代版本的merge sort。此处. 效果很好。 至少在这种情况下，看来对于这么长的列表来说，递归真的太深了。