c++ - pointer - stack vs heap java




Warum werden zwei verschiedene Konzepte beide "Heap" genannt? (6)

Das Lesen der Speicherbelegung (siehe Buddy Blocks ) erinnert mich an einen Heap in Datenstrukturen.

Warum wird der Runtime-Heap für die dynamische Speicherzuweisung in C-artigen Sprachen und die Datenstruktur, die beide "Heap" genannt werden, verwendet? Gibt es eine Beziehung?


Der Name Kollision ist bedauerlich, aber nicht so geheimnisvoll. Heap ist ein kleines, geläufiges Wort, das für einen Stapel, eine Sammlung, eine Gruppe usw. verwendet wird. Die Verwendung des Wortes für die Datenstruktur liegt (ich bin mir ziemlich sicher) vor dem Namen des Speicherpools. In der Tat, Pool wäre meiner Meinung nach eine viel bessere Wahl für Letzteres gewesen. Heap bezeichnet eine vertikale Struktur (wie einen Stapel), die zur Datenstruktur passt, aber nicht zum Speicherpool. Wir denken nicht, dass ein Speicherpool-Heap hierarchisch ist, während der Grundgedanke hinter der Datenstruktur darin besteht, das größte Element an der Spitze des Heaps (und Sub-Heaps) zu halten.

Heap die Datenstruktur stammt aus der Mitte der 60er Jahre; haufen Sie den Speicherpool, Anfang der 70er Jahre. Der Begriff Heap (Bedeutung Speicherpool) wurde mindestens 1971 von Wijngaarden in Diskussionen von Algol verwendet.

Die früheste Verwendung von Heap als Datenstruktur findet sich möglicherweise sieben Jahre zuvor in
Williams, JWJ 1964. "Algorithmus 232 - Heapsort", Mitteilungen der ACM 7 (6): 347-348


Donald Knuth sagt (Die Kunst der Computerprogrammierung, 3. Auflage, Bd. 1, S. 435):

Mehrere Autoren begannen etwa 1975, den Vorrat an verfügbarem Speicher einen "Haufen" zu nennen.

Er sagt nicht, welche Autoren und verweist nicht auf bestimmte Papiere, aber sagt, dass die Verwendung des Begriffs "Heap" in Bezug auf Prioritätswarteschlangen der traditionelle Sinn des Wortes ist.


Heap-like Datenstruktur wird von Algorithmus zum Finden verfügbarer Speicherzuweisung verwendet. Das Folgende ist aus http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html .

Wenn new aufgerufen wird, sucht es nach einem freien Speicherblock, der der Größe für Ihre Anfrage entspricht. Angenommen, dass ein solcher Speicherblock gefunden wird, wird er als reserviert markiert und ein Zeiger auf diesen Speicherort wird zurückgegeben. Es gibt mehrere Algorithmen, um dies zu erreichen, da ein Kompromiss zwischen dem Scannen des gesamten Speichers zum Finden des kleinsten freien Blocks, der größer als die Größe des Objekts ist, oder dem Zurückgeben des ersten Speicherplatzes, an den der Speicher benötigt wird, gemacht werden muss. Um die Geschwindigkeit des Erhalts eines Speicherblocks zu verbessern, werden die freien und reservierten Speicherbereiche in einer Datenstruktur gehalten, die den Binärbäumen ähnelt, die als Heap bezeichnet werden.


Sie haben den gleichen Namen, aber sie sind wirklich nicht ähnlich (auch nicht konzeptionell). Ein Speicher-Heap wird als Heap bezeichnet, genauso wie man einen Wäschekorb als "Heap of Clothes" bezeichnen würde. Dieser Name wird verwendet, um einen etwas unordentlichen Ort anzugeben, an dem Speicher nach Belieben zugewiesen und freigegeben werden kann. Die Datenstruktur (wie der Wikipedia-Link, auf den du dich beziehst) ist ganz anders.


Vielleicht wurde der erste implementierte Speicher-Heap von einer Heap-Struktur verwaltet?







heap-memory