C 中这些数字分析（哈希）算法的内存使用率非常高

Question

我有一个大学练习，我必须将一些散列方法与它们在散列中的冲突数进行比较 table。然后我做了这些数字分析算法，但它们使用了很多内存（我什至不能运行代码直到最后，因为它会杀死我的电脑）。您可以忽略这些评论，但如果您愿意并且懂葡萄牙语，请随意。

数字分析功能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 的可用 RAM 内存（总共 16 GB）。我测试了这两个函数，没有任何无限循环。当我输入lenarr = 10000时代码运行s，但我必须用len = 100000和lenarr测试等于20万，40万，60万，80万和100万，所以只有 10,000 对我不起作用。我做错了什么？有没有什么办法解决这一问题？我以前在任何代码中都没有内存问题，所以我不擅长在代码中控制我的内存。

Answer 1

泄漏原因

我在 valgrind 中查看了这个，看起来你错过了五个免费电话。这是最大的泄漏：

    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)));

如何使用 valgrind

以下是我执行 valgrind 分析的方式：

首先，我将程序的循环次数从 100K 减少到 10。这可以防止它在 valgrind 运行ning 时运行ning 内存不足。

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

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

第三，我运行 valgrind with --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。解决所有泄漏后，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

C 中这些数字分析（哈希）算法的内存使用率非常高

Very high memory usage in these Digit Analysis (Hash) algorithms in C

c

memory

arrays

hash

pointers

泄漏原因

如何使用 valgrind