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

Question

Comme je l'ai été de la programmation, je n'ai pas vu un cas où un tableau est mieux pour stocker des informations à toute autre forme de celle-ci. J'avais en effet compris l'ajout de "features" dans les langages de programmation avait amélioré ce et par qui les ont remplacés. Je vois maintenant qu'ils ne sont pas remplacé, mais plutôt donné une nouvelle vie, pour ainsi dire.

Donc, fondamentalement, ce qui est le point de l'utilisation des tableaux?

Ce n'est pas tellement pourquoi utiliser des tableaux à partir d'un ordinateur point de vue, mais plutôt pourquoi devrions-nous utiliser des tableaux à partir d'un point de vue de la programmation (une subtile différence). Ce que l'ordinateur fait avec le tableau n'était pas le point de la question.

Answer 1

Le temps de revenir en arrière dans le temps pour une leçon. Alors que nous ne pense pas à ces choses dans notre fantaisie géré langues aujourd'hui, ils sont construits sur la même base, voyons donc comment la mémoire est gérée en C.

Avant de plonger dans, une explication rapide de ce que le terme de "pointeur". Un pointeur est simplement une variable "points" pour un emplacement dans la mémoire. Il ne contient pas la valeur réelle à cette zone de la mémoire, il contient l'adresse de la mémoire. Pensez à un bloc de la mémoire comme une boîte aux lettres. Le pointeur serait l'adresse de la boîte aux lettres.

En C, un tableau est simplement un pointeur avec un décalage, le décalage précise dans quelle mesure en mémoire à regarder. Cette offre O(1) temps d'accès.

  MyArray   [5]
     ^       ^
  Pointer  Offset

Toutes les autres structures de données, soit de construire sur ce, ou de ne pas utiliser adjacentes de la mémoire pour le stockage, ce qui entraîne un mauvais accès aléatoire regarder de temps (même Si il y a d'autres avantages à ne pas utiliser sequential memory).

Par exemple, disons que nous avons un tableau avec 6 numéros (6,4,2,3,1,5), à la mémoire, elle devrait ressembler à ceci:

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

Dans un tableau, nous savons que chaque élément est à côté les uns des autres dans la mémoire. Un C array (Appelé MyArray ici) est tout simplement un pointeur vers le premier élément:

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

Si nous voulions chercher Montableau[4], à l'interne, il serait accessible comme ceci:

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

Car on peut directement accéder à un élément du tableau en ajoutant le décalage du pointeur, on peut trouver n'importe quel élément dans le même laps de temps, indépendamment de la taille de la matrice. Cela signifie que l'obtention d'Montableau[1000] prendrait la même quantité de temps que l'obtention de la Montableau[5].

Une alternative structure de données est une liste liée. C'est 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 chaque "nœud" dans son propre bloc. C'est parce qu'ils ne sont pas garantis d'être (et de plus ne sera probablement pas) adjacents dans la mémoire.

Si je veux accéder à P3, je ne peux pas accéder directement, parce que je ne sais pas où il est dans la mémoire. Tout ce que je sais où est la racine (P1) est, donc je dois commencer à P1, et de suivre chaque pointeur vers le nœud désiré.

C'est un O(N) temps (Les hausses des coûts de chaque élément est ajouté). Il est beaucoup plus coûteux P1000 par rapport à l'obtention de P4.

Niveau plus élevé de structures de données, telles que les tables de hachage, les piles et les files d'attente, tous peuvent utiliser un tableau (ou de plusieurs tableaux) à l'intérieur des Listes et Arbres Binaires utilisent généralement des nœuds et des pointeurs.

Vous pourriez vous demander pourquoi quelqu'un serait d'utiliser une structure de données qui nécessite linéaire de la traversée de la valeur plutôt que de simplement en utilisant un tableau, mais ils ont leurs usages.

Prendre notre gamme de nouveau. Cette fois, je veux trouver l'élément du tableau qui contient la valeur 5.

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

Dans cette situation, je ne sais pas ce décalage à ajouter à le pointeur de la trouver, j'ai donc commencer à 0, et de travailler mon chemin jusqu'à jusqu'à ce que je le trouve. Cela signifie que je dois effectuer 6 contrôles.

De ce fait, la recherche d'une valeur dans un tableau est considéré comme O(N). Le coût de la recherche augmente à mesure que le tableau devient plus grand.

Rappelez-vous, au-dessus où j'ai dit que, parfois, l'aide d'un non séquentiel structure de données peut 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 liée, cependant au lieu de le relier à un seul nœud, chaque nœud peut relier deux nœuds enfants.

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

 Assume that each connector is really a Pointer

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

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

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

Lors de la recherche un arbre binaire de la valeur de 75, nous avons seulement besoin pour visiter les 3 noeuds ( O(log N) ), en raison de cette structure:

• Est de 75 à moins de 100? Regardez Droit Nœud
• Est de 75 à plus de 50? Regardez Nœud de Gauche
• Il est le 75!

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

C'est là que les tableaux se faire battre, ils fournissent une constante O(N) le temps de recherche, en dépit de O(1) temps d'accès.

C'est un très haut de niveau vue d'ensemble sur les structures de données en mémoire, sautant sur beaucoup de détails, mais j'espère qu'il illustre un tableau de la force et de faiblesse par rapport à d'autres structures de données.

Answer 2

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

Answer 3

Peut-être que vous n'êtes pas au courant, mais la plupart des classes de collection utiliser les tableaux en tant que base mécanisme de stockage...

Un exemple dans la .Termes NETS est la liste de tableaux:

public class ArrayList : IList, ICollection, IEnumerable, ICloneable
{
    // Fields
    private const int _defaultCapacity = 4;
    private object[] _items; // <<<<<<<<<<<<<<<<<<<<<<<<<<< See this array?
    private int _size;
    [NonSerialized]
    private object _syncRoot;
    private int _version;
    private static readonly object[] emptyArray;

Maintenant, nous regardons un typique tapé classe de collection, StringCollection:

public class StringCollection : IList, ICollection, IEnumerable
{
    // Fields
    private ArrayList data; // <<<<<<<<< Stores its items internally in an ArrayList

La même chose se produit pour une Liste générique:

public class List<T> : IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection, IEnumerable
{
    // Fields
    private const int _defaultCapacity = 4;
    private static T[] _emptyArray;
    private T[] _items; // <<<<<<<<<<<<<<<<<<<<< See the array?
    private int _size;
    [NonSerialized]
    private object _syncRoot;
    private int _version;

J'ai l'impression de votre question que vous pensez que tous ces newfangled les moyens de stocker des collections d'articles ont remplacé le tableau, mais en fait, ils n'ont pas. Elles viennent en complément de beaucoup.

Answer 4

Pas tous les programmes de faire la même chose ou de s'exécuter sur le même matériel.

C'est généralement la réponse pourquoi les différentes fonctionnalités de la langue existent. Les tableaux sont une informatique de base concept de science. Le remplacement des tableaux avec des listes ou des matrices/vecteurs/quel que soit l'avancée de la structure de données serait gravement affecter les performances, et être carrément impossible dans un certain nombre de systèmes. Il ya un certain nombre de cas où l'utilisation d'un de ces "avancées" de la collecte de données les objets doivent être utilisés en raison de le programme en question.

Dans l'entreprise de programmation (dont la plupart d'entre nous), nous pouvons cibler le matériel qui est relativement puissant. À l'aide d'une Liste en C# ou Vecteur en Java est le bon choix à faire dans ces situations, car ces structures permettent au développeur pour atteindre les objectifs plus rapidement, ce qui à son tour permet à ce type de logiciel afin d'être plus complet.

Lors de l'écriture de logiciels embarqués ou un système d'exploitation d'un tableau peut souvent être le meilleur choix. Tout un ensemble offre moins de fonctionnalités, il prend moins de RAM, et le compilateur peut optimiser le code de manière plus efficace pour look-ups dans des tableaux.

Je suis sûr que j'en laissant de côté un certain nombre d'avantages pour ces cas, mais j'espère que vous obtenez le point.

Answer 5

Peut-être juste parce qu'ils sont la première chose qui vient à l'esprit lorsque l'on veut stocker une "collection" d'éléments dans un "set".

Peut-être qu'ils sont la plus ancienne structure dans les langages de programmation pour stocker une collection de données, dans un naturellement, triés manière (j'.e 1-1 correspondance avec les nombres entiers positifs).

Toutes les autres structures sont certaines formes et les détournements de tableaux.

Si votre question est: pourquoi les tableaux sont la première chose à l'esprit lorsque l'on veut stocker une collection? La question peut changer à "pourquoi les humains?", "Comment nous classer?", "Est-il une définition pour un jeu?" etc.