在C中这些数字分析(Hash)算法中的内存使用量很高。

Question

我有一个大学练习，在这里我必须比较一些散列方法和它们在散列表中的结合体数。然后我制作了这些数字分析算法，但是它们使用了大量的内存(我甚至不能运行代码直到结束，因为它杀死了我的计算机)。你可以忽略这些评论，但是如果你想知道葡萄牙语的话就可以自由了。

数字分析函数1(使用二值矩阵)

int hashUVDigitAnalysis(int len, int value, int numofdigits, int *arr){
    int keydigits, *digits = getDigits(value, &keydigits);

    if(numofdigits >= keydigits){
        free(digits);                                                        //                                     -ATENÇÃO-
        return value;                                                        //
    }else{                                                                   // Essa função funciona, mas quando testei com o vetor *arr muito grande, ele rapidamente
        int **numqntmatrix = (int **)(malloc(10 * sizeof(int *)));           //          consumiu maior parte da memória do meu pc, e o computador falhou por
        int cont1, cont2, countdigits;                                       //                    falta de memória. Use essa função apenas para
        float *detours = (float *)(malloc(keydigits * sizeof(float)));       //                            testar um único valor (UV).
                                                                             // Como alternativa, tentei realizar a função abaixo desta, mas a mesma deu o mesmo problema.
        for(cont1 = 0; cont1 < 10; cont1++){                                 //
            numqntmatrix[cont1] = (int *)(malloc(keydigits * sizeof(int)));
            for(cont2 = 0; cont2 < keydigits; cont2++){
                numqntmatrix[cont1][cont2] = 0;
            }
        }

        for(cont1 = 0; cont1 < len; cont1++){
            digits = getDigits(arr[cont1], &countdigits);
            for(cont2 = 0; cont2 < keydigits && cont2 < countdigits; cont2++){
                numqntmatrix[digits[cont2]][cont2] += 1;
            }
        }

        for(cont1 = 0; cont1 < keydigits; cont1++){
            detours[cont1] = 0.0;
        }

        for(cont1 = 0; cont1 < keydigits; cont1++){
            for(cont2 = 0; cont2 < 10; cont2++){
                detours[cont1] += (numqntmatrix[cont2][cont1] - (len / 10.0)) * (numqntmatrix[cont2][cont1] - (len / 10.0));
            }
        }

        for(cont1 = 0; cont1 < 10; cont1++){
            free(numqntmatrix[cont1]);
        }
        free(numqntmatrix);

        int *concatenate = (int *)(malloc(numofdigits * sizeof(int)));

        for(cont1 = 0; cont1 < numofdigits; cont1++){
            cont2 = 0;
            concatenate[cont1] = cont2;
            for(cont2 = 1; cont2 < keydigits; cont2++){
                if(detours[cont2] < detours[concatenate[cont1]] && detours[cont2] != -1){
                    concatenate[cont1] = cont2;
                }
            }
            detours[concatenate[cont1]] = -1;
        }

        digits = getDigits(value, &countdigits);
        int valueposition = 0;

        for(cont1 = 0; cont1 < numofdigits; cont1++){
            valueposition += digits[concatenate[cont1]] * pow(10, cont1);
        }

        free(detours);
        free(digits);

        return valueposition;
    }
}

数字分析函数2(仅使用数组)

int hashQuadraticDigitAnalysis(int len, int value, int numofdigits, int *arr){
    int keydigits, *digits = getDigits(value, &keydigits);

    if(numofdigits >= keydigits){
        free(digits);
        return value;
    }else{
        int cont1, cont2, countdigits;
        int *numbers = (int *)(malloc(10 * sizeof(int)));
        float *detours = (float *)(malloc(10 * sizeof(float)));

        for(cont1 = 0; cont1 < 10; cont1++){
            numbers[cont1] = 0;
            detours[cont1] = 0.0;
        }

        for(cont1 = 0; cont1 < 10; cont1++){
            for(cont2 = 0; cont2 < len; cont2++){
                digits = getDigits(arr[cont2], &countdigits);
                if(cont1 < countdigits){
                    numbers[digits[cont1]] += 1;
                }
            }
            for(cont2 = 0; cont2 < 10; cont2++){
                detours[cont1] += (numbers[cont2] - (len / 10.0)) * (numbers[cont2] - (len / 10.0));
                numbers[cont2] = 0;
            }
        }

        int *concatenate = (int *)(malloc(numofdigits * sizeof(int)));

        for(cont1 = 0; cont1 < numofdigits; cont1++){
            cont2 = 0;
            concatenate[cont1] = cont2;
            for(cont2 = 1; cont2 < keydigits; cont2++){
                if(detours[cont2] < detours[concatenate[cont1]] && detours[cont2] != -1){
                    concatenate[cont1] = cont2;
                }
            }
            detours[concatenate[cont1]] = -1;
        }

        digits = getDigits(value, &countdigits);
        int valueposition = 0;

        for(cont1 = 0; cont1 < numofdigits; cont1++){
            valueposition += digits[concatenate[cont1]] * pow(10, cont1);
        }

        free(concatenate);
        free(detours);
        free(digits);

        return valueposition;
    }
}

getDigits函数

int* getDigits(int value, int *addr_countdigits){
    int copyofvalue = value;
    *addr_countdigits = 0;

    while(copyofvalue != 0){
        copyofvalue = copyofvalue / 10;
        *addr_countdigits = *addr_countdigits + 1;
    }

    int tmp = *addr_countdigits;
    int *array = (int *)(malloc(tmp * sizeof(int)));
    copyofvalue = value;

    while(copyofvalue > 0){
        array[tmp - 1] = copyofvalue % 10;
        copyofvalue = copyofvalue / 10;
        tmp = tmp-1;
    }

    return array;
}

主

int main(void){
    int len = 100000, lenarr = 200000, cont, random, numcolision = 0, pos;

    int *randomarr = (int *)(malloc(lenarr * sizeof(int)));

    int *hash_division = (int *)(malloc(len * sizeof(int)));

    for(cont = 0; cont < len; cont++){
        hash_division[cont] = -1;
    }

    for(cont = 0; cont < lenarr; cont++){
        random  = (((rand() & 255)<<8 | (rand() & 255))<<8 | (rand() & 255))<<7 | (rand() & 127);
        random = random % 2000000001;
        randomarr[cont] = random;
    }

    for(cont = 0; cont < lenarr; cont++){
        pos = hashUVDigitAnalysis(lenarr, randomarr[cont], 5, randomarr);
        if(hash_division[pos] == -1){
            hash_division[pos] = randomarr[cont];
        } else{
            numcolision++;
        }
    }

    printf("%d", numcolision);
    return 0;
}

我有14 GB的可用内存(总共16 GB)。我测试了这两个函数，没有任何无限循环。当我放置lenarr = 10000时，代码就会运行，但是我必须用len = 100000进行测试，lenarr值为20万、40万、60万、80万和100万，所以只有1万条不适用于我。我做错什么了吗？有办法解决这个问题吗？我以前在任何代码中都没有内存问题，所以我不擅长在代码中控制我的内存。

Answer 1

漏水原因

我看了这篇文章，好像你错过了五个免费电话。这是最大的泄漏：

    for(cont1 = 0; cont1 < len; cont1++){
        digits = getDigits(arr[cont1], &countdigits);
        for(cont2 = 0; cont2 < keydigits && cont2 < countdigits; cont2++){
            numqntmatrix[digits[cont2]][cont2] += 1;
        }
        // free memory returned by getDigits()
        free(digits);
    }

每一个循环都调用getDigits()，它分配从未释放过的内存。

其他泄漏来源：

• int keydigits, *digits = getDigits(value, &keydigits);
• int *concatenate = (int *)(malloc(numofdigits * sizeof(int)));
• int *randomarr = (int *)(malloc(lenarr * sizeof(int)));
• int *hash_division = (int *)(malloc(len * sizeof(int)));

如何使用缬草

下面是我如何进行英勇分析的方法：

首先，我将程序的循环次数从100 K减少到10，这样就可以防止它在运行的时候耗尽内存。

其次，我用-ggdb编译了程序，以启用调试信息。下面是我使用的命令：

gcc test027.c -Wall -Werror -lm -ggdb -o test027

第三，我和--leak-check=full一起跑了

valgrind --leak-check=full ./test027 

这向我展示了内存泄漏来源的堆叠痕迹。每一个看起来都是这样的：

==174419== 1,501,600 bytes in 40,000 blocks are definitely lost in loss record 1 of 1
==174419==    at 0x483C7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==174419==    by 0x10925C: getDigits (test027.c:16)
==174419==    by 0x10940D: hashUVDigitAnalysis (test027.c:50)
==174419==    by 0x109988: main (test027.c:118)

您首先看到的是内存泄漏的大小。(1 501 600字节)您应该首先解决最大的内存泄漏问题。接下来，您将看到有多少分配从未被释放。(40 000街区)。接下来，您将看到程序中负责的部分的行号。

解决每次内存泄漏的问题，然后重新运行。一旦您解决了所有的漏洞，valgrind将显示以下输出：

==174500== HEAP SUMMARY:
==174500==     in use at exit: 0 bytes in 0 blocks
==174500==   total heap usage: 43,003 allocs, 43,003 frees, 1,621,428 bytes allocated
==174500== 
==174500== All heap blocks were freed -- no leaks are possible