W rzeczywistości jest to nieco związane z pytaniem, które zadałem wczoraj, dlaczego stos i stos są niezbędne w aplikacjach, których używamy dzisiaj (i dlaczego nie możemy po prostu wybrać stosu zamiast obu, aby mieć proste & szczególny standard).
Jednak wiele odpowiedzi wskazywało, że stos jest niezastąpiony ze względu na fakt, że jest on setki (lub tysiące) razy szybszy niż próba alokacji / odwołania do stosu. Wiem, że istnieje problem z dynamiczną alokacją pamięci, jeśli zlikwidujemy Stertę, ale czy nie istnieje sposób na obejście tego, a może sposób na ulepszenie stosu, aby mógł on obsłużyć dynamiczną alokację pamięci?
Odpowiedzi:
Problem ze stosami polega na tym, że nie można „zwolnić” pamięci, chyba że jest na wierzchu stosu. Załóżmy na przykład, że przydzieliłeś 3 rzeczy o różnych rozmiarach:
Stos miałby
a
na dole,b
na środku ic
na górze. Staje się to problematyczne, jeśli chcemy uwolnićb
:Obejściem tego problemu jest przeniesienie wszystkich danych po
b
i przesunięcie, jeśli tak, aby nastąpiło późnieja
. To działa, ale w tym przypadku będzie wymagało 5000000 kopii - coś, co będzie znacznie wolniejsze niż kupa.Właśnie dlatego mamy stos. Chociaż alokacja może być wolniejsza niż stos (
O(log n)
vsO(1)
), stosy pozwalają na szybkie zwolnienie pamięci w dowolnym miejscu -O(log n)
w porównaniu do stosuO(n)
źródło
Facebook doesn't remove content from its disk when you ask it to remove it, it just removes the pointer to it
- Co w zasadzie dzieje się, gdy wykonujesz zwykłe usuwanie pliku w dowolnym systemie operacyjnym.Stos jest zależny od wątku, a stos jest cały proces
Jeśli 100 wątków ma wszystkie przetwarzane elementy pracy, które umieszczam w kolejce, to gdzie dokładnie mam alokować elementy pracy, aby każdy ze 100 wątków mógł je zobaczyć?
Istnieją również inne rodzaje pamięci
Np. Pliki mapowane w pamięci, pamięć współdzielona, mapowane we / wy (tryb jądra). Argument wydajności jest w takich sytuacjach dyskusyjny.
źródło
Stos jest strukturą LIFO (ostatni na wejściu, pierwszy na wyjściu), na której górze znajduje się wskaźnik odniesienia (zwykle obsługiwany przez sprzęt). Powiedziawszy to, wszystko, co próbujesz przydzielić na stosie zamiast na stosie, musiałoby być zmienną lokalną w każdej funkcji na górze tego stosu. Zatem głównym powodem stosu jest to, że twoja procedura główna () musiałaby wstępnie przydzielić wszystkie struktury danych, z których korzysta Twój program (które mają być dostępne przez cały czas trwania programu), zanim wszystkie struktury danych zostaną przydzielone wywołania funkcji zostaną ostatecznie usunięte, gdy te wywołania funkcji powrócą, a ich ramki lub rekordy aktywacji zostaną usunięte ze stosu.
źródło
Stosy świetnie sprawdzają się w przypadku alokacji pamięci, które są zgodne z regułami Last in First out (LIFO), co oznacza, że zwalniasz pamięć w dokładnie odwrotnej kolejności, w jakiej ją alokujesz. LIFO jest bardzo powszechnym, być może najczęstszym wzorem przydziału pamięci. Ale to nie jedyny wzór, ani nawet wspólny wzór. Aby napisać skuteczny program, który może rozwiązać wiele różnych problemów, musimy uwzględnić mniej popularne wzorce, nawet jeśli oznacza to bardziej złożoną infrastrukturę.
Jeśli uda mi się uzyskać wszystkie meta dla akapitu: jesteś początkującym, jako początkujący cenisz prostotę i zasady czarno-białe. Jednak jako początkujący masz tylko wizjer z szerokiej gamy problemów i ograniczeń, które muszą zostać uwzględnione przez programy komputerowe. Wchodzisz w technologię, która jest aktywnie rozwijana przez 75 lat. Nie ma nic złego w pytaniu, dlaczego rzeczy są takie, jakie są, ale ogólnie odpowiedź brzmi: „Tak, wypróbowaliśmy prostą, bezpośrednią metodę 50 lat temu i okazało się, że nie działa zbyt dobrze dla całych klas problemów, więc musieliśmy zrobić coś bardziej skomplikowanego ”. W miarę postępu technologii prostota musi ustępować miejsca wydajności i elastyczności.
źródło
Na inny przykład, zamknięcia. Jeśli ustawisz pop, możesz stracić rekord aktywacyjny zamknięcia. Jeśli więc chcesz, aby ta anonimowa funkcja i jej dane trwały, musisz ją zapisać gdzie indziej niż na stosie wykonawczym.
źródło
Wśród wielu innych powodów przydzielania miejsca na sterty.
Jeśli chcesz przekazać adres obiektu z powrotem do programu wywołującego, nie powinieneś przekazywać adresu zmiennej stosu, ponieważ pamięć stosu zostanie ponownie użyta i prawdopodobnie nadpisana przez następną wywoływaną funkcję. Musisz uzyskać wymaganą pamięć za pomocą malloc (), aby upewnić się, że nie zostanie ona zastąpiona wywołaniami kolejnych funkcji.
Możesz przekazać adresy elementów stosu z funkcji do wywoływanych funkcji, ponieważ możesz zagwarantować, że będą one istnieć, dopóki Twój program nie „zwróci ()”. Ale gdy tylko funkcja zwróci, cała pamięć stosu jest gotowa do pobrania.
źródło