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

tipos de datos estructurados (4)

Como estaba programando, 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" añadidas en los lenguajes de programación habían mejorado sobre esto y por eso las reemplacé. Ahora veo que no se los reemplaza sino que se les da nueva vida, por así decirlo.

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

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

Es hora de regresar a tiempo para una lección. Si bien no pensamos demasiado en estas cosas en nuestros sofisticados lenguajes administrados de hoy, están construidos sobre la misma base, así que veamos cómo se maneja 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 memoria, contiene la dirección de memoria. Piensa en un bloque de memoria como un buzón. El puntero sería la dirección de ese buzón.

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

MyArray [5] ^ ^ Pointer Offset

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

Por ejemplo, digamos que tenemos una matriz con 6 números (6,4,2,3,1,5) en ella, 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 MyArray aquí) 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] tomarí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 sean) 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), así que en su lugar tengo que comenzar en P1, y seguir cada puntero al 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 caro llegar a P1000 en comparación con llegar a P4.

Las estructuras de datos de nivel superior, como las tablas hash, las pilas y las colas, todas pueden usar una matriz (o varias 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 requiera un recorrido lineal para buscar un valor en lugar de simplemente usar una matriz, pero tienen sus usos.

Tome 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 añadir al puntero para encontrarlo, así que tengo que comenzar en 0 y seguir subiendo hasta encontrarlo. Esto significa que tengo que realizar 6 controles.

Debido a esto, buscar un valor en una matriz se considera O (N). El costo de 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 vincular a un solo nodo, cada nodo puede vincular a dos nodos secundarios.

Cuando los datos se insertan en un árbol binario, usan 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 menor, 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 un árbol binario por el valor de 75, solo necesitamos visitar 3 nodos (O (log N)) debido a esta estructura:

¿Tiene 75 menos de 100? Mira el nodo derecho
¿75 es mayor que 50? Mira el nodo izquierdo
¡Son los 75!

Aunque hay 5 nodos en nuestro árbol, no necesitamos ver los otros dos, porque sabíamos que ellos (y sus hijos) posiblemente no podrí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 debemos 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 las matrices son superadas, proporcionan un tiempo de búsqueda O (N) constante, a pesar del tiempo de acceso O (1).

Esta es una descripción general de alto nivel increíble 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 se puede superar.

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 capitalizan:

En las tablas de búsqueda de su aplicación (una matriz estática para acceder a ciertas respuestas categóricas)
Memoization (ya se han calculado los resultados de la función compleja, para que no se vuelva a calcular el valor de la función, digamos log x)
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 )

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

Esta suele ser la respuesta por la cual existen varias características del lenguaje. Las matrices son un concepto central de ciencias de la computación. Reemplazar las matrices con listas / matrices / vectores / cualquier estructura de datos avanzada tendría un impacto severo en el rendimiento y sería francamente impracticable en una serie de sistemas. Hay 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 comercial (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 en estas situaciones porque estas estructuras le permiten al desarrollador alcanzar los objetivos más rápido, lo que a su vez permite que este tipo de software sea más destacado.

Cuando se escribe software embebido o un sistema operativo, una matriz puede ser la mejor opción. Mientras que 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 el punto.