Pourquoi utilisons-nous des tableaux au lieu d'autres structures de données?

Pendant que je programmais, je n'ai pas vu d'instance où un tableau est meilleur pour stocker des informations qu'une autre forme de celles-ci. J'avais en effet pensé que les "fonctionnalités" ajoutées dans les langages de programmation s'étaient améliorées et que cela les avait remplacées. Je vois maintenant qu'ils ne sont pas remplacés mais plutôt donnés une nouvelle vie, pour ainsi dire.

Donc, en gros, quel est l'intérêt d'utiliser des tableaux?

Ce n'est pas tant pourquoi utilisons-nous des tableaux d'un point de vue informatique, mais plutôt pourquoi utiliserions-nous des tableaux d'un point de vue de programmation (une différence subtile). Ce que l'ordinateur fait avec la baie n'était pas le point de la question.

Il est temps de remonter le temps pour une leçon. Bien que nous ne pensions pas beaucoup à ces choses dans nos langages gérés de fantaisie aujourd'hui, ils sont construits sur la même base, alors regardons comment la mémoire est gérée en C.

Avant de plonger, une brève explication de la signification du terme " pointeur ". Un pointeur est simplement une variable qui "pointe" vers un emplacement en mémoire. Il ne contient pas la valeur réelle dans cette zone de mémoire, il contient l'adresse de mémoire qui lui est associée. Considérez un bloc de mémoire comme une boîte aux lettres. Le pointeur serait l'adresse de cette boîte aux lettres.

En C, un tableau est simplement un pointeur avec un décalage, le décalage spécifie la distance à parcourir en mémoire. Cela donne le temps d'accès O (1) .

  MyArray   [5]
     ^       ^
  Pointer  Offset

Toutes les autres structures de données s'appuient sur cela ou n'utilisent pas de mémoire adjacente pour le stockage, ce qui entraîne un mauvais temps de recherche d'accès aléatoire (bien qu'il y ait d'autres avantages à ne pas utiliser de mémoire séquentielle).

Par exemple, disons que nous avons un tableau avec 6 nombres (6,4,2,3,1,5), en mémoire cela ressemblerait à ceci:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================

Dans un tableau, nous savons que chaque élément est côte à côte en mémoire. Le tableau AC (appelé MyArrayici) est simplement un pointeur vers le premier élément:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^
MyArray

Si nous voulions rechercher MyArray[4], en interne, il serait accessible comme ceci:

   0     1     2     3     4 
=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
                           ^
MyArray + 4 ---------------/
(Pointer + Offset)

Étant donné que nous pouvons accéder directement à n'importe quel élément du tableau en ajoutant l'offset au pointeur, nous pouvons rechercher n'importe quel élément dans le même laps de temps, quelle que soit la taille du tableau. Cela signifie que l'obtention MyArray[1000]prendrait le même temps que l'obtention MyArray[5].

Une autre structure de données est une liste chaînée. Il s'agit d'une liste linéaire de pointeurs, chacun pointant vers le nœud suivant

========    ========    ========    ========    ========
| Data |    | Data |    | Data |    | Data |    | Data |
|      | -> |      | -> |      | -> |      | -> |      | 
|  P1  |    |  P2  |    |  P3  |    |  P4  |    |  P5  |        
========    ========    ========    ========    ========

P(X) stands for Pointer to next node.

Notez que j'ai fait de chaque "nœud" son propre bloc. En effet, ils ne sont pas garantis (et ne seront probablement pas) adjacents en mémoire.

Si je veux accéder à P3, je ne peux pas y accéder directement, car je ne sais pas où il est en mémoire. Tout ce que je sais, c'est où se trouve la racine (P1), donc je dois commencer à P1 et suivre chaque pointeur jusqu'au nœud souhaité.

Il s'agit d'un temps de recherche O (N) (le coût de recherche augmente à mesure que chaque élément est ajouté). Il est beaucoup plus cher de se rendre au P1000 que de se rendre au P4.

Les structures de données de niveau supérieur, telles que les tables de hachage, les piles et les files d'attente, peuvent toutes utiliser un tableau (ou plusieurs tableaux) en interne, tandis que les listes liées et les arbres binaires utilisent généralement des nœuds et des pointeurs.

Vous vous demandez peut-être pourquoi quelqu'un utiliserait une structure de données qui nécessite une traversée linéaire pour rechercher une valeur au lieu de simplement utiliser un tableau, mais ils ont leur utilité.

Reprenez notre tableau. Cette fois, je veux trouver l'élément de tableau qui contient la valeur «5».

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^     ^     ^     ^     ^   FOUND!

Dans cette situation, je ne sais pas quel décalage ajouter au pointeur pour le trouver, je dois donc commencer à 0 et remonter jusqu'à ce que je le trouve. Cela signifie que je dois effectuer 6 vérifications.

Pour cette raison, la recherche d'une valeur dans un tableau est considérée comme O (N). Le coût de la recherche augmente à mesure que le tableau s'agrandit.

Rappelez-vous ci-dessus où j'ai dit que l'utilisation d'une structure de données non séquentielle peut parfois avoir des avantages? La recherche de données est l'un de ces avantages et l'un des meilleurs exemples est l'arbre binaire.

Un arbre binaire est une structure de données similaire à une liste chaînée, mais au lieu de se lier à un seul nœud, chaque nœud peut se lier à deux nœuds enfants.

         ==========
         |  Root  |         
         ==========
        /          \ 
  =========       =========
  | Child |       | Child |
  =========       =========
                  /       \
            =========    =========
            | Child |    | Child |
            =========    =========

 Assume that each connector is really a Pointer

Lorsque des données sont insérées dans un arbre binaire, elles utilisent plusieurs règles pour décider où placer le nouveau nœud. Le concept de base est que si la nouvelle valeur est supérieure aux parents, elle l'insère à gauche, si elle est inférieure, elle l'insère à droite.

Cela signifie que les valeurs dans un arbre binaire pourraient ressembler à ceci:

         ==========
         |   100  |         
         ==========
        /          \ 
  =========       =========
  |  200  |       |   50  |
  =========       =========
                  /       \
            =========    =========
            |   75  |    |   25  |
            =========    =========

Lors de la recherche d'un arbre binaire pour la valeur de 75, il suffit de visiter 3 nœuds (O (log N)) à cause de cette structure:

• Est-ce que 75 est inférieur à 100? Regardez le nœud droit
• 75 est-il supérieur à 50? Regardez le nœud gauche
• Il y a le 75!

Même s'il y a 5 nœuds dans notre arbre, nous n'avons pas eu besoin de regarder les deux autres, car nous savions qu'ils (et leurs enfants) ne pouvaient pas contenir la valeur que nous recherchions. Cela nous donne un temps de recherche qui, dans le pire des cas, signifie que nous devons visiter chaque nœud, mais dans le meilleur des cas, nous n'avons qu'à visiter une petite partie des nœuds.

C'est là que les tableaux sont battus, ils fournissent un temps de recherche linéaire O (N), malgré le temps d'accès O (1).

Il s'agit d'un aperçu incroyablement élevé des structures de données en mémoire, ignorant de nombreux détails, mais nous espérons qu'il illustre la force et la faiblesse d'un tableau par rapport à d'autres structures de données.

Pour O (1) accès aléatoire, qui ne peut pas être battu.

Tous les programmes ne font pas la même chose ou ne s'exécutent pas sur le même matériel.

C'est généralement la réponse pour laquelle diverses fonctionnalités de langage existent. Les tableaux sont un concept informatique fondamental. Le remplacement de tableaux par des listes / matrices / vecteurs / quelle que soit la structure de données avancée aurait un impact sérieux sur les performances et serait carrément impraticable dans un certain nombre de systèmes. Il existe un certain nombre de cas où l'utilisation de l'un de ces objets de collecte de données "avancés" devrait être utilisée en raison du programme en question.

Dans la programmation d'entreprise (ce que la plupart d'entre nous font), nous pouvons cibler du matériel relativement puissant. Utiliser une liste en C # ou un vecteur en Java est le bon choix à faire dans ces situations car ces structures permettent au développeur d'atteindre les objectifs plus rapidement, ce qui permet à ce type de logiciel d'être plus en vedette.

Lors de l'écriture d'un logiciel intégré ou d'un système d'exploitation, une baie peut souvent être le meilleur choix. Alors qu'un tableau offre moins de fonctionnalités, il prend moins de RAM et le compilateur peut optimiser le code plus efficacement pour les recherches dans les tableaux.

Je suis sûr que je laisse de côté un certain nombre d'avantages pour ces cas, mais j'espère que vous comprendrez.

Un moyen de regarder les avantages des tableaux est de voir où est la capacité d'accès O (1) des tableaux est nécessaire et donc capitalisée:

1. Dans les tables de recherche de votre application (un tableau statique pour accéder à certaines réponses catégorielles)

2. Mémorisation (résultats de fonctions complexes déjà calculés, de sorte que vous ne calculez plus la valeur de la fonction, par exemple log x)

3. Applications de vision par ordinateur à haute vitesse nécessitant un traitement d'image ( https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing )