时间戳

首页 > 解决方案 > 排序时出现分段错误 - Malloc

c - 排序时出现分段错误 - Malloc

问题描述

我正在读取一个浮点数文件，然后对它们进行排序。当我对 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; 
}

标签： csortingsegmentation-faultmalloc

解决方案

这些行：

float a[count]; // In radixSort

float array[eleNum]; // In main

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

我不确定更改为malloc是否会解决您的问题，但如果不这样做，您将无法解决。

此外，您应该检查返回值malloc以查看分配是否有效。然后，如果您的问题仍然存在，我建议使用-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); 
}

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

推荐阅读