我有一個大學練習，我必須將一些散列方法與它們在散串列中的碰撞數進行比較。然后我制作了這些數字分析演算法，但它們使用了大量記憶體（我什至無法運行代碼直到最后，因為它會殺死我的計算機）。您可以忽略評論，但如果您愿意并且知道葡萄牙語，則可以自由選擇。
數字分析功能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;
}
I have 14 GB of usable RAM memory (total of 16 GB).
I tested both functions and there isn't any infinity loop. The code runs when I put lenarr = 10000, but I have to test with len = 100000 and lenarr equals to 200 thousand, 400 thousand, 600 thousand, 800 thousand and 1 million, so only 10 thousand will not works for me. I'm doing something wrong? Is there any way to fix this? I never had a memory problem in any code before, so I'm not good with controlling my memory in code.
uj5u.com熱心網友回復：
泄漏原因
我在 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);
}
通過 this 呼叫的每個回圈都會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 運行時耗盡記憶體。
其次，我用-ggdb,編譯程式以啟用除錯資訊。這是我使用的命令：
gcc test027.c -Wall -Werror -lm -ggdb -o test027
第三，我運行 valgrind --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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/384364.html
標籤：arrays c pointers memory hash
下一篇：未初始化的區域變數使用C