Pourquoi deux concepts différents sont-ils tous deux appelés «tas»?

170

Pourquoi le tas d'exécution est-il utilisé pour l'allocation de mémoire dynamique dans les langages de style C et la structure de données appelée «le tas»? Y a-t-il une relation?

c++ heap terminology heap-memory Andrey Fedorov
la source
4
Je me posais la question aujourd'hui en étudiant les structures de données.
MitMaro
1
question en double? http://stackoverflow.com/questions/756861/whats-the-relationship-between-a-heap-and-the-heap
timB33
3
Allez dans un dictionnaire anglais et comptez le nombre d'entrées sous "Exécuter". Combien des 40+ entrées s'appliquent aux ordinateurs? :)
jmucchiello
2
duplication possible de Quelle est la relation entre "un" tas et "le" tas?
RCIX
Un article connexe ici concernant le tas d'exécution utilisé pour l'allocation de mémoire dynamique.
RBT

Réponses:

77

Donald Knuth dit (The Art of Computer Programming, Third Ed., Vol.1, p. 435):

Plusieurs auteurs ont commencé vers 1975 à appeler le pool de mémoire disponible un «tas».

Il ne dit pas quels auteurs et ne donne aucune référence à des articles spécifiques, mais dit que l'utilisation du terme «tas» par rapport aux files d'attente prioritaires est le sens traditionnel du mot.

James McNellis
la source
11
Pool serait un meilleur nom que tas.
7
Intéressant. Quelqu'un devrait lui demander s'il se souvient de quels auteurs.
Prof. Falken
27
Wikipédia affirme que c'est parce qu'à un stade précoce Lisp a utilisé un tas (structure de données) pour implémenter sa mémoire. Ça ne dit pas comment. Sa référence est "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction aux algorithmes. MIT Press / McGraw-Hill.", Que je n'ai pas.
Steve Jessop
2
Je n'ai aucune référence pour cela, mais je suppose qu'au départ, la structure de données utilisée pour organiser les références aux blocs ouverts de mémoire était un tas min. On dirait que ce serait au moins un moyen décent de trouver rapidement le plus petit bloc de mémoire qui vous permettrait de stocker les données que vous essayez de stocker.Mise à jour: Ce que j'ai dit ressemble exactement à des blocs d' amis en.wikipedia.org/wiki/Dynamic_memory_allocation # Buddy% 5Fblocks
Will
4
@SteveJessop - Checking Cormen, Leiserson, Rivest, Stein - 3e édition (2009) au début du chapitre Heapsort, il est seulement dit «Le terme« tas »a été inventé à l'origine dans le contexte de heapsort, mais il est depuis venu à faire référence à" stockage récupéré ", comme les langages de programmation Java et Lisp fournissent. Notre structure de données de tas n'est pas un stockage avec ramasse-miettes, et chaque fois que nous nous référons aux tas dans ce livre, nous entendons une structure de données plutôt qu'un aspect du ramassage des ordures. ' CLRS - 2e édition a également presque exactement le même phrasé (aucune indication que Lisp a utilisé un tas).
dr jimbob
64

Ils portent le même nom mais ils ne sont vraiment pas similaires (même conceptuellement). Un tas de mémoire est appelé un tas de la même manière que vous appelleriez un panier à linge un "tas de vêtements". Ce nom est utilisé pour indiquer un endroit quelque peu désordonné où la mémoire peut être allouée et désallouée à volonté. La structure des données (comme le lien Wikipédia auquel vous faites référence le souligne) est assez différente.

Andrew Hare
la source
8
Oui, je pense que c'est plutôt le point sur lequel il fonde sa question: ils sont différents. Alors pourquoi sont-ils appelés la même chose - y a-t-il une relation sous-jacente?
Sean Owen
9
La façon dont j'ai interprété cette réponse est "non, il n'y a pas de relation sous-jacente", donc cela répond à la question.
Laurence Gonsalves
Andrew répond à cela. Il n'y a pas de relation. Juste une coïncidence. Le tas de mémoire est plus fidèle à l'usage courant puisque la mémoire est allouée comme s'il s'agissait d'un "tas de vêtements". La structure des données exigeait cependant un plus grand effort d'imagination. Et cela devient un «pourquoi» beaucoup plus intéressant. Le nom vient du fait que les nœuds sont organisés par leur clé et qu'une clé de nœud parent est toujours> = que son nœud enfant.
Alexandre Bell
6
Ils ne sont certainement pas liés. Cependant, le problème de l'appeler "le tas" est que "l'homologue du tas" - "la pile" - est aussi une pile réelle.
dan
1
Je sais pourquoi la structure de données de tas s'appelle un tas: parce qu'elle satisfait la propriété de tas. Mais pourquoi la propriété de tas est-elle appelée telle? Cela n'a aucun sens pour moi, car un nom comme "top heavy" serait bien meilleur.
Thomas Eding
31

La collision de noms est malheureuse, mais pas si mystérieuse. Heap est un petit mot courant utilisé pour désigner une pile, une collection, un groupe, etc. L'utilisation du mot pour la structure de données précède (j'en suis sûr) le nom du pool de mémoire. En fait, la piscine aurait été un bien meilleur choix pour ce dernier, à mon avis. Heap connote une structure verticale (comme une pile), qui correspond à la structure de données, mais pas au pool de mémoire. Nous ne considérons pas un tas de pool de mémoire comme hiérarchique, alors que l'idée fondamentale derrière la structure de données est de garder le plus grand élément en haut du tas (et des sous-tas).

Heap la structure des données remonte au milieu des années 60; tas de mémoire, le début des années 70. Le terme tas (qui signifie pool de mémoire) a été utilisé au moins dès 1971 par Wijngaarden dans les discussions sur Algol.

Peut-être que la première utilisation du tas comme structure de données se trouve sept ans plus tôt dans
Williams, JWJ 1964. "Algorithm 232 - Heapsort", Communications of the ACM 7 (6): 347-348

IJ Kennedy
la source
1
Oui, mais un tas implique également le désordre et les tas de mémoire sont généralement désordonnés. Le tas de structure de données est extrêmement bien ordonné. Donc, encore une fois, il y a un décalage égal dans l'autre sens basé sur la définition commune du tas.
jmucchiello
Il est toujours présenté comme l'opposé de stack, ce qui devrait suffire à expliquer le nom IMO.
reinierpost
1
Ce n'est pas un hasard - la liste gratuite peut être implémentée en tant que file d'attente prioritaire via un tas binomial.
Heath Hunnicutt
2
@jmucchiello: un tas de bûches (voir photo ) est bien ordonné et ressemble à un arbre. C'est l'origine du nom de la structure de données selon l'un de mes manuels de premier cycle.
gioele
6

En fait, lire sur la façon dont la mémoire est allouée (voir Buddy Blocks ) me rappelle un tas de structures de données.

Tech Guy itinérant
la source
Mon commentaire sur la réponse de Peter Zhang est également pertinent ici. Le système de jumelage binaire peut être représenté comme un arbre binaire, et il ressemble également à un tas max valide lorsque la "clé" de chaque nœud est la mémoire totale en dessous (mais ces valeurs sont implicites et ne changent jamais). Ni l'allocation ni l'algorithme de libération n'utilisent d'opérations de tas sur cet arbre binaire, pour autant que je sache.
Eric Dubé
5

OMI c'est simplement un accident / coïncidence que ces deux choses totalement indépendantes aient le même nom. C'est comme un graphique et un graphique .

MAK
la source
Les deux graphiques peuvent cependant être liés d'une manière ou d'une autre. Imaginez le graphique d'une fonction comme suit: Le domaine du tuple, plage) est un sommet et une arête connecte deux de ces sommets
2
@Amit: Pour les graphes continus, cela signifierait un nombre infini de sommets. C'est correct, mais cela rend également le concept d'arêtes entre les sommets dénué de sens. Dans le graphique de la fonction f (x) = x * 2, y a-t-il une arête entre (0,0) et (1,2)? Si oui, qu'en est-il de (0,0) et (0,5,1)? (0,0) et (0,25,0,5)? Il n'y a aucun moyen d'avoir le concept d'arête entre les sommets, donc ce n'est pas vraiment un graphe.
MAK
5

Une structure de données semblable à un tas est utilisée par l'algorithme de recherche d'allocation de mémoire disponible. Ce qui suit est extrait de http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html .

Quand newest invoqué, il commence à rechercher un bloc de mémoire libre qui correspond à la taille de votre demande. En supposant qu'un tel bloc de mémoire soit trouvé, il est marqué comme réservé et un pointeur vers cet emplacement est renvoyé. Il existe plusieurs algorithmes pour accomplir cela car un compromis doit être fait entre le balayage de toute la mémoire pour trouver le plus petit bloc libre plus grand que la taille de votre objet, ou le retour du premier où la mémoire nécessaire tient. Afin d'améliorer la vitesse d'obtention d'un bloc de mémoire, les zones de mémoire libres et réservées sont conservées dans une structure de données similaire aux arbres binaires appelée tas.

Peng Zhang
la source
1
Je suis extrêmement sceptique à ce sujet, en particulier "... les zones libres et réservées de la mémoire sont conservées dans une structure de données similaire à des arbres binaires appelés tas". Il me semble que l'auteur est en train de deviner qu'il y a une connexion, basée sur le nom "tas", et qu'il se trompe probablement. Quelqu'un peut-il confirmer / réfuter?
Don Hatch
1
Après quelques recherches légères sur le système Binary Buddy (utilisé sous Linux), il peut être représenté par un arbre binaire en raison de la façon dont il partitionne les données. Cet arbre binaire ressemble à un tas max valide si vous observez les nœuds en termes de mémoire totale, mais les nœuds ne sont pas insérés dans cet arbre binaire car ils sont dans un tas max - les nœuds sont insérés directement dans la plus petite feuille de mémoire libre> = la taille demandée. 1 2 3
Eric Dubé
1

Les termes familiers de mémoire de pile et de mémoire de tas ne sont pas utilisés dans la norme C ++. La norme utilise le stockage statique, le stockage des threads, le stockage automatique et le stockage dynamique.

Plus d'informations peuvent être trouvées dans la section Stockage Duraction de la norme.

Par conséquent, du point de vue du langage et de la bibliothèque standard, il n'y a pas de confusion.

R Sahu
la source
1

Q. Qu'est-ce qu'un tas? A. Un tas est une collection d'objets placés les uns sur les autres.

Réponse à votre question: le tas de mémoire et le tas binaire utilisent le même concept que vous connaissez. Les données sont stockées sous la forme d'un tas dans la mémoire dans le même ordre que celui écrit dans le programme alors que le tas binaire est une structure de données qui suit le même concept de stockage des données de manière ordonnée sous la forme d'un tas (Données en haut de l'autre). Dites-moi ce que vous pensez dans la section commentaires.

Mayank Tolani
la source
-2

Peut-être que le premier tas de mémoire implémenté a été géré par une structure de tas?

Adam Maras
la source
8
Cette hypothèse ne semble pas du tout évidente - en quoi un tas (la structure de données) est-il utile du tout pour maintenir un tas (la région de mémoire dynamique)?
Keith Randall
7
-1. Je préférerais une déclaration faisant autorité avec des preuves au lieu de ce qui n'est évidemment qu'une supposition.
Rob Kennedy
Hautement improbable. Il semble n'y avoir aucune bonne raison d'utiliser un tas (la structure de données) pour gérer le tas (le pool de mémoire libre).
jason