由于输入数组尺寸过大，C 程序崩溃(段错误)。如何在不使用 static/global/malloc 的情况下防止它？

Question

以下程序是使用堆排序对大量随机数进行排序。程序的输出是递归heapSort函数的总执行时间(以微秒为单位)。输入数组的大小由SIZE宏定义。

该程序在 SIZE 最多 100 万 (1000000) 的情况下运行良好。但是当我尝试执行 SIZE 1000 万(10000000)的程序时，程序会生成段错误(核心转储)。

注意:我已经尝试在 Linux 上使用 ulimit -s 命令增加堆栈的软限制和硬限制(128 MB)。 SEGFAULT 仍然存在。

请建议我对所需代码进行任何更改，或者提出任何可以克服现有 SEGFAULT 问题的方法，而无需动态声明数组或全局/静态数组。 /* 实现堆排序算法的程序 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

long SIZE = 10000000; // Or #define SIZE 10000000

long heapSize;

void swap(long *p, long *q)
{
    long temp = *p;
    *p = *q;
    *q = temp;
}

void heapify(long A[], long i)
{
    long left, right, index_of_max;
    left = 2*i + 1;
    right = 2*i + 2;

    if(left<heapSize && A[left]>A[i])
        index_of_max = left;
    else
        index_of_max = i;

    if(right<heapSize && A[right]>A[index_of_max])
        index_of_max = right;

    if(index_of_max != i)
    {
        swap(&A[index_of_max], &A[i]);
        heapify(A, index_of_max);
    }       
}

void buildHeap(long A[])
{
    long i;

    for(i=SIZE/2; i>=0 ; i--)
        heapify(A,i);
}

void heapSort(long A[])
{
    long i;

    buildHeap(A);

    for(i=SIZE-1 ; i>=1 ; i--)
    {
        swap(&A[i], &A[0]);
        heapSize--;
        heapify(A, 0);
    } 
}

int main()
{
    long i, A[SIZE];
    heapSize = SIZE;
    struct timespec start, end;

    srand(time(NULL));
    for(i = 0; i < SIZE; i++)
        A[i] = rand() % SIZE;

    /*printf("Unsorted Array is:-\n");
    for(i = 0; i < SIZE; i++)
        printf("%li\n", A[i]);
    */

    clock_gettime(CLOCK_MONOTONIC_RAW, &start);//start timer
    heapSort(A);
    clock_gettime(CLOCK_MONOTONIC_RAW, &end);//end timer

    //To find time taken by heapsort by calculating difference between start and stop time.
    unsigned long delta_us = (end.tv_sec - start.tv_sec) * 1000000 \
                            + (end.tv_nsec - start.tv_nsec) / 1000;

    /*printf("Sorted Array is:-\n");
    for(i = 0; i < SIZE; i++) 
        printf("%li\n", A[i]);
    */

    printf("Heapsort took %lu microseconds for sorting of %li elements\n",delta_us, SIZE);

    return 0;
}

Answer 1

因此，一旦您计划坚持使用仅堆栈方法，您就必须了解谁是堆栈空间的主要使用者。

• 玩家 #1:数组 A[] 本身。根据操作系统/构建，它消耗大约。 40 或 80 Mb 堆栈。仅限一次性。
• 玩家#2:小心递归!在你的例子中，这是 heapify() 函数。每个调用都会消耗相当多的堆栈 block 来服务于调用约定、堆栈对齐(例如堆栈帧等)。如果您执行该百万次和树状模式，那么您也会在这里花费数十兆字节。因此，您可以尝试以非递归方式重新实现此函数，以减少堆栈大小压力。