Garbage collector, utrata pamięci

0

Cześć, przygotowuję się na zajęcia na studia i nie mogę przebrnąć przez to. Zależy mi na podpowiedzi, ponieważ nie chcę nauczyć się źle. Otóż mam określić ilość pamięci utraconej poprzez brak deallokacji. Potrzebuję podać "co najmniej" i "co najwyżej". Rozumiem, że ważną rolę odgrywają tutaj ograniczenia forów ale co z tworzeniem tempów i ich wartości. Mam to jakoś wymnożyć?

int Alg(int n) {
    for (int i_1=0; i_1< nLogN; i_1++) do {
      tmp_0=new(nDoPotęgiPierw10);
      delete(tmp_0);
    }
    tmp_1=new(nDoPotęgi1/3);
    for (int i_1=0; i_1<nLogKwadratN; i_1++) do {
      for (int i_2=0; i_2<nLogN; i_2++) do {
        tmp_2=new(nDoPotęgi1/3);
      }
      for (int i_2=0; i_2<nDoPotęgi10; i_2++) do {
        delete(tmp_2);
      }
      delete(tmp_1);
    }
    for (int i_1=0; i_1<nDoPotęgi3/2; i_1++) do {
      tmp_3=new(logN);
    }
}
3

Twój problem nie jest z zadnym GC ani utratą pamięci tylko z tym że chyba nie umiesz liczyć złożoności obliczeniowej algorytmu. Policz ile masz alokacji i ile dealokacji w zależności od n.

0

Zgadza się, gdybym umiał to bym nie pisał tego tematu.
Rozumiem, że alokację i dealokację wyznaczam dzieki ograniczeniom fora. Jeśli znajdują się pętle wewnętrzne to należy się wymnożyć przez siebie ograniczenia. Dobrze myślę? Co z tym teraz powinienem zrobić?

0

A jesteś pewien że ten kod masz dobrze? Bo on niewiele ma sensu, szczególnie w kontekście tego zwalniania pamięci. To się wywali od razu.
Od razu widać za to że pierwsza pętla nic nie traci, a z ostatniej cieknie wszystko. Środkowa jest za to błędna i takich operacji nie da się wykonać.

0

To jest test, który ma sprawdzić moją wiedzę. Przepisałem cały dokładnie, ma to za zadanie właśnie za zadanie sprawdzenie czy potrafię sprawdzić ile pamięci "uciekło" oraz obliczyć S(n) - dolną lub górną, zależy czy się da.

0

Najprościej odpalić ten program za pomocą Valgrind'a i od razu będziesz wiedział ile bajtów wyciekło. Instalujesz Ubunciaka razem z jakimś IDE do C czy CPP np. QtCreator, do tego instalujesz program Valgrind. Kompilujesz swój projekt w CPP, a następnie uruchamiasz z konsoli poprzez valgrind ./nazwaProgramu i wiesz wszystlo o wyciekach pamieci.

Tutaj nawet nie chodzi o gotowca. Będziesz po prostu wiedział czy dobrze policzyleś utracone bajty.

0

Ale czy to na pewno to chodzi? Ja mam po prostu zaznaczyć dobrą odpowiedź czy np utrata pamięci w danym algorytmie będzie wynosiła O(n^3). Wydaje mi się, że to dokładne liczenie bajtów mija się z zadaniem.

0

Trzeba podsumować liczbę wykonań pętli i liczbę wycieków na każdą pętlę.
W zasadzie samo dodawanie algebraiczne.

Raczej nie chodzi tu o GC (bo to C++) tylko o jakieś abstrakcyjne alokacje.

Przykład dla ostatniej pętli:

    for (int i_1=0; i_1<nDoPotęgi3/2; i_1++) do {
      tmp_3=new(logN);
    }

Liczba alokacji: a = n^3/2
Rozmiar alokacji: ra = alog(n) = (n^3/2)log(n)
Liczba zwolnień: d = 0
Rozmiar zwolnionej pamięci: rd = dlog(n) = 0
Liczba wycieków: w = a - d = n^3/2
Rozmiar wycieków: rw = ra - rd = (n^3/2)
log(n)

Zrób tak analogicznie dla każdej pętli i dla tej "nad-pętli" i podsumuj. Autora zadania pewnie interesuje suma rw.
Wielokrotne zwalnianie tego samego bym zignorował i założył że nie wywala programu, tak jakby wykonało się raz.

Edit: te alokacje przyjmują jeszcze rozmiar (też abstrakcyjny, może być liczba bajtów albo liczba słów albo jeszcze co innego), więc dodawanie, ale już z logarytmami (Szkoła średnia?)

0

Dziękuję za odpowiedz. W takim razie jeśli mam policzyć wycieki na przestrzeni całego algorytmu to jak zrobię to tak jak mówisz to wyjdą mi przykładowo różne rzędy. W celu ograniczenia dolnej granicy wybieram najniższy rząd a górnej najwyższy, dobrze myślę?

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0