归并排序算法中的C段错误

Question

我正在尝试对 C 中一个相当大的双向链表的键进行排序，该链表大约有 100,000 个元素。这是 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。我在这里包括它们...请原谅 merge 函数中的多个 printfs 因为我一直在尝试调试在 [=14 的第 4097592 次递归入口时发生的分段错误=] 功能。 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;
    }
}

运行代码有效，就像我说的，直到我到达 merge 的第 4097592 个条目。我在函数调用之前放了一个 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

@VladfromMoscow 建议使用非递归排序算法，因为递归算法不适合长列表。因此，我尝试为我的双向链表调整合并排序的迭代版本 here。奇迹般有效。至少在这种情况下，递归似乎对于这么长的列表来说确实太深了。

Answer 2

分段错误是由于使用了递归合并，它为每个合并的节点调用自身。主代码自上而下是可以的，因为那将具有 O(log2(n)) 的堆栈 space 复杂度，但是合并函数需要迭代。

most often used

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

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

在 Visual Studio 2015 年之前，std::list::sort 的大多数实现可能都是自下而上的，它从使用列表数组切换到使用迭代器（以避免诸如没有默认分配器之类的问题并提供异常安全性）。这是在先前的线程中提出的，最初我只是接受了更改，假设切换到迭代器需要更改自上而下。后来又出现了这个问题，所以我调查了一下，确定没有必要切换到自上而下的归并排序。我的主要遗憾是没有从最初的问题开始研究这个问题。我确实更新了我的答案以显示基于独立迭代器的自下而上合并排序，以及 VS2019 包含文件中 std::list::sort 的替换。

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

归并排序算法中的C段错误

C Segmentation Fault in Merge Sort Algorithm

c

mergesort

segmentation-fault