• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Stos - Moja własna implementacja

VPS Starter Arubacloud
0 głosów
712 wizyt
pytanie zadane 8 lipca 2018 w C i C++ przez niezalogowany
Witam, mógłby ktoś rzucić okiem na moją implementację stosu?

https://github.com/Musialny/stack
komentarz 8 lipca 2018 przez niezalogowany
Aktualnie jest już upubliczniona wersja stosu z garbage collectorem oraz zooptymalizowanymi operacjami Push i Pop.

2 odpowiedzi

0 głosów
odpowiedź 8 lipca 2018 przez RafalS VIP (122,820 p.)
wybrane 8 lipca 2018
 
Najlepsza

Przy każdej uwadze dodam jak poważny jest to wg mnie błąd w skali od 1 do 6:

 1. 2/6 poprawne nazewnictwo zwieksza czytelnosc kodu

template <typename data>

imo nazwa data troche myląca. Trzymałbym się konwencji czyli zwykłego T, a jak już chcesz dać temu dłuższą nazwe to prędziej type, bo tym to jest, typem nie danymi.

2. 6/6 Memory access violation

	data Pop()
	{
		data returnVal;
		returnVal = container[objCount - 1]; 

w ostatniej linijce poleci wyjątek dla container[-1] gdy zrobie pop na pustym stosie. Chyba nie tak to powinno działać, no nie?

3. 5/6 wycieki pamięci w cholere.

Widzę sporo new a nie widzę żadnych delete, czyli masz sporo wycieków pamięci. Nie widać tego jeśli programy są prościutkie i działają krótko, ale gdyby np przeglądarka internetowa gdzieś korzystała z takiej implementacji stosu to bardzo szybko zaczęłaby zużywać o kilka GB ramu za dużo. Dam prosty przykład:

	Stack<std::string> s;
	for (size_t i = 0; i < 10000; i++)
	{
		s.Push("dupa");
	}

a to wcale nie jest jakiś mocny stress test. Zgadnij ile ramu zjadł ten prosty program? 6 GB :D. 

No ale przecież to stos "aż" 10 tys stringów (to aż jest ironiczne :D). A co jeśli będziemy używać niewielkich stosów i je niszczyć, bardzo częsty use case:

	for (size_t i = 0; i < 10000000; i++)
	{
		Stack<std::string> s;
		s.Push("dupa");
	}

dochodzimy do ostatniej linijki i wielkie zaskoczenie - mimo, że nie używamy już żadnych stosów (wszystkie zwolniliśmy) to program zajmuje 2GB pamięci.

4. 5/6 skorelowane mocno z poprzednim

	void Push(data obj)
	{
		buffer = container;
		container = new data[objCount + 1];

czemu dodanie pojedyńczego elementu do stosu wymaga zawsze przepiasania całego stosu od zera? Troche to mało optymalne, no nie? I przede wszystkim alokacji wielgachnych obszarów pamięci dla dużych programów. Puściłem pare stress testów i powiem Ci, że było po szumie wiatraka słychać alokacje pamięci :D

6. 5/6

czemu dodanie jednego elementu wymaga przepisania wszystkich poprzednich? Use case stosu to częste dodawania i sciaganie z końca. Wiesz jak wolno to będzie działać jesli będziemy za każdym razem wszystko kopiować?

5. 5/6

	data Pop()
	{
		data returnVal;
		returnVal = container[objCount - 1];
		buffer = container;
		container = new data[objCount - 1];

wut? sciagniecie elementu ze stosu wymaga zaalokowania tablicy na objCount - 1? Rozumiem, że chcemy strasznie oszczędzać pamięć (pomimo wycieków, które powodują, że tracimy jej jeszcze wiecej), ale po co za każdym razem pomniejszać tablice kosztem przeaalokowania całego stosu. Przy stosie na 10000 elementów po sciagnieciu jednego przealokowujemy 9999, tylko po to żeby zaoczędzić sizeof(element). Alokacja pamięci też trwa, wiesz o tym?

6. 1/6

		data returnVal;
		returnVal = container[objCount - 1];

czemu nie od razu:

		data returnVal = container[objCount - 1];

7. 2/6

		if (buffer != nullptr)
		{
			for (int i = 0; i < objCount; i++)

jesli buffer będzie == nullptr to objCount będzie 0, więc można by sprawdzać czy mamy pusty stos, co byłoby bardziej czytelne. Tak na marginesie to jak mamy pusty stos to objCount == 0, więc pętla i tak sie ani raz nie wykona więc sprawdzenie jest ogólnie bez sensu w tej wersji.

Na razie tyle, jak coś zauważe to jeszcze bd pisał. Generalnie to bardzo kiepska implemenetacja stosu ;/

komentarz 8 lipca 2018 przez niezalogowany
co do wycieków pamięci to ich już nie ma ;-)
komentarz 8 lipca 2018 przez niezalogowany

@RafalS, Ale fakt, faktem wolne to :-D, jaką ocene dasz końcową (0 - 10) uwzględnijąc działający garbage collector?

komentarz 8 lipca 2018 przez RafalS VIP (122,820 p.)
No bez wycieków to dalej jest kiepski program :D Choć tak na prawdę niewiele mu brakuje. Dobrze zacząłeś z powiększaniem tablicy, ale gdybyś tak powiększał ją hurtowo w metodzie push w ten sposób: jeśli kolejna liczba sie nie zmiesci to zaalokuj 2x wieksza tablice zamiast wieksza o 1. Wtedy to byłby już całkiem sensowny stos :P No i wywal zmiejszanie tablicy z pop, bo to wg mnie bez sensu :P
komentarz 8 lipca 2018 przez niezalogowany
Zmniejszanie tablicy z pop wywalę. No i zaimplementuje lepszą alokacje pamięci bo to jest BEZNADZIEJNIE WOLNE, Dzięki :-)
komentarz 8 lipca 2018 przez niezalogowany

@RafalS, Optymalizacja zrobiona, co o tym sądzisz?

komentarz 8 lipca 2018 przez niezalogowany
przypadkowy komentarz
komentarz 8 lipca 2018 przez RafalS VIP (122,820 p.)
Bd mial czas dopiero poznym wieczorem
komentarz 8 lipca 2018 przez niezalogowany
spk
komentarz 8 lipca 2018 przez RafalS VIP (122,820 p.)
		if (objCount > 0)
			return false;
		else
			return true;

równoważne z:

return objCount <= 0;
T * buffer;

dalej jest składową klasy, a nie powinien bo to zaciemnia design. Buffer jest wykorzystywany tymczasowo w metodach, wiec powinien być zmienną lokalną.

	int stackSize()
	{
		return objCount;
	}

	int stackArraySize()

metoda size w klasie stack nie musi się nazywać stackSize :D każdy się domyśli, że jeśli wywłouje size na obiekcie stack to będzie to stackSize.

A stackArraySize w kontenerach STL nazywa się capacity.

Poza tym wg mnie jest ok.

komentarz 8 lipca 2018 przez niezalogowany
:-D
0 głosów
odpowiedź 8 lipca 2018 przez criss Mędrzec (172,590 p.)
  1. Przyjęlo się, że nazwy typów zaczyna się od dużej litery, bo tak się łatwiej czyta (wiadomo co jest typem, a co zmienną itd..). W przypadku template parameter z reguły jest to T. Dla czytelności fajnie jakbyś zmienił `data` na coś z dużej litery.
  2. Nie potrzebujesz `buffer` jako member variable.
  3. Po realokacji nie zwalniasz poprzednio zaalokowanej pamięci.
  4. Mógłbyś wprowadzić jakiś stosunek ilości zaalokowanej pamięci do faktycznie używanej, żeby nie musieć realokować przy każdym push/pop. Tzn. np. gdy pushujesz na pusty stos, to alokujesz pamięć na dwa elementy mimo, że potrzebujesz na jeden. Wtedy przy kolejnym pushu nie musisz realokować. Dopiero przy 3 - wtedy alokujesz np. na 6 elementów mimo, że potrzebujesz na 3. Itd... Analogicznie dla pop. Oczywiście może to wyglądać nieco inaczej, rzucam tylko przykład.
  5. Do przekopiowywania danych do nowego bloku pamięci możesz (i powinieneś) skorzystać z move semantics, bo nie potrzebujesz już obiektów w starym bloku, tylko chcesz mieć je w nowym. Tzn:
    for (size_t i = 0u; i < objCount; ++i)
       container[i] = std::move(buffer[i]);

    .

  6. (rozszerzenie poprzedniego punktu) W przypadku gdy typ jest POD (plain old data - doczytaj jeśli nie kojarzysz), możesz po prostu użyc memcpy. Do compile-time sprawdzenia czy T jest POD możesz wykorzystać std::is_pod. To jednak już troche wyższy poziom i wymaga małej zabawy z template-ami, więc nie przejmuj się jeśli nie potrafisz tego teraz zrobić.

  7. Nie ma potrzeby reprezentować ilości elementów w signed type (zawsze będzie >=0). Standardowo używa się do tego size_t.

  8. isEmpty() zwraca dokładnie przeciwieństwo tego, co powinna.

komentarz 8 lipca 2018 przez niezalogowany
co do isEmpty() to efekt działania jest zamierzony, a co do zwalniania pamięci to nie upubliczniłem commita. Dzięki za rady ;-)

Podobne pytania

+4 głosów
1 odpowiedź 434 wizyt
pytanie zadane 5 lutego 2017 w C i C++ przez JAKUBW Nałogowiec (33,470 p.)
0 głosów
1 odpowiedź 190 wizyt
pytanie zadane 19 listopada 2018 w C i C++ przez MAXIM7 Obywatel (1,990 p.)
+1 głos
1 odpowiedź 32,701 wizyt
pytanie zadane 31 maja 2015 w Algorytmy przez fraktal Nowicjusz (200 p.)

92,454 zapytań

141,262 odpowiedzi

319,089 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...