Una introducción a los algoritmos y las estructuras de datos (edición de Javascript)

Introducción

Comprender los algoritmos y las estructuras de datos es crucial para mejorar su rendimiento 10 veces más que sus pares que no lo hacen. Esto se debe a que analiza los problemas críticamente e idea los mejores medios para resolverlos. Podría significar acelerar los tiempos de solicitud del servidor o encontrar la mejor manera de almacenar grandes conjuntos de datos con un espacio mínimo en disco.

Este artículo tiene como objetivo ayudarlo a comprender los conceptos básicos de algoritmos y estructuras de datos y cómo implementarlos usando JavaScript.

¿Qué es un algoritmo? Un algoritmo es un conjunto de instrucciones paso a paso para realizar una tarea. Suponga que tiene problemas para levantarse temprano y no cumple con los plazos. ¿Cómo resuelves esto? ¡Ajá! Establecer alarmas. Así es como se ve un algoritmo.

Las estructuras de datos, por otro lado, son formas de almacenar datos de manera eficiente.

Las estructuras de datos y los algoritmos (DSA) son tan vitales que son fundamentales para el rendimiento general de una computadora. El algoritmo que elija determinará su tiempo de ejecución (notación Big O) o su eficiencia. Algunos DSA populares son la búsqueda binaria, la recursividad, la ordenación, las matrices, las listas vinculadas y las tablas hash.

¿Qué es la búsqueda binaria?

Suponga que está buscando un nombre en el directorio de un país; comienza con una J. Puede comenzar desde el principio (desde los países "A") y seguir pasando las páginas hasta llegar a la lista de países "J" (estos países están ordenados alfabéticamente). Si el país comienza con una "Z", entonces sigue hojeando hasta el final del directorio. Esto se conoce como un algoritmo de búsqueda simple. Pero imagínese si se tratara de un directorio telefónico con más de 100.000 números de teléfono, esto es inimaginablemente difícil. ¿Cómo optimizas esto? Búsqueda binaria al rescate.

El algoritmo de búsqueda binaria toma una lista ordenada de elementos como entrada, y si el elemento que está buscando está en la lista, la búsqueda binaria devuelve la posición donde se encuentra, de lo contrario, devuelve nulo. En lugar de ir paso a paso para llegar a Japón, la búsqueda binaria divide esta matriz en varias partes y busca cada una de ellas en consecuencia.

De esta manera, la búsqueda es rápida.

arreglos

Son una colección de elementos indexados por una clave. Los elementos de la matriz se almacenan secuencialmente, y la clave sirve como identificador en la colección. Sus índices comienzan con 0.

Son súper útiles porque recuperar u ordenar cualquier elemento lleva un tiempo constante O(1). también se puede usar para implementar muchas otras estructuras de datos que imponen restricciones adicionales sobre cómo se manipulan los datos. Una cadena, por ejemplo, puede implementarse como una matriz de caracteres.

Aquí hay una implementación de matrices y búsqueda binaria en JavaScript.

 function binary_search(list, item) { let guess = list.find(element => element == item); if (guess) { return guess + "\ncountry index no: " + list.findIndex(country => country === guess); } return null + ": element is not in the array" } console.log(binary_search(country_list, 'Japan')); // Japan | country index no: 109 console.log(binary_search(country_list, 'Cookie')); // null: element is not in the array

Algoritmo de clasificación

Los programadores rara vez utilizan la clasificación. En su mayoría, ya lo maneja el lenguaje o las bibliotecas en las que codifican. El lenguaje JavaScript, por ejemplo, ordena las matrices mediante la ordenación por inserción, la ordenación en montón o la ordenación rápida.

Heapsort es similar al método de filtro de matriz de Javascript. Divide la entrada en una región ordenada y una región no ordenada y mueve elementos iterativamente a la región ordenada. Aquí hay un ejemplo;

Lista enlazada

Una lista enlazada es una estructura de datos en la que cada elemento contiene datos y un puntero al siguiente elemento de la lista. Una característica distintiva de una lista enlazada es que sus elementos pueden estar dispersos en cualquier parte de la memoria. Esto no es cierto para las matrices. Vea algunos ejemplos a continuación;

¿Qué son las tablas hash?

Las tablas hash son listas de elementos arbitrarios en una matriz. El elemento a almacenar o su clave se utiliza como índice en la matriz. Aquí hay un ejemplo:

La función hash convierte la clave de los elementos que se colocarán en un hash, luego asigna los elementos hash a un lugar específico en la tabla. Cada uno de estos elementos también puede ser una submatriz de elementos arbitrarios en la tabla.

recursividad

La recursividad es una técnica de codificación utilizada en muchos otros algoritmos. Es un atajo para un código extenso y es posible que no ofrezca ninguna mejora en el rendimiento excepto para el programador.

Supongamos que encuentras una maleta del tesoro. Para desbloquear este caso, debe tomar una llave de una caja con otras cajas más pequeñas, que aún pueden tener otras cajas en ellas.

Un enfoque es hacer una lista de montones de casillas para buscar y luego revisar cada una de estas casillas. Si encuentras una llave, ¡genial! De lo contrario, agregue la nueva caja vacía a la lista de pila para buscar más tarde.

La recursividad elimina el paso en el que agrega el nuevo cuadro vacío encontrado a una lista de búsqueda. Llama al método de búsqueda inmediatamente en el nuevo cuadro encontrado vacío. Aquí hay un ejemplo en Javascript;

 const suitCase = new Map(); suitCase.set('box-0', '') .set('box-1', '') .set('box-2', '') .set('box-3', '') .set('box-4', 'key') .set('box-5', '') .set('box-6', ''); function search (suit) { for (let [key, value] of suit) { if (value === 'key') { console.log(`Found ${value} at ${key}!`); } } } search(suitCase); // prints Found key at box-4!

¡Encontraste la llave, Tada!

En resumen, DSA es una excelente manera de pensar de manera efectiva como programador. Te da herramientas para resolver problemas difíciles. Haga clic en el enlace del repositorio de GitHub para descargar todos los fragmentos de código utilizados en este artículo. ¡Feliz hackeo!

Repositorio de código de GitHub