Блог

У меня есть университетское упражнение, в котором я должен сравнить некоторые методы хеширования с их количеством коллизий в хэш-таблице. Затем я создал алгоритмы анализа цифр в диссертациях, но они используют много памяти (я даже не могу запустить код до конца, потому что это убивает мой компьютер). Вы можете игнорировать комментарии, но можете быть свободны, если хотите, и знаете португальский язык.

Функция анализа цифр 1 (с использованием динамической матрицы)

 int hashUVDigitAnalysis(int len, int value, int numofdigits, int *arr){  int keydigits, *digits = getDigits(value, amp;keydigits);   if(numofdigits gt;= 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 lt; 10; cont1  ){ //  numqntmatrix[cont1] = (int *)(malloc(keydigits * sizeof(int)));  for(cont2 = 0; cont2 lt; keydigits; cont2  ){  numqntmatrix[cont1][cont2] = 0;  }  }   for(cont1 = 0; cont1 lt; len; cont1  ){  digits = getDigits(arr[cont1], amp;countdigits);  for(cont2 = 0; cont2 lt; keydigits amp;amp; cont2 lt; countdigits; cont2  ){  numqntmatrix[digits[cont2]][cont2]  = 1;  }  }   for(cont1 = 0; cont1 lt; keydigits; cont1  ){  detours[cont1] = 0.0;  }   for(cont1 = 0; cont1 lt; keydigits; cont1  ){  for(cont2 = 0; cont2 lt; 10; cont2  ){  detours[cont1]  = (numqntmatrix[cont2][cont1] - (len / 10.0)) * (numqntmatrix[cont2][cont1] - (len / 10.0));  }  }   for(cont1 = 0; cont1 lt; 10; cont1  ){  free(numqntmatrix[cont1]);  }  free(numqntmatrix);   int *concatenate = (int *)(malloc(numofdigits * sizeof(int)));   for(cont1 = 0; cont1 lt; numofdigits; cont1  ){  cont2 = 0;  concatenate[cont1] = cont2;  for(cont2 = 1; cont2 lt; keydigits; cont2  ){  if(detours[cont2] lt; detours[concatenate[cont1]] amp;amp; detours[cont2] != -1){  concatenate[cont1] = cont2;  }  }  detours[concatenate[cont1]] = -1;  }   digits = getDigits(value, amp;countdigits);  int valueposition = 0;   for(cont1 = 0; cont1 lt; 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, amp;keydigits);   if(numofdigits gt;= 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 lt; 10; cont1  ){  numbers[cont1] = 0;  detours[cont1] = 0.0;  }   for(cont1 = 0; cont1 lt; 10; cont1  ){  for(cont2 = 0; cont2 lt; len; cont2  ){  digits = getDigits(arr[cont2], amp;countdigits);  if(cont1 lt; countdigits){  numbers[digits[cont1]]  = 1;  }  }  for(cont2 = 0; cont2 lt; 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 lt; numofdigits; cont1  ){  cont2 = 0;  concatenate[cont1] = cont2;  for(cont2 = 1; cont2 lt; keydigits; cont2  ){  if(detours[cont2] lt; detours[concatenate[cont1]] amp;amp; detours[cont2] != -1){  concatenate[cont1] = cont2;  }  }  detours[concatenate[cont1]] = -1;  }   digits = getDigits(value, amp;countdigits);  int valueposition = 0;   for(cont1 = 0; cont1 lt; numofdigits; cont1  ){  valueposition  = digits[concatenate[cont1]] * pow(10, cont1);  }   free(concatenate);  free(detours);  free(digits);   return valueposition;  } }  

getDigits function

 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 gt; 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 lt; len; cont  ){  hash_division[cont] = -1;  }   for(cont = 0; cont lt; lenarr; cont  ){  random = (((rand() amp; 255)lt;lt;8 | (rand() amp; 255))lt;lt;8 | (rand() amp; 255))lt;lt;7 | (rand() amp; 127);  random = random % 2000000001;  randomarr[cont] = random;  }   for(cont = 0; cont lt; 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 ГБ полезной оперативной памяти (всего 16 ГБ). Я протестировал обе функции, и там нет никакого цикла бесконечности. Код запускается , когда я ставлю lenarr = 10000 , но я должен протестировать len = 100000 и lenarr равен 200 тысячам, 400 тысячам, 600 тысячам, 800 тысячам и 1 миллиону, поэтому только 10 тысяч не будут работать для меня. Я делаю что-то не так? Есть ли какой-нибудь способ это исправить? У меня никогда раньше не было проблем с памятью ни в одном коде, поэтому я плохо управляю своей памятью в коде.

Причина утечки

Я посмотрел это в вальгринде, и похоже, что ты пропустил пять бесплатных звонков. Это самая крупная утечка:

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

Каждый цикл через этот вызов getDigits() , который выделяет память, которая никогда не освобождается.

Другие источники утечек:

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

Как использовать valgrind

Вот как я провел анализ вальгринда:

Во-первых, я сократил количество циклов, выполняемых программой, со 100 тыс. до 10. Это предотвращает нехватку памяти во время работы valgrind.

Во-вторых, я скомпилировал программу с -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. Как только вы устраните все утечки, 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