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

Mientras programaba, no he visto una instancia en la que una matriz sea mejor para almacenar información que otra forma de la misma. De hecho, me imaginé que las "características" agregadas en los lenguajes de programación habían mejorado sobre esto y por eso las reemplazó. Ahora veo que no son reemplazados sino que se les da nueva vida, por así decirlo.

Entonces, básicamente, ¿cuál es el punto de usar matrices?

Esto no es tanto por qué usamos matrices desde el punto de vista de la computadora, sino más bien por qué usaríamos matrices desde un punto de vista de programación (una sutil diferencia). Lo que la computadora hace con la matriz no era el punto de la pregunta.

Es hora de retroceder en el tiempo para una lección. Si bien hoy en día no pensamos mucho en estas cosas en nuestros sofisticados lenguajes administrados, se basan en la misma base, así que veamos cómo se administra la memoria en C.

Antes de sumergirme, una explicación rápida de lo que significa el término " puntero ". Un puntero es simplemente una variable que "apunta" a una ubicación en la memoria. No contiene el valor real en esta área de la memoria, contiene la dirección de la memoria. Piense en un bloque de memoria como un buzón. El puntero sería la dirección de ese buzón.

En C, una matriz es simplemente un puntero con un desplazamiento, el desplazamiento especifica qué tan lejos en la memoria buscar. Esto proporciona tiempo de acceso O (1) .

  MyArray   [5]
     ^       ^
  Pointer  Offset

Todas las demás estructuras de datos se basan en esto o no usan memoria adyacente para el almacenamiento, lo que resulta en un tiempo de búsqueda de acceso aleatorio deficiente (aunque existen otros beneficios al no usar memoria secuencial).

Por ejemplo, supongamos que tenemos una matriz 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 está uno al lado del otro en la memoria. La matriz de CA (llamada MyArrayaquí) es simplemente un puntero al primer elemento:

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

Si quisiéramos buscar MyArray[4], internamente se accedería así:

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

Debido a que podemos acceder directamente a cualquier elemento de la matriz agregando el desplazamiento al puntero, podemos buscar cualquier elemento en la misma cantidad de tiempo, independientemente del tamaño de la matriz. Esto significa que obtener MyArray[1000]llevaría la misma cantidad de tiempo que obtener MyArray[5].

Una estructura de datos alternativa es una lista vinculada. Esta es una lista lineal de punteros, cada uno apuntando al siguiente nodo

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

P(X) stands for Pointer to next node.

Tenga en cuenta que hice cada "nodo" en su propio bloque. Esto se debe a que no se garantiza que sean (y probablemente no lo serán) adyacentes en la memoria.

Si quiero acceder a P3, no puedo acceder directamente a él, porque no sé dónde está en la memoria. Todo lo que sé es dónde está la raíz (P1), por lo que debo comenzar en P1 y seguir cada puntero hasta el nodo deseado.

Este es un tiempo de búsqueda O (N) (el costo de búsqueda aumenta a medida que se agrega cada elemento). Es mucho más costoso llegar a P1000 en comparación con llegar a P4.

Las estructuras de datos de nivel superior, como tablas hash, pilas y colas, pueden usar una matriz (o múltiples matrices) internamente, mientras que las Listas vinculadas y los Árboles binarios generalmente usan nodos y punteros.

Quizás se pregunte por qué alguien usaría una estructura de datos que requiere un recorrido lineal para buscar un valor en lugar de solo usar una matriz, pero tienen sus usos.

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

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

En esta situación, no sé qué desplazamiento agregar al puntero para encontrarlo, por lo que tengo que comenzar en 0 y avanzar hasta encontrarlo. Esto significa que tengo que realizar 6 verificaciones.

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.

¿Recuerdas arriba donde dije que a veces usar una estructura de datos no secuencial puede tener ventajas? La 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 vinculada, sin embargo, en lugar de vincularse a un solo nodo, cada nodo puede vincularse a dos nodos secundarios.

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

 Assume that each connector is really a Pointer

Cuando los datos se insertan en un árbol binario, utiliza varias reglas para decidir dónde colocar el nuevo nodo. El concepto básico es que si el nuevo valor es mayor que los padres, lo inserta a la izquierda, si es más bajo, lo inserta a la derecha.

Esto significa que los valores en un árbol binario podrían verse así:

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

Al buscar en un árbol binario el valor de 75, solo necesitamos visitar 3 nodos (O (log N)) debido a esta estructura:

• ¿75 es menos de 100? Mire el nodo derecho
• ¿75 es mayor que 50? Mire el nodo izquierdo
• Ahí está el 75!

Aunque hay 5 nodos en nuestro árbol, no tuvimos que mirar los dos restantes, porque sabíamos que ellos (y sus hijos) no podían contener el valor que estábamos 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 solo tenemos que visitar una pequeña porción de los nodos.

Ahí es donde los arreglos son superados, proporcionan un tiempo de búsqueda O (N) lineal, a pesar del tiempo de acceso O (1).

Esta es una descripción increíblemente de alto nivel sobre las estructuras de datos en la memoria, omitiendo muchos detalles, pero con suerte ilustra la fortaleza y debilidad de una matriz en comparación con otras estructuras de datos.

Para O (1) acceso aleatorio, que no puede ser vencido.

No todos los programas hacen lo mismo o se ejecutan en el mismo hardware.

Esta suele ser la respuesta de por qué existen varias características del lenguaje. Las matrices son un concepto básico de informática. Reemplazar las matrices con listas / matrices / vectores / cualquier estructura de datos avanzada afectaría severamente el rendimiento y sería francamente impracticable en varios sistemas. Existen varios casos en los que se debe utilizar uno de estos objetos de recopilación de datos "avanzados" debido al programa en cuestión.

En la programación empresarial (que la mayoría de nosotros hacemos), podemos apuntar al hardware que es relativamente poderoso. Usar una Lista en C # o Vector en Java es la elección correcta para hacer en estas situaciones porque estas estructuras permiten al desarrollador lograr los objetivos más rápido, lo que a su vez permite que este tipo de software sea más destacado.

Al escribir software embebido o un sistema operativo, una matriz a menudo puede ser la mejor opción. Si bien una matriz ofrece menos funcionalidad, ocupa menos RAM y el compilador puede optimizar el código de manera más eficiente para búsquedas en matrices.

Estoy seguro de que estoy dejando de lado algunos de los beneficios para estos casos, pero espero que entiendan.

Una forma de ver las ventajas de las matrices es ver dónde se requiere la capacidad de acceso O (1) de las matrices y, por lo tanto, se capitaliza:

1. En las tablas de búsqueda de su aplicación (una matriz estática para acceder a ciertas respuestas categóricas)

2. Memoization (resultados de funciones complejas ya calculados, para que no vuelva a calcular el valor de la función, digamos log x)

3. Aplicaciones de visión por computadora de alta velocidad que requieren procesamiento de imágenes ( https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing )