Aller au contenu principal

Les données en mémoire

La mémoire20 min

Cases contiguës, liens, adresses et coût réel des accès.

Dans cette leçon

Deux façons de ranger les données

La mémoire ne connaît ni liste, ni pile, ni arbre. Elle conserve des valeurs dans des emplacements concrets. Toutes les structures de ce parcours partent de deux idées : placer les données côte à côte, ou relier des morceaux placés ailleurs.

Contigu

Les cases se suivent. À partir d'une adresse de départ, un calcul permet de trouver directement une position.

Non contigu

Les morceaux peuvent être dispersés. Une référence indique où trouver le morceau suivant.

Nous utilisons ici un modèle volontairement simple : des adresses décimales fictives et des entiers de 4 octets. Ce modèle ne décrit pas tous les détails d'un ordinateur. Il suffit pour voir les copies, les décalages et les parcours que vos structures provoquent.

  1. Repérez le comportement attendu

    Cherchez-vous une valeur par position, ajoutez-vous souvent au début, ou suivez-vous surtout des relations entre objets ?

  2. Dessinez le rangement

    Représentez les cases ou les nœuds avant d'analyser une opération.

  3. Comptez les gestes

    Nommez les lectures, écritures, copies, décalages ou liens suivis. Le coût devient alors visible.

Contigu : Des cases qui se suivent

base : @2404 octets par casecapacité : 8 casesget(i) : 1 accès

Un tableau réserve un bloc de cases voisines. Si sa première case commence à l'adresse 240 et qu'une case occupe 4 octets, l'adresse de l'index i vaut 240 + i × 4.

Le calcul qui remplace le parcours

Pour lire l'index 3, la machine calcule 240 + 3 × 4 = 252. Elle ne lit pas les index 0, 1 et 2.
Scores.java

Force

  • Une position se traduit directement en adresse.
  • Les valeurs restent regroupées dans un bloc compact.

Limite

  • Il faut réserver une capacité.
  • Insérer au milieu oblige les voisins à se décaler.

Réponse possible

  • Allouer un bloc plus grand et recopier les valeurs.
  • Choisir des liens si les modifications locales dominent.

Non contigu : Des nœuds reliés

Dans une liste chaînée, chaque nœud contient une valeur et une référence vers le suivant. Les nœuds ci-dessous sont dessinés sur une ligne pour rester lisibles. En mémoire, ils peuvent se trouver à des adresses éloignées.

Node.java

Une référence n'est pas l'objet

Le champ next ne contient pas une copie du prochain nœud. Il contient son adresse. Pour atteindre le troisième nœud, il faut suivre les liens un à un depuis head : @584 (head) → @316 → @972. Il faut donc trois accès pour récupérer la valeur 7.

Les liens conviennent bien

  • • La structure grandit sans recopier un grand bloc.
  • • Vous modifiez souvent autour d'un nœud déjà trouvé.
  • • L'ordre logique compte plus que l'accès par index.

Les liens coûtent cher

  • • Vous demandez souvent le n-ième élément.
  • • Chaque nœud ajoute au moins une référence.
  • • Chaque saut vers le prochain nœud demande un accès.

Comparer les gestes réels

Dire qu'une structure est « rapide » ne suffit pas. Nommez l'opération et ce qu'elle oblige la mémoire à faire.

QuestionCases contiguësNœuds reliés
Trouver l'élément d'index i
Coût faible

Calculer son adresse, puis lire une case.

Coût élevé

Partir d'un point d'entrée connu, puis suivre les liens jusqu'à la valeur recherchée.

Insérer au début
Coût élevé

Décaler chaque valeur existante d'une case.

Coût faible

Créer un nœud et changer quelques références.

Grandir quand l'espace manque
Coût élevé

Réserver un autre bloc et recopier les valeurs.

Coût faible

Allouer un nœud supplémentaire.

Des repères, pas des règles

Le nom d'une structure donne un point de départ. Une solution réelle combine souvent plusieurs mécanismes, comme un répertoire contigu et des blocs séparés. Comprenez les accès, les copies et les liens réellement nécessaires, puis composez une représentation adaptée à vos besoins. Les structures classiques restent des repères : votre variante doit aussi préserver leurs invariants et leurs coûts.

Quand les deux modèles se combinent

Les deux modèles peuvent coopérer. Un petit répertoire contigu garde des références vers des blocs de taille fixe, alloués séparément.

Répertoire contigu

[0]bloc 0
[1]bloc 1
[2]bloc 2

Bloc 0

0
1
2
3

Bloc 1

4
5
6
7

Bloc 2

8
9
10
11

i = 10 → bloc 2, position 2

  1. Trouvez le bloc

    Avec des blocs de 4 valeurs, l'index 10 appartient au bloc 10 / 4 = 2.

  2. Trouvez la position dans le bloc

    Le reste de la division donne 10 % 4 = 2.

  3. Suivez les deux accès

    Lisez d'abord la référence du bloc 2 dans le répertoire, puis la position 2 dans ce bloc.

Ce n'est pas une troisième base

Le répertoire utilise la contiguïté. Les blocs utilisent des références : le tableau par blocs combine donc les deux modèles. Un buffer circulaire fait autre chose : il garde un seul tableau contigu et réinterprète ses indices grâce au modulo.

Vérifiez vos réflexes

Vérifiez vos réflexes

Une réponse par question. La correction apparaît tout de suite.

1. Un tableau commence à l'adresse 240 et chaque case occupe 4 octets. Quelle est l'adresse de la case d'index 3 ?
2. Pourquoi la machine peut-elle atteindre directement la case 3 d'un tableau ?
3. Que doit faire un tableau qui contient n valeurs pour insérer une nouvelle valeur au début ?
4. Quel énoncé décrit une liste chaînée en mémoire ?
5. Que combine un tableau par blocs ?

Continuez le parcours

Vous savez maintenant distinguer le rangement des données. La leçon suivante sépare cette question d'une autre : que doit permettre la structure ?

TAD et structures de donnéesLe contrat définit ce que vous pouvez faire. L'implémentation détermine comment ces opérations sont réalisées.Listes, piles et filesTableaux, maillons, LIFO, FIFO et buffer circulaire.

Centre de commandes

Rechercher une page et s'y rendre