c - 多次使用 realloc 获取未知大小数组的好方法吗

Question

我将读取一个包含未知大小数组的文件 像那样

1、2、3、....

5、6、8 ....

该算法使用起来安全且快速吗？

 array =NULL;    /* for realloc */
for(i=0;fgets(line,256,input) != NULL ;++i){
    array =(double**)realloc(array,sizeof(double*)*(i+1));
    value =strtok(line,selector); 
    for(j=0;value != NULL;++j){

        array[i] =(double*)realloc(array[i],sizeof(double)*(j+1));
        sscanf(value,"%lf",&array[i][j]);
        value =strtok(NULL,selector);
    }

}

Answer 1

关于速度:您的算法具有二次复杂度 O(n^2)，其中 n 是每行值的数量或行数。这效率不高。

正常的解决方法是跟踪两个大小，即分配数组的大小和当前正在使用的元素数。通过仅增加当前使用的元素数量(当然，并将值存储在正确的位置)或通过首先 realloc() 将数组两次来添加一个值 当前大小。这样做的结果是，即使 n 非常大，数组中的平均元素也只会被复制一次。这将复杂度降低到 O(n)。

当然，如果您的数组中只有大约 10 个条目，那么所有这些都是无关紧要的。但你要求的是速度。

---

关于安全性:我看到的唯一风险是，您创建了大量的临时对象，这些临时对象只是为了在下一次迭代中被稍大的对象替换而过度地碎片化您的地址空间。从长远来看，这可能会导致内存饥饿增加，但几乎不可能精确衡量这种影响。