2

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

该程序适用于高达 100 万（1000000）的SIZE 。但是当我尝试执行SIZE 1000 万（10000000）的程序时，程序会产生分段错误（核心转储）。

注意：我已经尝试在 Linux (128 MB) 上使用ulimit -s命令增加堆栈的软限制和硬限制。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;
}
4

1 回答 1

2

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

  • 玩家 #1：数组 A[] 本身。根据操作系统/构建，它消耗大约。40 或 80 Mb 的堆栈。仅一次。
  • 玩家#2：小心递归！在您的情况下，这是 heapify() 函数。每次调用都会消耗体面的堆栈块来服务于调用约定、堆栈对齐（如堆栈帧等）。如果你这样做一百万次和树状模式，你也会在这里花费数十兆字节。因此，您可以尝试以非递归方式重新实现此函数以减少堆栈大小压力。
于 2018-03-01T14:24:12.190 回答