Introducción

A medida que la lógica empresarial se mueve de atrás hacia adelante cada vez más, la experiencia en Ingeniería Frontend se vuelve cada vez más crucial. Como ingenieros frontend , dependemos de bibliotecas de visualización como React para ser productivos. Ver bibliotecas a su vez depende de bibliotecas estatales como Redux para administrar los datos. Juntos, React y Redux se suscriben al paradigma de programación reactiva en el que las actualizaciones de la interfaz de usuario reaccionan a los cambios de datos. Cada vez más, los backends actúan simplemente como servidores API, proporcionando puntos finales solo para recuperar y actualizar los datos. En efecto, el backend simplemente "reenvía" la base de datosal frontend, esperando que el ingeniero de frontend maneje toda la lógica del controlador. La creciente popularidad de los microservicios y GraphQL atestigua esta tendencia creciente.

Ahora, además de tener una comprensión estética de HTML y CSS, se espera que los ingenieros de frontend también dominen JavaScript. A medida que los almacenes de datos del cliente se convierten en "réplicas" de las bases de datos del servidor, el conocimiento profundo de las estructuras de datos idiomáticas se vuelve fundamental. De hecho, el nivel de experiencia de un ingeniero se puede inferir de su capacidad para distinguir cuándo y por qué utilizar una estructura de datos en particular.

Los malos programadores se preocupan por el código. Los buenos programadores se preocupan por las estructuras de datos y sus relaciones.

- Linus Torvalds, creador de Linux y Git

En un nivel alto, existen básicamente tres tipos de estructuras de datos. Las pilas y las colas son estructuras en forma de matriz que difieren solo en cómo se insertan y eliminan los elementos. Las listas enlazadas , árboles , y los gráficos son estructuras con nodos que mantienen referencias a otros nodos. Las tablas hash dependen de las funciones hash para guardar y localizar datos.

En términos de complejidad, Stacksy Queuesson los más simples y pueden construirse a partir Linked Lists. Treesy Graphsson los más complejos porque amplían el concepto de lista enlazada. Hash TablesNecesita utilizar estas estructuras de datos para funcionar de manera confiable. En términos de eficiencia, las Listas Vinculadas son más óptimas para el registro y almacenamiento de datos, mientras que las Tablas Hash son las más eficaces para buscar y recuperar datos.

Para explicar por qué e ilustrar cuándo , este artículo se ajustará al orden de estas dependencias. ¡Vamos a empezar!

Apilar

Podría decirse que el más importante Stacken JavaScript es la pila de llamadas donde empujamos en el alcance de un functioncada vez que lo ejecutamos. Programáticamente, es solo una arraycon dos operaciones basadas en principios: pushy pop. Push agrega elementos a la parte superior de la matriz, mientras que Pop los elimina de la misma ubicación. En otras palabras, las pilas siguen el protocolo "Último en entrar, primero en salir" (LIFO).

A continuación se muestra un ejemplo de Stackcódigo en. Observe que podemos invertir el orden de la pila: la parte inferior se convierte en la parte superior y la parte superior se convierte en la parte inferior. Como tal, podemos usar los métodos unshifty de la matriz shiften lugar de pushy pop, respectivamente.

A medida que aumenta el número de elementos, push/ se popvuelve cada vez más eficaz que unshift/ shiftporque cada elemento debe volver a indexarse ​​en el último, pero no en el primero.

Cola

JavaScript es un lenguaje de programación impulsado por eventos que permite admitir operaciones sin bloqueo . Internamente, el navegador administra solo un hilo para ejecutar todo el código JavaScript, usando la cola de eventos para poner en colalisteners y el bucle de eventos para escuchar el registrado events. Para admitir la asincronicidad en un entorno de un solo subproceso (para ahorrar recursos de CPU y mejorar la experiencia web), listener functions elimine la cola y ejecute solo cuando la pila de llamadas esté vacía. Promisesdependen de esta arquitectura dirigida por eventos para permitir una ejecución de "estilo síncrono" de código asincrónico que no bloquea otras operaciones.

Programáticamente, Queuesson solo matrices con dos operaciones principales: unshifty pop. Unshift pone en cola los elementos al final de la matriz, mientras que Pop los retira de la cola desde el principio de la matriz. En otras palabras, las colas siguen el protocolo "Primero en entrar, primero en salir" (FIFO). Si se invierte la dirección, podemos reemplazar unshifty popcon pushy shift, respectivamente.

Un ejemplo de Queuecódigo en:

Lista enlazada

Al igual que las matrices, Linked Listsalmacena elementos de datos en orden secuencial . En lugar de mantener índices, las listas enlazadas contienen punteros a otros elementos. El primer nodo se llama cabeza mientras que el último nodo se llama cola . En una lista enlazada individualmente , cada nodo tiene solo un puntero al siguiente nodo. Aquí, la cabeza es donde comenzamos nuestra caminata por el resto de la lista. En una lista doblemente enlazada , también se mantiene un puntero al nodo anterior . Por lo tanto, también podemos comenzar desde la cola y caminar “hacia atrás” hacia la cabeza.

Las listas vinculadas tienen inserciones y eliminaciones de tiempo constante porque simplemente podemos cambiar los punteros. Para realizar las mismas operaciones en matrices, se requiere un tiempo lineal porque los elementos siguientes deben cambiarse. Además, las listas vinculadas pueden crecer siempre que haya espacio. Sin embargo, incluso los arreglos "dinámicos" que cambian de tamaño automáticamente pueden resultar inesperadamente costosos. Por supuesto, siempre hay una compensación. Para buscar o editar un elemento en una lista vinculada, es posible que tengamos que recorrer toda la longitud, lo que equivale a un tiempo lineal. Sin embargo, con los índices de matriz, estas operaciones son triviales.

Al igual que las matrices, las listas enlazadas pueden funcionar como pilas . Es tan simple como hacer que la cabeza sea el único lugar para la inserción y extracción. Las listas vinculadas también pueden funcionar como colas . Esto se puede lograr con una lista doblemente enlazada, donde la inserción ocurre en la cola y la remoción ocurre en la cabeza, o viceversa. Para un gran número de elementos, esta forma de implementar las colas es más eficaz que el uso de matrices porque las operaciones shifty unshiftal comienzo de las matrices requieren un tiempo lineal para volver a indexar cada elemento posterior.

Las listas vinculadas son útiles tanto en el cliente como en el servidor. En el cliente, las bibliotecas de gestión de estado como Redux estructuran su lógica de middleware en forma de lista enlazada. Cuando se envían acciones , se canalizan de un middleware al siguiente hasta que se visitan todos antes de llegar a los reductores . En el servidor, los marcos web como Express también estructuran su lógica de middleware de manera similar. Cuando se recibe una solicitud, se envía de un middleware al siguiente hasta que se emite una respuesta .

Un ejemplo de Doubly-Linked Listcódigo en:

Árbol

A Treees como una lista enlazada , excepto que mantiene referencias a muchos nodos secundarios en una estructura jerárquica . En otras palabras, cada nodo no puede tener más de un padre. El Modelo de objetos de documento (DOM) es una estructura de este tipo, con un htmlnodo raíz que se ramifica en los nodos heady body, que se subdividen en todas las etiquetas html familiares . Bajo el capó, la herencia y la composición de prototipos con componentes React también producen estructuras de árbol. Por supuesto, como representación en memoria del DOM, el DOM virtual de React también es una estructura de árbol.

El árbol de búsqueda binaria es especial porque cada nodo no puede tener más de dos hijos . El hijo de la izquierda debe tener un valor menor o igual que su padre, mientras que el hijo de la derecha debe tener un valor mayor . Estructurado y equilibrado de esta manera, podemos buscar cualquier valor en tiempo logarítmico porque podemos ignorar la mitad de la ramificación con cada iteración. La inserción y eliminación también pueden ocurrir en tiempo logarítmico. Además, el valor más pequeño y más grande se puede encontrar fácilmente en la hoja más a la izquierda y más a la derecha , respectivamente.

El recorrido a través del árbol puede ocurrir en un procedimiento vertical u horizontal . En Depth-First Traversal (DFT) en la dirección vertical, un algoritmo recursivo es más elegante que uno iterativo. Los nodos se pueden recorrer en preorden , en orden o posorden . Si necesitamos explorar las raíces antes de inspeccionar las hojas, deberíamos optar por reservar . Pero, si necesitamos explorar las hojas antes que las raíces, deberíamos elegir post-order . Como su nombre lo indica, in-order nos permite atravesar los nodos en orden secuencial . Esta propiedad hace que los árboles de búsqueda binaria sean óptimos para la clasificación .

En Breadth-First Traversal (BFT) en la dirección horizontal, un enfoque iterativo es más elegante que uno recursivo. Esto requiere el uso de a queuepara rastrear todos los nodos secundarios con cada iteración. Sin embargo, es posible que la memoria necesaria para tal cola no sea trivial. Si la forma de un árbol es más ancha que profunda, BFT es una mejor opción que DFT. Además, la ruta que toma BFT entre dos nodos es la más corta posible.

Un ejemplo de Binary Search Treecódigo en:

Grafico

Si un árbol es libre de tener más de un padre, se convierte en un Graph. Los bordes que conectan los nodos en un gráfico pueden estar dirigidos o no dirigidos, ponderados o no ponderados . Los bordes que tienen tanto dirección como peso son análogos a los vectores .

Varias herencias en forma de Mixins y objetos de datos que tienen relaciones de varios a varios producen estructuras de gráficos. Una red social e Internet en sí también son gráficos. El gráfico más complicado de la naturaleza es nuestro cerebro humano, que las redes neuronales intentan replicar para dar superinteligencia a las máquinas .

Un ejemplo de Graphcódigo en:

TK

Tabla de picadillo

Una tabla hash es una estructura similar a un diccionario que empareja claves con valores . La ubicación en la memoria de cada par está determinada por a hash function, que acepta una clave y devuelve la dirección donde se debe insertar y recuperar el par. Pueden producirse colisiones si dos o más claves se convierten en la misma dirección. Por robustez, gettersy settersdebe anticiparse a estos eventos para asegurar que todos los datos se pueden recuperar y no hay datos se sobrescribe. Por lo general, linked listsofrece la solución más sencilla. Tener mesas muy grandes también ayuda.

Si sabemos que nuestras direcciones estarán en secuencias enteras, simplemente podemos usarlas Arrayspara almacenar nuestros pares clave-valor. Para asignaciones de direcciones más complejas, podemos usar Mapso Objects. Las tablas hash tienen inserción y búsqueda de tiempo constante en promedio. Debido a las colisiones y el cambio de tamaño, este costo insignificante podría crecer hasta convertirse en un tiempo lineal. En la práctica, sin embargo, podemos asumir que las funciones hash son lo suficientemente inteligentes como para que las colisiones y el cambio de tamaño sean raras y baratas. Si las claves representan direcciones y, por lo tanto, no se necesita hash, una simple object literalpuede ser suficiente. Por supuesto, siempre hay una compensación. La simple correspondencia entre claves y valores, y la simple asociatividad entre claves y direcciones, sacrifican las relaciones entre los datos. Por lo tanto, las tablas hash no son óptimas para almacenar datos.

Si una decisión de compensación favorece la recuperación sobre el almacenamiento, ninguna otra estructura de datos puede igualar la velocidad de las tablas hash para la búsqueda , inserción y eliminación . Por tanto, no es de extrañar que se utilice en todas partes . Desde la base de datos hasta el servidor y el cliente, las tablas hash y, en particular, las funciones hash , son cruciales para el rendimiento y la seguridad de las aplicaciones de software. La velocidad de las consultas de la base de datos depende en gran medida de mantener tablas de índices que apuntan a registros en orden ordenado . De esta manera, las búsquedas binarias se pueden realizar en tiempo logarítmico , una gran ganancia de rendimiento, especialmente para Big Data .

Tanto en el cliente como en el servidor, muchas bibliotecas populares utilizan la memorización para maximizar el rendimiento. Al mantener un registro de las entradas y salidas en una tabla hash, las funciones se ejecutan solo una vez para las mismas entradas. La popular biblioteca Reselect utiliza esta estrategia de almacenamiento en caché para optimizar mapStateToPropsfunciones en aplicaciones habilitadas para Redux . De hecho, bajo el capó, el motor de JavaScript también utiliza tablas hash llamadas montones para almacenar todos los variablesy primitivescreamos. Se accede a ellos desde punteros en la pila de llamadas .

La propia Internet también se basa en algoritmos hash para funcionar de forma segura. La estructura de Internet es tal que cualquier computadora puede comunicarse con cualquier otra computadora a través de una red de dispositivos interconectados. Siempre que un dispositivo inicia sesión en Internet, también se convierte en un enrutador a través del cual pueden viajar los flujos de datos. Sin embargo, es un arma de doble filo. Una arquitectura descentralizada significa que cualquier dispositivo en la red puede escuchar y manipular los paquetes de datos que ayuda a transmitir. Las funciones hash como MD5 y SHA256 desempeñan un papel fundamental en la prevención de estos ataques de intermediario . El comercio electrónico a través de HTTPS es seguro solo porque se utilizan estas funciones hash.

Inspiradas en Internet, las tecnologías blockchain buscan abrir la estructura de la web a nivel de protocolo . Al usar funciones hash para crear huellas dactilares inmutables para cada bloque de datos , esencialmente toda la base de datos puede existir abiertamente en la web para que cualquiera la vea y contribuya. Estructuralmente, las cadenas de bloques son solo listas unidas de árboles binarios de hashes criptográficos. El hash es tan críptico que cualquier persona puede crear y actualizar abiertamente una base de datos de transacciones financieras . La increíble implicación es el asombroso poder de crear dinero en sí mismo. Lo que antes solo era posible para los gobiernos y los bancos centrales, ¡ahora cualquiera puede crear su propia moneda de forma segura ! Esta es la información clave realizada por el fundador de Ethereum y el fundador seudónimo de Bitcoin .

A medida que más y más bases de datos salgan a la luz, la necesidad de ingenieros frontend que puedan abstraer todas las complejidades criptográficas de bajo nivel también se agravará. En este futuro, el principal diferenciador será la experiencia del usuario .

Un ejemplo de Hash Tablecódigo en:

Para ejercicios de algoritmos que utilizan estas estructuras de datos y más, consulte: Algoritmos en JavaScript: 40 problemas, soluciones y explicaciones

Conclusión

A medida que la lógica se mueve cada vez más del servidor al cliente, la capa de datos en la interfaz se vuelve primordial. La gestión adecuada de esta capa implica el dominio de las estructuras de datos sobre las que descansa la lógica. Ninguna estructura de datos es perfecta para cada situación porque optimizar para una propiedad siempre equivale a perder otra. Algunas estructuras son más eficientes para almacenar datos, mientras que otras son más eficaces para buscar entre ellas. Por lo general, uno se sacrifica por el otro. En un extremo, las listas enlazadas son óptimas para el almacenamiento y se pueden convertir en pilas y colas ( tiempo lineal ). Por otro lado, ninguna otra estructura puede igualar la velocidad de búsqueda de las tablas hash ( tiempo constante ). Las estructuras de los árboles se encuentran en algún lugar intermedio ( tiempo logarítmico ), y solo un gráfico puede representar la estructura más compleja de la naturaleza: el cerebro humano ( tiempo polinomial ). Tener el conjunto de habilidades para distinguir cuándo y articular por qué es un sello distintivo de un ingeniero estrella de rock.

Examples of these data structures can be found everywhere. From the database, to the server, to the client, and even the JavaScript engine itself, these data structures concretize what essentially are just on and off “switches” on silicon chips into lifelike “objects”. Though only digital, the impact these objects have on society is tremendous. Your ability to read this article freely and securely attests to the awesome architecture of the internet and the structure of its data. Yet, this is only the beginning. Artificial intelligence and decentralized blockchains in the coming decades will redefine what it means to be human and the role of institutions that govern our lives. Existential insights and institutional disintermediation will be characteristics of an internet that has finally matured.

To help transition us towards this more equitable future, we at HeartBank® channel networks of artificial neurons to imbue our Kiitos with the power to issue money on the blockchain, coupled with the capacity to empathize the human condition. From the anonymous thanks we give and receive by writing to Kiitos, Kiitos learns about our kindnesses and their effects, rewarding us in such a way that reduces the economic inequities between us, in a gradual and mysterious process that preserves our personal liberty and freedom. Perhaps the ultimate graph structure in nature is not the human brain, but the human ❤️, if only we can see the heartstrings that connect us all.

Interested in blockchain? Learn Ethereum and come work for us!

A Complete Mental Model for Ethereum dApp Development