191 votos

¿Por qué usamos las matrices en lugar de otras estructuras de datos?

Como yo estaba de programación, no he visto un caso en el que una matriz es mejor para almacenar información que la otra forma de la misma. I en efecto, había descubierto el añadido de las "características" de los lenguajes de programación había mejorado en esto y por que los sustituyan. Ahora veo que no sustituye sino que le da la vida nueva, por así decirlo.

Así que, básicamente, ¿cuál es el punto de la utilización de matrices?

Esto no es tanto por qué se utilizan las matrices de un equipo punto de vista, sino más bien ¿por qué hemos de utilizar matrices desde un punto de vista de la programación (una sutil diferencia). Lo que hace la computadora con la matriz no era el punto de la cuestión.

763voto

FlySwat Puntos 61945

Tiempo para volver atrás en el tiempo para una lección. Si bien no piensa acerca de estas cosas en nuestra imaginación lenguajes administrados hoy en día, se basan en el mismo fundamento, así que echemos un vistazo a cómo la memoria se gestiona en C.

Antes de profundizar en el, una breve explicación de lo que el término "puntero". Un puntero es simplemente una variable en la que "apunta" a una ubicación en la memoria. No contiene el valor real en esta área de memoria que contiene la dirección de memoria. Pensar en un bloque de memoria como un buzón. El puntero sería la dirección del buzón de correo.

En C, una matriz es simplemente un puntero con un offset, el offset especifica lo lejos en la memoria para mirar. Esto proporciona O(1) tiempo de acceso.

  MyArray   [5]
     ^       ^
  Pointer  Offset

Todas las demás estructuras de datos ya sea para construir sobre esto, o no uso de memoria adyacente para el almacenamiento, resultando en una pobre acceso aleatorio buscar tiempo (Aunque hay otros beneficios de no usar la memoria secuencial).

Por ejemplo, supongamos que tenemos un array con 6 números (6,4,2,3,1,5), en la memoria se vería así:

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

En una matriz, sabemos que cada elemento es uno al lado del otro en la memoria. Una matriz C (Llamado MyArray aquí) es simplemente un puntero al primer elemento:

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

Si queremos buscar MyArray[4], internamente se accede como este:

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

Porque podemos acceder directamente a cualquier elemento de la matriz mediante la adición de un desplazamiento para el puntero, podemos buscar cualquier elemento en la misma cantidad de tiempo, independientemente del tamaño de la matriz. Esto significa que llegar MyArray[1000] sería tomar la misma cantidad de tiempo como llegar MyArray[5].

Una alternativa de estructura de datos es una lista vinculada. Esta es una lista lineal de los punteros, cada una apuntando a la siguiente nodo

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

P(X) stands for Pointer to next node.

Tenga en cuenta que he hecho cada "nodo" en su propio bloque. Esto es porque ellos no están garantizadas a ser (y probablemente no va a ser) adyacentes en la memoria.

Si desea tener acceso a P3, yo directamente no se puede acceder a ella, porque no sé donde está en la memoria. Todo lo que sé es donde está la raíz (P1) es, en lugar de eso tengo que empezar a P1, y el seguimiento de cada puntero al nodo deseado.

Este es un O(N) buscar el tiempo (La mirada hasta el costo aumenta a medida que cada elemento es añadido). Es mucho más caro llegar a P1000 en comparación a llegar a P4.

Mayor nivel de estructuras de datos, tales como tablas hash, pilas y colas, todos pueden usar un array (o de múltiples matrices) internamente, mientras que las Listas Enlazadas y Árboles Binarios normalmente el uso de nodos y enlaces.

Usted podría preguntarse por qué alguien querría usar una estructura de datos que requiere lineales de recorrido para buscar un valor en lugar de simplemente utilizar una matriz, pero ellos tienen sus usos.

Tome nuestra matriz de nuevo. Esta vez, quiero encontrar el elemento de la matriz que contiene el valor '5'.

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

En esta situación, no sé qué de desplazamiento para agregar al puntero para encontrarlo, así que tengo que empezar en 0, y el trabajo de mi camino hasta que la encuentre. Esto significa que tengo que realizar 6 cheques.

Debido a esto, la búsqueda de un valor en una matriz se considera O(N). El costo de la búsqueda aumenta a medida que la matriz se hace más grande.

Recuerde, arriba de donde me dijo que a veces con un no secuencial de la estructura de datos puede tener sus ventajas? Búsqueda de datos es una de estas ventajas y uno de los mejores ejemplos es el Árbol Binario.

Un Árbol Binario es una estructura de datos similar a una lista enlazada, sin embargo en lugar de vincular a un único nodo, cada nodo puede vincular a dos nodos hijos.

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

 Assume that each connector is really a Pointer

Cuando se insertan datos en un árbol binario, utiliza varias reglas para decidir donde colocar el nuevo nodo. El concepto básico es que si el nuevo valor es mayor que el de los padres, se inserta a la izquierda, si es inferior, se inserta a la derecha.

Esto significa que los valores en un árbol binario podría tener este aspecto:

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

Al buscar en un árbol binario para el valor de los 75, sólo tenemos que visitar 3 nodos ( O(log N)), porque de esta estructura:

  • Es de 75 a menos de 100? Mirar a la Derecha del Nodo
  • Es de 75 años mayor que 50? Mira a la Izquierda del Nodo
  • No es el 75!

Aunque hay 5 nodos en nuestro árbol, no necesitamos mirar a los dos restantes, porque sabíamos que ellos (y sus hijos), no podría contener el valor que estamos buscando. Esto nos da un tiempo de búsqueda, que en el peor de los casos significa que tenemos que visitar cada nodo, pero en el mejor de los casos sólo tenemos que visitar una pequeña porción de los nodos.

Que es donde las matrices de recibir una paliza, que proporcionan una constante O(N) tiempo de búsqueda, a pesar de O(1) tiempo de acceso.

Este es un muy alto nivel de descripción de estructuras de datos en memoria, saltando sobre un montón de detalles, pero espero que ilustra una matriz de fortaleza y debilidad en comparación con otras estructuras de datos.

73voto

Jason Puntos 125291

Para acceso aleatorio o (1), que no pueden ser derrotados.

31voto

Chris Puntos 14136

Quizás no eres consciente de ello, pero la mayoría de las clases de colección de utilizar las matrices como su base en el mecanismo de almacenamiento de...

Un ejemplo en .NET es el ArrayList:

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;

Ahora, nos fijamos en una de las típicas escribió clase de colección, StringCollection:

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

Lo mismo ocurre para una Lista genérica:

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;

Tengo la impresión de su pregunta que creo que todas estas nuevas formas de almacenamiento de colecciones de elementos han sustituido a la matriz, pero en realidad, ellos no tienen. Complementan mucho.

21voto

Jason Jackson Puntos 11563

No todos los programas de la misma cosa o ejecutar en el mismo hardware.

Esta suele ser la respuesta de por qué diferentes características del lenguaje de existir. Los arreglos son de un núcleo de ciencias de la computación concepto. Colocación de matrices con listas/matrices/vectores/lo avanzado de la estructura de datos afectaría gravemente el rendimiento, y ser francamente imposible en un número de sistemas. Hay cualquier cantidad de casos donde el uso de uno de estos "avanzado" de recogida de datos, los objetos deben ser usados por el programa en cuestión.

En los negocios de programación (que la mayoría de nosotros lo hacemos), podemos apuntar que el hardware es relativamente poderoso. El uso de una Lista en C# o Vector en Java es la elección correcta para hacer en estas situaciones debido a que estas estructuras permiten que el desarrollador para cumplir las metas más rápido, lo cual permite que este tipo de software sea más destacados.

Cuando la escritura de software embebido o un sistema operativo, una matriz puede ser a menudo la mejor opción. Mientras que una matriz tiene menos funcionalidad, ocupa menos memoria RAM, y el compilador puede optimizar el código de manera más eficiente para las búsquedas en las matrices.

Estoy seguro de que me estoy dejando una serie de beneficios para estos casos, pero espero que usted consigue el punto.

19voto

goralı Puntos 1

Tal vez sólo porque ellos son la primera cosa que viene a la mente cuando queremos almacenar una "colección" de los artículos en un "set".

Tal vez son la estructura más antigua en los lenguajes de programación para almacenar una colección de datos, en una forma ordenada manera (es decir 1-1 correspondencia con los enteros positivos).

Todas las demás estructuras son algunas de las formas y los desvíos de las matrices.

Si tu pregunta es por qué las matrices son la primera cosa en mente cuando queremos almacenar una colección? La pregunta puede cambiar a "¿por qué los seres humanos cuentan?", "¿Cómo clasificamos?", "Hay una definición de un conjunto?", etc.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by: