Dlaczego dwie różne koncepcje nazywane są „stertą”?

170

Dlaczego sterta środowiska wykonawczego jest używana do dynamicznej alokacji pamięci w językach typu C i struktura danych są nazywane „stertą”? Czy jest jakiś związek?

c++ heap terminology heap-memory Andrey Fedorov
źródło
4
Zastanawiałem się nad tym dzisiaj, studiując struktury danych.
MitMaro
1
zduplikowane pytanie? http://stackoverflow.com/questions/756861/whats-the-relationship-between-a-heap-and-the-heap
timB33
3
Przejdź do słownika języka angielskiego i policz liczbę wpisów w sekcji „Uruchom”. Ile z ponad 40 zgłoszeń dotyczy komputerów? :)
jmucchiello
2
możliwy duplikat Jaka jest relacja między „stertą” a „stertą”?
RCIX
Powiązany post w tym miejscu stosu wykonawczego wrt używanego do dynamicznej alokacji pamięci.
RBT

Odpowiedzi:

77

Donald Knuth mówi (The Art of Computer Programming, Third Ed., Vol. 1, str. 435):

Około 1975 r. Kilku autorów zaczęło nazywać pulę dostępnej pamięci „stertą”.

Nie mówi, którzy autorzy i nie podaje odniesień do żadnych konkretnych artykułów, ale mówi, że użycie terminu „sterta” w odniesieniu do kolejek priorytetowych jest tradycyjnym znaczeniem tego słowa.

James McNellis
źródło
11
Pula byłaby lepszą nazwą niż sterta.
7
Ciekawy. Ktoś powinien go zapytać, czy pamięta, którzy autorzy.
Prof. Falken
27
Wikipedia twierdzi, że dzieje się tak, ponieważ Lisp na wczesnym etapie używał sterty (struktury danych) do implementacji swojego magazynu pamięci. Nie mówi, jak to zrobić. Jego odniesieniem jest „Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Wprowadzenie do algorytmów. MIT Press / McGraw-Hill.”, Którego nie mam.
Steve Jessop,
2
Nie mam odniesienia do tego, ale przypuszczam, że początkowo struktura danych używana do organizowania odniesień do otwartych bloków pamięci była minimalna. Wygląda na to, że byłby to przynajmniej przyzwoity sposób na szybkie znalezienie najmniejszego bloku pamięci, który pozwoliłby na przechowywanie danych, które próbujesz przechowywać. Aktualizacja: to, co powiedziałem, brzmi dokładnie jak bloki znajomych en.wikipedia.org/wiki/Dynamic_memory_allocation # Buddy% 5Fblocks
Will
4
@SteveJessop - Checking Cormen, Leiserson, Rivest, Stein - 3. wydanie (2009) na początku rozdziału Heapsort mówi tylko, że „Termin„ sterta ”został pierwotnie wymyślony w kontekście sortowania kopców, ale od tamtej pory odnosi się do„ miejsce na dane bezużyteczne ”, takie jak języki programowania Java i Lisp. Nasza struktura danych sterty nie jest magazynem śmieciowym, a ilekroć mówimy o stertach w tej książce, mamy na myśli raczej strukturę danych niż aspekt zbierania śmieci ”. CLRS - wydanie 2 również ma prawie dokładnie to samo sformułowanie (nic nie wskazuje na to, że Lisp używał stosu).
dr jimbob
64

Mają tę samą nazwę, ale tak naprawdę nie są podobne (nawet koncepcyjnie). Sterta pamięci nazywana jest stertą w taki sam sposób, jak kosz na bieliznę nazywamy „stertą ubrań”. Ta nazwa jest używana do wskazania nieco niechlujnego miejsca, w którym można dowolnie alokować i zwalniać pamięć. Struktura danych (jak wskazuje odsyłacz do Wikipedii) jest zupełnie inna.

Andrew Hare
źródło
8
Tak, myślę, że to raczej punkt, na którym opiera swoje pytanie: są różni. Dlaczego więc nazywają się to samo - czy istnieje jakaś ukryta relacja.
Sean Owen
9
Sposób, w jaki zinterpretowałem tę odpowiedź, brzmi: „nie, nie ma żadnego podstawowego związku”, więc odpowiada na pytanie.
Laurence Gonsalves
Andrew odpowiada na to. Nie ma żadnego związku. Tylko zbieg okoliczności. Sterta pamięci jest bardziej zgodna z powszechnym użyciem, ponieważ pamięć jest przydzielana tak, jakby była „stertą ubrań”. Struktura danych wymagała jednak większej wyobraźni. I to staje się dużo bardziej interesującym „dlaczego”. Nazwa pochodzi od faktu, że węzły są uporządkowane według klucza, a klucz węzła nadrzędnego jest zawsze> = niż jego węzeł potomny.
Alexandre Bell
6
Zdecydowanie nie są ze sobą spokrewnieni. Jednak problem z nazywaniem go „stertą” polega na tym, że „odpowiednik sterty” - „stos” - jest również rzeczywistym stosem.
dan
1
Wiem, dlaczego struktura danych sterty nazywa się stertą: ponieważ spełnia ona właściwość sterty. Ale dlaczego tak nazywa się właściwość sterty? Nie ma to dla mnie sensu, bo nazwa typu „top heavy” byłaby znacznie lepsza.
Thomas Eding,
31

Kolizja nazw jest niefortunna, ale nie aż tak tajemnicza. Sterta to małe, powszechne słowo używane na oznaczenie stosu, kolekcji, grupy itp. Użycie tego słowa na określenie struktury danych poprzedza (jestem prawie pewien) nazwę puli pamięci. W rzeczywistości basen byłby moim zdaniem znacznie lepszym wyborem dla tego drugiego. Sterta oznacza strukturę pionową (jak stos), która pasuje do struktury danych, ale nie do puli pamięci. Nie myślimy o stercie puli pamięci jako hierarchicznej, podczas gdy podstawową ideą stojącą za strukturą danych jest utrzymywanie największego elementu na szczycie stosu (i pod-stosów).

Heap struktura danych sięga połowy lat 60-tych; sterty puli pamięci, wczesne lata 70. Termin sterta (oznaczający pula pamięci) był używany co najmniej już w 1971 roku przez Wijngaardena w dyskusjach na temat Algola.

Prawdopodobnie najwcześniejsze użycie sterty jako struktury danych zostało znalezione siedem lat wcześniej w
Williams, JWJ 1964. „Algorithm 232 - Heapsort”, Communications of the ACM 7 (6): 347-348

IJ Kennedy
źródło
1
Tak, ale stos oznacza również nieporządek, a stosy pamięci są generalnie nieuporządkowane. Sterta struktury danych jest bardzo dobrze uporządkowana. Więc znowu istnieje równe niedopasowanie idące w drugą stronę w oparciu o wspólną definicję sterty.
jmucchiello
Jest zawsze wprowadzane jako przeciwieństwo stosu, co powinno wystarczyć do wyjaśnienia nazwy IMO.
reinierpost
1
To nie przypadek - bezpłatną listę można zaimplementować jako kolejkę priorytetową za pośrednictwem stosu dwumianowego.
Heath Hunnicutt
2
@jmucchiello: stos kłód (patrz zdjęcie ) jest uporządkowany i przypomina drzewo. Stąd pochodzi nazwa struktury danych według jednego z moich podręczników licencjackich.
gioele
6

Właściwie czytanie o sposobie alokacji pamięci (patrz Buddy Blocks ) przypomina mi stertę struktur danych.

Podróżujący Technik
źródło
Mój komentarz do odpowiedzi Petera Zhanga jest tutaj również istotny. Binarny system znajomych może być reprezentowany jako drzewo binarne, a także wygląda jak poprawna maksymalna sterta, gdy „klucz” każdego węzła jest całkowitą pamięcią znajdującą się pod nim (ale te wartości są niejawne i nigdy się nie zmieniają). O ile wiem, ani algorytm alokacji, ani zwalniania nie używają operacji sterty w tym drzewie binarnym.
Eric Dubé
5

IMO to tylko przypadek / zbieg okoliczności, że te dwie zupełnie niezwiązane ze sobą rzeczy mają tę samą nazwę. To jak wykres i wykres .

MAK
źródło
Te dwa wykresy mogą być jednak w jakiś sposób powiązane. Wyobraź sobie wykres funkcji w następujący sposób: domena krotki, zakres) to wierzchołek, a krawędź łączy dwa takie wierzchołki
2
@Amit: W przypadku wykresów ciągłych oznaczałoby to nieskończoną liczbę wierzchołków. To jest w porządku, ale to również sprawia, że ​​pojęcie krawędzi między wierzchołkami jest bez znaczenia. Czy na wykresie funkcji f (x) = x * 2 istnieje krawędź między (0,0) a (1,2)? Jeśli tak, to co powiesz na (0,0) i (0,5,1)? (0,0) i (0,25,0,5)? Nie ma możliwości uzyskania pojęcia krawędzi między wierzchołkami, więc tak naprawdę nie jest to wykres.
MAK
5

Struktura danych przypominająca stertę jest używana przez algorytm znajdowania dostępnej alokacji pamięci. Poniższy fragment pochodzi z http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html .

Kiedy newjest wywoływany, zaczyna szukać wolnego bloku pamięci, który pasuje do rozmiaru twojego żądania. Zakładając, że taki blok pamięci zostanie znaleziony, jest oznaczany jako zarezerwowany i zwracany jest wskaźnik do tej lokalizacji. Jest kilka algorytmów, aby to osiągnąć, ponieważ trzeba znaleźć kompromis między skanowaniem całej pamięci w celu znalezienia najmniejszego wolnego bloku większego niż rozmiar twojego obiektu lub zwróceniem pierwszego, w którym zmieści się potrzebna pamięć. Aby przyspieszyć otrzymywanie bloku pamięci, wolne i zarezerwowane obszary pamięci są utrzymywane w strukturze danych podobnej do drzew binarnych zwanych stertą.

Peng Zhang
źródło
1
Jestem bardzo sceptyczny wobec tego, a konkretnie: „... wolne i zarezerwowane obszary pamięci są utrzymywane w strukturze danych podobnej do drzew binarnych zwanych stertą”. Wydaje mi się, że autor zgaduje, że istnieje powiązanie oparte na nazwie „sterta” i prawdopodobnie się myli. Czy ktoś może potwierdzić / odrzucić?
Don Hatch
1
Po lekkich badaniach systemu Binary Buddy (używanego w systemie Linux) można go przedstawić w postaci drzewa binarnego ze względu na sposób, w jaki dzieli dane. To drzewo binarne wygląda jak poprawna maksymalna sterta, jeśli obserwujesz węzły pod względem całkowitej pamięci, ale węzły nie są wstawiane do tego drzewa binarnego, ponieważ znajdują się w maksymalnym stosie - węzły są wstawiane bezpośrednio do najmniejszego liścia wolnej pamięci> = żądany rozmiar. 1 2 3
Eric Dubé
1

Potoczne terminy pamięć stosu i pamięć sterty nie są używane w standardzie C ++. Standard wykorzystuje magazyn statyczny, magazyn wątków, magazyn automatyczny i magazyn dynamiczny.

Więcej można znaleźć w sekcji normy dotyczącej trwałości przechowywania .

Dlatego z punktu widzenia języka i standardowej biblioteki nie ma zamieszania.

R Sahu
źródło
1

P. Co to jest sterta? A. Sterta to zbiór obiektów umieszczonych jeden na drugim.

Odpowiedź na twoje pytanie: Zarówno sterta pamięci, jak i sterta binarna używają tego samego pojęcia, co wiesz. Dane są przechowywane w formie sterty w pamięci w tej samej kolejności, w jakiej są zapisywane w programie, natomiast sterta binarna to struktura danych, która opiera się na tej samej koncepcji przechowywania danych w uporządkowany sposób w postaci sterty (Data on top z drugiej). Daj mi znać, co myślisz w sekcji komentarzy.

Mayank Tolani
źródło
-2

Być może pierwsza zaimplementowana sterta pamięci była zarządzana przez strukturę sterty?

Adam Maras
źródło
8
Ta hipoteza nie wydaje się wcale oczywista - w jaki sposób sterta (struktura danych) jest w ogóle użyteczna do utrzymywania sterty (dynamicznego obszaru pamięci)?
Keith Randall
7
-1. Wolałbym autorytatywne oświadczenie z dowodami zamiast tego, co oczywiście jest tylko domysłem.
Rob Kennedy
Wysoce nieprawdopodobne. Wydaje się, że nie ma dobrego powodu, aby używać sterty (struktury danych) do zarządzania stertą (pulą wolnej pamięci).
jason