Una descripción general de cómo funcionan las matrices

En informática, existe el concepto de una estructura de datos lineal , lo que significa que los datos están estructurados de forma lineal en la que el orden importa . Hay matrices y listas enlazadas , pero hoy hablaré principalmente sobre matrices y un poco sobre listas enlazadas.

La mayoría de los lenguajes orientados a objetos vienen con matrices , mientras que la mayoría f idiomas unctional vienen con listas enlazadas (ver por qué en otro de mis artículos, que se menciona en la parte inferior de este artículo).

Hay una buena razón para esta diferenciación en la que nos sumergiremos más adelante. Por ahora, echemos un vistazo rápido a las diferencias entre las dos estructuras de datos. Para hacer esto, tendremos que hacer un viaje al pasado.

Rebobinar el tiempo

Los objetos y funciones y todo lo que sabemos sobre las computadoras, se almacenan fundamentalmente en bits y bytes en la computadora.

En lenguajes como Java y C, debe declarar explícitamente el tamaño de una matriz de antemano.

Espera, pero Ruby no hace eso.

En Ruby, usamos Arraypara nuestras estructuras de datos lineales. Podemos agregar cosas aparentemente infinitas en una matriz Ruby y no importaría en lo que a nosotros respecta.

Eso es genial, ¿no? Eso significa que las matrices son infinitamente grandes, ¿verdad? ¿Y que Ruby es el lenguaje superior? ¡Suerte con nosotros!

Pero no tan rápido. * hace estallar tu burbuja *

No hay matrices de tamaño infinito; lo que ves en Ruby es lo que llamamos Dynamic Array , y tiene un costo.

Para comprender qué son las matrices dinámicas, primero echemos un vistazo a cómo se representan las matrices en la memoria. Dado que MRI Ruby (Matz 'Ruby Interpreter) se compila en código C, veremos cómo se representan las matrices en C.

C-ing es creer

Nos sumergiremos en un poco de código C para ayudarnos a C un poco mejor… :)

En lenguajes de nivel inferior como C, usted mismo debe lidiar con los punteros y la asignación de memoria. Incluso si no ha tratado con C antes (d isclaimer - yo tampoco ), puede haber C-een uno de los ejemplos más (in) famosos a continuación:

Analicemos este fragmento de código:

  • malloc no tiene ningún significado mágico detrás de él, literalmente significa memory allocation
  • malloc devuelve un puntero
  • malloc toma un argumento, que es el tamaño de la memoria que desea que el programa le asigne.
  • 100 * sizeof(int) le dice al programa que queremos almacenar 100 enteros, así que asígnenos 100 * el tamaño de lo que ocuparía cada entero.
  • ptr/ pointer almacena la referencia a la dirección de memoria.

¡Timmy guarda equipaje!

Si el ejemplo anterior realmente no tiene sentido, pruebe esta analogía. Piense en la asignación de memoria como un conserje de equipaje. Funciona así:

  • Timmy va al mostrador, le dice al conserje que tiene 2 piezas de equipaje, aproximadamente así de grandes, y que le gustaría guardarlas en el almacén.
  • El conserje echa un vistazo al almacén y dice: "Sí, tenemos algo de espacio en el B4área designada y asignaremos ese espacio para guardar su equipaje".
  • Le entregan a Timmy una tarjeta de recogida con el área designada en ella, B4en nuestro caso.
  • Timmy está feliz, anda haciendo lo que sea, y cuando quiere recoger su equipaje, vuelve al mostrador y les muestra su tarjeta de recogida . “ ¿Has visto mi equipaje? "

En nuestro ejemplo, el equipaje de Timmy son los datos , la tarjeta de recogida es el puntero (indica dónde se almacena el bolso de Timmy). El lugar donde el conserje guarda el equipaje de Timmy es el bloque de memoria y el mostrador es el programa .

Al mostrar el contador ( el programa ) la tarjeta de Timmy ( puntero / dirección de memoria ), Timmy puede recuperar su equipaje ( datos ). ¿Prima? Como saben exactamente dónde está guardado el bolso de Timmy B4, ¡esto significa que pueden recuperar todo el equipaje de Timmy con relativa rapidez!

Además, ¿alguna vez se preguntó por qué accede a elementos en una matriz con índice , como tal?

Esto se debe a que la matriz contiene las referencias al bloque de memoria y el índice le indica el desplazamiento .

Una analogía de eso es que si les pido que busquen a Timmy en una cola de 20 personas, lógicamente tendrían que preguntarles a cada uno de ellos si es Timmy. Pero, si te digo que Timmy es el sexto ( índice ) de la primera persona ( tu puntero original ), sabes exactamente dónde buscar.

La recuperación de elementos en matrices es rápida exactamente por esto: el programa no tiene que revisar los 100 elementos para encontrar lo que está buscando. Si tiene el índice, solo tiene que agregar el desplazamiento a la dirección de memoria original, ¡y el droide que estaba buscando estará allí!

Entonces, ¿qué son las matrices dinámicas?

Así que les he contado un poco sobre cómo se representan las matrices en la memoria, pero ahora es el momento de hablar sobre algunas desventajas.

¿Recuerda cómo tiene que declarar explícitamente la cantidad de memoria que necesita? Esto significa que la matriz encontrará un lugar que se ajustará exactamente a su tamaño. No hay garantía de que pueda caber más de lo que tiene (porque el bloque de memoria justo detrás podría estar ocupado).

Volviendo a nuestra analogía con el equipaje: piense en ello como si Timmy tuviera que guardar 2 piezas de equipaje y B4pudiera almacenar exactamente 2 piezas de equipaje, así que se lo asignan a Timmy. Ahora, por alguna razón, Timmy quiere guardar otra pieza de equipaje, pero B4no puede guardar 3 piezas, solo 2, entonces, ¿qué hacen?

Ellos toman todo su equipaje existente, lo mueven a un nuevo lugar en el que caben más de 3 piezas y luego las almacenan todas juntas.

Esa es una operación costosa, ¡pero así es exactamente como funciona la memoria!

En Ruby, que no tiene que declarar un tamaño específico antes de la mano , pero eso es porque Rubí lo hace por ti automágicamente a través de matrices dinámicas.

Lo que hace una matriz dinámica es que si la matriz se acerca a su capacidad total, declarará automáticamente una matriz nueva y más grande y moverá todos los elementos existentes a ella, y la matriz anterior se recolectará como basura. ¿Cuánto más grande? El factor de crecimiento suele ser 2; el doble del tamaño de la matriz actual.

De hecho, no confíe en mi palabra .

Ruby tiene un módulo ObjectSpace que nos permite interactuar con objetos actuales que viven en la memoria. Podemos usar este módulo para echar un vistazo al uso de memoria de nuestra matriz dinámica: ¡suena exactamente como lo que queremos!

He escrito un pequeño script Ruby que calcula el factor de crecimiento de la matriz dinámica. Siéntase libre de echarle un vistazo aquí, y si lo hace, puede ver que las matrices Ruby tienen un factor de crecimiento de 1.5x (es decir, hacen una matriz que es un 50% más grande en cada copia).

Sé qué son las matrices, qué son las listas vinculadas?

Tenga en cuenta que aunque las matrices y las listas vinculadas se consideran estructuras de datos lineales, tienen una gran diferencia entre ellas.

Los elementos de una matriz se almacenan literalmente uno al lado del otro en la memoria (por lo que podemos tener un índice para búsquedas rápidas). Pero los nodos en las listas vinculadas no tienen tal restricción (razón por la cual no hay búsqueda de índice para las listas vinculadas): todos y cada uno de los elementos se pueden almacenar en cualquier lugar del bloque de memoria.

Es casi como si Timmy estuviera tratando de guardar 5 maletas, y el conserje no tiene espacio y decide dejarlas por todos lados. ¿Suena desorganizado?

Además, si están almacenados en diferentes lugares, ¿cómo saber qué bolsos son de Timmy? Sugerencia: ¡solo mantén un registro del siguiente nodo / bolsa! En nuestro caso, el conserje los guarda por separado pero con una etiqueta en cada uno de ellos que apunta a la siguiente bolsa.

Un nodo en una lista vinculada consta de dos partes: la parte de datos y un puntero al siguiente nodo. Así es como pueden mantener la linearparte: todavía tienen el concepto de orden, ¡simplemente no tienen que almacenarse en orden literalmente!

node = [ data | pointer ]

Por ejemplo, dado el siguiente ejemplo almacenado en la memoria:

[C | D] [A | B] [B | C] [D | nil]

Parece que estos bits están fuera de servicio, pero si le hubiera dicho que el primer elemento lo es A, podría decirme el orden exacto de la lista:

list = [A -> B -> C ->D -> cero]

Hay muchas cosas interesantes que puedes hacer con listas enlazadas en las que no voy a profundizar aquí (también muchas cosas sobre Big O de las que no hablé). Pero ya hay un montón de buenos artículos sobre estructuras de datos. Si lo hiciste aquí, te sugiero que leas la entrada de blog de Ali aquí.

gracias, siguiente: una introducción a las listas vinculadas

En esta publicación, vamos a hablar sobre la estructura de datos de la lista enlazada en el lenguaje de "gracias, siguiente" por ... dev.to

También puede leer más sobre List / Contras en Wiki aquí.

Nota final

Inicialmente escribí este artículo para un tema ligeramente diferente: [Elixir | ¿Por qué las listas vinculadas?], Pero descubrí que me llevó demasiado tiempo explicar cómo funcionan las matrices antes de poder explicar y explorar por qué Elixir usa listas vinculadas. Así que los he separado en dos artículos.

En ese artículo, hablo de por qué los lenguajes funcionales usan listas enlazadas como su estructura de datos lineal. ¡Compruébalo!

[Elixir | ¿Por qué las listas vinculadas? ]

Siempre he pensado que las estructuras de datos son geniales, pero ¿sabes qué es mejor? ¡Verlos en la naturaleza! Mientras pasa por ... dev.to

Fuentes

  1. //medium.com/@rebo_dood/ruby-has-a-memory-problem-part-1-7887bbacc579 - Aquí es donde descubrí ObjectSpacemétodos adicionales al requerirlo

Publicado originalmente en dev.to