无论如何，在决策树中与2D数组打交道时是否有避免使用“ memcpy”？

Question

我正在尝试编码二进制决策树。以下代码是一个可作为整个算法的一部分的数据分配的工作示例，尽管它具有一些 error 由Valgrind检测到。

您可能已经知道，这棵树由节点组成。在每个节点中，它通过分裂条件携带所有合格的观测值（行）。继续继续，分裂也依赖于这些行。

并且可以通过所有变量和值从贪婪的搜索中找到最佳的分裂条件，这意味着该数据分割步骤可以执行数百次以找到最佳分裂（通过Gini Index在分类问题中评估）。我认为使用memcpy时可能会很昂贵。最糟糕的部分是，每次分开尝试后，我必须释放复制行的内存。

因此，我在想是否有一种方法可以避免使用memcpy从字面上复制整个数据集，而只需在每个分割中引用原始数据集的合格行。这样，不需要过多的memcpy和免费。

问题：要针对以下示例特定，如何使用一个指针记录合格行的地址，以便不需要memcpy ，并允许（易于或方便）执行合格行贪婪的搜索以进行最佳分裂。

让我知道您的问题是否对您不清楚。非常感谢您的时间。

欢迎任何帮助和建议。

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

void printArray(double array[], unsigned int size) {
    for (unsigned int i = 0; i < size; ++i) {
        printf("%.3f  ", array[i]);
    }
    printf("\n");
}

double **alloc_2dArray(unsigned int row, unsigned int col)
{
    double **Array = (double **) malloc(row * sizeof(double *));

    for (unsigned int i = 0; i < row; i++) {
        Array[i] = (double *) malloc(col * sizeof(double));
    }

    return Array;
}

void dealloc_2dArray(double **Array, unsigned int row, unsigned int col)
{
    for (unsigned int i = 0; i < row; i++)
    {
        free(Array[i]);
    }
    free(Array);
}

int main(){

    double **data = alloc_2dArray(4,4);
    double delta[4] = {1,0,1,0};

    double **dataL = alloc_2dArray(4,4);
    double **dataR = alloc_2dArray(4,4);

    int i,j;

    int k=0;
    //data initialization
    for(i=0; i<4; i++){
        for(j=0; j<4; j++){
            data[i][j] = k++;
        }
    }

    int l=0, r=0;

    for(i=0; i<4; i++){
        if((int)delta[i] ==0){
            memcpy(dataL[l++], data[i], 4*sizeof(double));
        }else{
            memcpy(dataR[r++], data[i], 4*sizeof(double));
        }
    }

    for(i = l; i<4; i++){
        free(dataL[i]);
    }

    printf("l and r are %d %d\n", l, r);

    dataL = realloc(dataL, l*sizeof(double*));

    for(i = r; i<4; i++){
        free(dataR[i]);
    }

    dataR = realloc(dataR, r*sizeof(double*));

    for(i=0; i<4; i++){
        if(dataL[i] != NULL){
            printArray(dataL[i],4);
        }
        if(dataR[i] != NULL){
            printArray(dataR[i],4);
        }
    }

    dealloc_2dArray(data, 4,4);
    dealloc_2dArray(dataL, l, 4);
    dealloc_2dArray(dataR, r, 4);
    return 0;
}

Answer 1

我 think 您询问您是否只能将原始数据行指针保留在拆分矩阵中。答案是肯定的，你可以。但是，所有权发挥了作用。

对于下面的示例（没有memcpy操作）datal和datar datar 指针床是直接分配的，而没有分配的数据行的实际行给他们。这些行是从原始数据矩阵中“借”的。

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

void printArray(double const array[], unsigned int size)
{
    for (unsigned int i = 0; i < size; ++i)
    {
        printf("%-7.3f", array[i]);
    }
    printf("\n");
}

double **alloc_2dArray(unsigned int row, unsigned int col)
{
    double **Array = malloc(row * sizeof(double *));

    for (unsigned int i = 0; i < row; i++)
    {
        Array[i] = (double *)malloc(col * sizeof(double));
    }

    return Array;
}

void dealloc_2dArray(double **Array, unsigned int row)
{
    for (unsigned int i = 0; i < row; i++)
    {
        free(Array[i]);
    }
    free(Array);
}

int main()
{

    double **data = alloc_2dArray(4,4);
    double delta[4] = {1, 0, 1, 0};

    double **dataL = calloc(4, sizeof *dataL);
    double **dataR = calloc(4, sizeof *dataR);

    unsigned int i, j;

    double k = 0;

    // data initialization
    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < 4; j++)
        {
            data[i][j] = k;
            k += 1;
        }
    }
    printf("data[]\n");
    for (i=0; i<4; ++i)
        printArray(data[i], 4);
    fputc('\n', stdout);

    unsigned int l = 0, r = 0;
    for (i = 0; i < 4; i++)
    {
        if ((int)delta[i] == 0)
        {
            dataL[l++] = data[i];
        }
        else
        {
            dataR[r++] = data[i];
        }
    }

    printf("l=%u r=%u\n", l, r);
    dataL = realloc(dataL, l * sizeof(double *));
    dataR = realloc(dataR, r * sizeof(double *));

    printf("dataL[]\n");
    for (i=0; i<l; ++i)
        printArray(dataL[i], 4);
    fputc('\n', stdout);

    printf("dataR[]\n");
    for (i=0; i<r; ++i)
        printArray(dataR[i], 4);
    fputc('\n', stdout);

    free(dataL);
    free(dataR);
    dealloc_2dArray(data,4);
    return 0;
}

输出

data[]
0.000  1.000  2.000  3.000  
4.000  5.000  6.000  7.000  
8.000  9.000  10.000 11.000 
12.000 13.000 14.000 15.000 

l=2 r=2
dataL[]
4.000  5.000  6.000  7.000  
12.000 13.000 14.000 15.000 

dataR[]
0.000  1.000  2.000  3.000  
8.000  9.000  10.000 11.000 

关于这些行指针的实际所有权。只有您知道那里有什么合适的。如果原始数据矩阵要继续拥有它们，则必须注意确保data及其行 datal和Datar仍在使用中。同样，如果datar和datal是所有权，则在释放data 时，您不应释放这些行data），并具有datal和datar free'ing不仅要释放其基本指针床，还可以释放行。

无论如何，你去了。