realloc() тратит много места, что я сделал не так?

Итак, я выполнял это упражнение:

Напишите функцию C void вхождения (char* s, char c, char*** occp, int* n), которая для заданной строки s и char c подсчитывает количество вхождений char c в строке s и возвращает это число в n и возвращает в occp адрес нового массива char, который содержит адреса каждого c вхождения в s

основной образец:

#include <stdio.h>

int main(){
    int i, n;
    char** occ;
    occorrenze("engineering", 'n', &occ, &n);
    for (i=0; i<n; ++i) printf("%s\n", occ[i]); // prints ngineering neering ng
    free(occ);
}

Изначально я написал функцию так:

void occurrences(char* s1, char c, char*** s, int* n){
    *n=0;
     char* arr[2];
     int length=strlen(s1);
     int i;
     for(i=0; i<length; i++){
        if(s1[i]==c)(*n)++;
     }
     *s=(malloc((*n)*sizeof(char**)));
     int a=0;
     for(i=0; i<length; i++){
        if(s1[i]==c){
           (*s)[a]= &s1[i];
           a++;
        }
     }
}

Работало хорошо, но я хотел попробовать переписать его, повторяя строку всего один раз. Я подумал об использовании функции realloc(), которую я никогда раньше не использовал, и в конце концов я придумал это:

void occurrences(char* s1, char c, char*** s, int* n){
    *n=0;
    *s=malloc(0);
     char* arr[2];
     int length=strlen(s1);
     int i,a=0;
     for(i=0; i<length; i++){
        if(s1[i]==c){
            (*n)++;
            *s=realloc(*s,(*n)*sizeof(char**));
            (*s)[a]= &s1[i];
            a++;

        }
     }
}

Этот, похоже, тоже работал хорошо, но затем я запускаю Valgrind:

==4893== HEAP SUMMARY:
==4893==     in use at exit: 0 bytes in 0 blocks
==4893==   total heap usage: 4 allocs, 4 frees, 48 bytes allocated
==4893== 
==4893== All heap blocks were freed -- no leaks are possible
==4893== 
==4893== For counts of detected and suppressed errors, rerun with: -v
==4893== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

выделено 48 байт? Должно было быть 24 байта, верно? Общий размер кучи равен 8*n! вместо 8*n... видимо я что-то упускаю XD

РЕДАКТИРОВАТЬ: скопировал правильную функцию, лол


c memory heap-memory realloc
person Atlas80b    schedule 21.05.2014    source источник
comment
Как вы думаете, почему должно быть 24?   -  person nos    schedule 21.05.2014
comment
Ошибка копирования/вставки @Andrew Medico, извините!   -  person Atlas80b    schedule 21.05.2014
comment
32-битная или 64-битная система? 64-битные системы используют 8-байтовые указатели, что дает 48.   -  person DoxyLover    schedule 21.05.2014
comment
Это может быть не то, на что вы надеетесь, но, честно говоря, было бы более эффективно сделать это своим первоначальным способом. Я полагаю, вы пишете функцию, которая должна работать для всех строк, поэтому у вас нет статистики по размеру входных данных, чтобы найти способ сделать схему перераспределения более эффективной, чем просто подсчет того, насколько большой вам нужно сделать результирующую строку. и соответствующим образом распределяя пространство. Наконец, процессор, скорее всего, будет иметь функцию предсказания ветвлений, что сделает повторяющиеся циклы более эффективными.   -  person Joel Dentici    schedule 21.05.2014
comment
Здесь результат не изменится, но технически вы должны выделить (*n)*sizeof(char*) байт (не используя sizeof(char**)).   -  person nobody    schedule 21.05.2014
comment
@ user2482551: Спасибо за объяснение! Кстати, я не пытался сделать функцию более эффективной, я просто экспериментировал :)   -  person Atlas80b    schedule 21.05.2014
comment
@AndrewMedico: Ты прав! Виноват   -  person Atlas80b    schedule 22.05.2014

Ответы (3)


arrow_upward
0
arrow_downward

ИСПОЛЬЗОВАНИЕ КУЧИ:

Если вы malloc(1), система выделяет для вас кусок памяти, способный хранить один байт. Однако вы можете не осознавать, что система, как правило, никогда не выделяет ни одного байта. В действительности выделенный кусок памяти, скорее всего, намного больше; возможно, минимум 8, 16 или 32 байта. Следовательно, malloc()ed пространство не равно heap space-используемому.

И из-за указанного выше «минимального» распределения системной памяти функция realloc() может вернуть тот же адрес, который был задан; если системное выделение по этому адресу достаточно велико, чтобы вместить (в вашем случае) больший размер. Как только системное выделение станет слишком маленьким, realloc() вернет новый адрес в больший кусок системной памяти (и, скорее всего, больше, чем запрошено realloc).

Несколько комментариев:

void occurrences(char* s1, char c, char*** s, int* n){
   *n=0;
   *s=NULL;

Изменил строку выше. Не нужно malloc(0);. Значение s (NULL) будет передано в realloc(), которое затем будет работать так же, как malloc(),

    char* arr[2];
    int length=strlen(s1);
    int i,a=0;
    for(i=0; i<length; i++){
    if(s1[i]==c){
        (*n)++;
        *s=realloc(*s,(*n) * sizeof(char**));  // !DANGER!

Вместо приведенной выше строки рассмотрите следующую замену:

    if(s1[i]==c){
        char *tmp;
        (*n)++;
        tmp=realloc(*s,(*n) * sizeof(char**));  // Much better.
        if(NULL == tmp)
           {
           /* Handle realloc() failure. */
           ...
           }
        else
           *s = tmp;  

        ...

Если вы не сделаете это, как показано выше, в случае сбоя realloc() ранее выделенная память (на которую указывает s) будет потеряна; заменен на NULL.

        (*s)[a]= &s1[i];
        a++;

    }
 }

}

person Mahonri Moriancumer    schedule 21.05.2014
comment
Большое спасибо за ваши советы ^^ - person Atlas80b; 22.05.2014

arrow_upward
4
arrow_downward

Разве valgrind не измеряет общую выделенную память во время выполнения приложения?

0 + 8 + 16 + 24 = 48.

person Mark    schedule 21.05.2014
comment
Я только что обнаружил, что неправильно понимаю вывод valgrind.. спасибо XD - person Atlas80b; 22.05.2014

arrow_upward
0
arrow_downward

Вы можете избавить себя от головной боли, если не используете *n и *occp в качестве переменных, а используете локальные переменные и сохраняете их в самом конце функции. Делает вещи намного яснее и снижает вероятность ошибок.

person gnasher729    schedule 17.07.2021