排序时出现分段错误 - Malloc

Question

我正在读取一个浮点数文件，然后对它们进行排序。当我对 100 万个数字使用以下排序和交换函数时，我能够成功地对数字进行排序。但是，当我尝试对 1 亿个数字进行排序时，我遇到了分段错误。我不确定为什么，因为我正在动态分配内存。我如何处理超过 100 万个数字？

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

void swap(float *a, float *b, size_t n) {
    size_t numbytes; 
    size_t sz = sizeof(float); 
    void *temp = NULL; 
    
    numbytes = n * sz; 
    if (numbytes == 0){
        exit(EXIT_FAILURE); 
    }
    temp = malloc(numbytes);
    
    memcpy(temp, a, numbytes);
    memcpy(a,b,numbytes); 
    memcpy(b,temp,numbytes);
    
    free(temp); 
}

void radixSort(float array[], size_t count) {
    int numOfZero = 0; 
    float a[count];
    float *b = a;
    
    for (uint32_t radix=1; radix; radix<<=1) { //unsigned int 32 bit
        uint32_t *arrayToInt = (uint32_t *)array;
        int zeroCount=0;
        int oneCount=0;
        numOfZero=0;
        
        for (int j=0; j < count; ++j)
        numOfZero += !(arrayToInt[j]&radix);
        oneCount=numOfZero;
        
        for (int j=0; j < count; ++j)
        if (arrayToInt[j]&radix){
            b[oneCount]=array[j];
            ++oneCount;
        }
        else{
            b[zeroCount]=array[j];
            ++zeroCount;
        }
        swap(b,array,count);
    }
    if (numOfZero < count){
        memcpy(b+(count-numOfZero), array, numOfZero*sizeof(float));
        
        for (int d=0,j=count-1;j>=numOfZero;j--,d++)
        b[d]=array[j];
        memcpy(array, b, count*sizeof(float));
    }
}
int main(int argc, char *argv[]) {
    int fd; 
    float num; 
    size_t nr; 
    int eleNum = 0; 
    
    fd = open(argv[1], O_RDONLY); 
    
    if (fd == -1){
        perror("Error opening file");
        exit(EXIT_FAILURE);
    }
    
    struct stat st; 
    fstat(fd, &st); 
    off_t size = st.st_size; 
    for (int j = 0; j < size/4; j++){
        eleNum++; 
    } 
    
    float array[eleNum];
    for (int i = 0; i < eleNum; i++){
        nr = read(fd, &num, sizeof(float));
        if (nr == -1){
            perror("Error reading file"); 
            exit(EXIT_FAILURE); 
        }
        array[i] = num; 
    }
    
    radixSort(array, eleNum);
    
    close(fd); 

    return 0; 
}

Answer 1

这些行：

float a[count]; // In radixSort

float array[eleNum]; // In main

永远不会为这么大的数字工作。 VLA:s 是（通常并且总是在实践中）分配在堆栈上。在 Windows 系统上，堆栈通常为 1MB，在 Linux 上通常为 8MB。我已经写了一个关于 VLA:s 的答案，你可以阅读一下。简而言之，我建议不要使用它们。

我不确定改成malloc是否能解决你的问题，但你不做是解决不了的。

此外，您应该检查 malloc 中的 return 值以查看分配是否有效。然后，如果您的问题仍然存在，我建议您使用 -Wall -Wextra -pedantic -std=c11 -fsanitize=address -g 进行编译。使用 gdb 或其他调试器查找导致段错误的行并调查值。使用 valgrind 检测内存泄漏。

还有这个：

for (int j = 0; j < size/4; j++){
    eleNum++; 
}

很奇怪。相当于eleNum = size/4.

这个，在swap：

if (numbytes == 0){
    exit(EXIT_FAILURE); 
}

完全没有必要。将 0 作为大小参数传递给 memcpy 是安全的。这只会导致什么都不会发生。我可以出于调试目的理解这一点，但在那种情况下你应该打印一些有用的东西，甚至更好，使用 assert(numbytes > 0)

排序时出现分段错误 - Malloc

Segmentation Fault While Sorting - Malloc

c

sorting

malloc

segmentation-fault