En este artículo, aprenderemos por qué todo programador debería aprender estructuras de datos y algoritmos con la ayuda de ejemplos.
Este artículo es para aquellos que acaban de comenzar a aprender algoritmos y se preguntan qué impacto tendrá para impulsar sus habilidades profesionales / de programación. También es para aquellos que se preguntan por qué las grandes empresas como Google, Facebook y Amazon contratan programadores que son excepcionalmente buenos optimizando algoritmos.
¿Qué son los algoritmos?
De manera informal, un algoritmo no es más que una mención de los pasos para resolver un problema. Son esencialmente una solución.
Por ejemplo, un algoritmo para resolver el problema de los factoriales podría verse así:
Problema: encuentre el factorial de n
Inicializar hecho = 1 Para cada valor v en el rango de 1 an: Multiplica el hecho por v hecho contiene el factorial de n
Aquí, el algoritmo está escrito en inglés. Si estuviera escrito en un lenguaje de programación, lo llamaríamos código . Aquí hay un código para encontrar el factorial de un número en C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
La programación se trata de estructuras de datos y algoritmos. Las estructuras de datos se utilizan para almacenar datos, mientras que los algoritmos se utilizan para resolver el problema utilizando esos datos.
Las estructuras de datos y los algoritmos (DSA) analizan en detalle las soluciones a los problemas estándar y le brindan una idea de cuán eficiente es usar cada uno de ellos. También le enseña la ciencia de evaluar la eficiencia de un algoritmo. Esto le permite elegir la mejor de varias opciones.
Uso de estructuras de datos y algoritmos para hacer su código escalable
El tiempo es oro.
Supongamos que Alice y Bob están tratando de resolver un problema simple de encontrar la suma de los primeros 10 11 números naturales. Mientras Bob escribía el algoritmo, Alice lo implementó demostrando que es tan simple como criticar a Donald Trump.
Algoritmo (por Bob)
Inicialice sum = 0 para cada número natural n en el rango de 1 a 1011 (inclusive): agregue n a sum sum es su respuesta
Código (por Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice y Bob se sienten eufóricos de sí mismos porque podrían construir algo propio en casi un instante. Entremos a hurtadillas en su espacio de trabajo y escuchemos su conversación.
Alice: Ejecutemos este código y averigüemos la suma. Bob: Ejecuté este código hace unos minutos, pero todavía no muestra el resultado. ¿Qué tiene de malo?
¡Huy! Algo salió mal! Una computadora es la máquina más determinista. Regresar e intentar ejecutarlo nuevamente no ayudará. Así que analicemos qué está mal con este código simple.
Dos de los recursos más valiosos para un programa de computadora son el tiempo y la memoria .
El tiempo que tarda la computadora en ejecutar el código es:
Tiempo para ejecutar el código = número de instrucciones * tiempo para ejecutar cada instrucción
El número de instrucciones depende del código que utilizó, y el tiempo necesario para ejecutar cada código depende de su máquina y compilador.
En este caso, el número total de instrucciones ejecutadas (digamos x) es , que esx = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Supongamos que una computadora puede ejecutar instrucciones en un segundo (puede variar según la configuración de la máquina). El tiempo necesario para ejecutar el código anterior esy = 108
Tiempo necesario para ejecutar el código = x / y (más de 16 minutos)
¿Es posible optimizar el algoritmo para que Alice y Bob no tengan que esperar 16 minutos cada vez que ejecutan este código?
Estoy seguro de que ya adivinó el método correcto. La suma de los primeros N números naturales viene dada por la fórmula:
Suma = N * (N + 1) / 2
Convertirlo en código se verá así:
int suma (int N) (return N * (N + 1) / 2;)
Este código se ejecuta en una sola instrucción y realiza la tarea sin importar cuál sea el valor. Sea mayor que el número total de átomos del universo. Encontrará el resultado en poco tiempo.
El tiempo necesario para resolver el problema, en este caso, es 1/y(que es de 10 nanosegundos). Por cierto, la reacción de fusión de una bomba de hidrógeno tarda entre 40 y 50 ns, lo que significa que su programa se completará con éxito incluso si alguien arroja una bomba de hidrógeno en su computadora al mismo tiempo que ejecuta su código. :)
Nota: Las computadoras toman algunas instrucciones (no 1) para calcular la multiplicación y la división. He dicho 1 sólo por simplicidad.
Más sobre escalabilidad
La escalabilidad es escala más capacidad, lo que significa la calidad de un algoritmo / sistema para manejar el problema de un tamaño mayor.
Considere el problema de configurar un aula de 50 estudiantes. Una de las soluciones más sencillas es reservar una habitación, conseguir una pizarra, unas tizas y el problema está resuelto.
Pero, ¿y si aumenta el tamaño del problema? ¿Qué pasa si el número de estudiantes aumenta a 200?
La solución aún se mantiene, pero necesita más recursos. En este caso, probablemente necesitará una sala mucho más grande (probablemente un cine), una pantalla de proyección y un lápiz digital.
¿Qué pasa si el número de estudiantes aumenta a 1000?
La solución falla o consume muchos recursos cuando aumenta el tamaño del problema. Esto significa que su solución no era escalable.
Entonces, ¿qué es una solución escalable?
Consider a site like Khanacademy, millions of students can see videos, read answers at the same time and no more resources are required. So, the solution can solve the problems of larger size under resource crunch.
If you see our first solution to find the sum of first N natural numbers, it wasn't scalable. It's because it required linear growth in time with the linear growth in the size of the problem. Such algorithms are also known as linearly scalable algorithms.
Our second solution was very scalable and didn't require the use of any more time to solve a problem of larger size. These are known as constant-time algorithms.
Memory is expensive
Memory is not always available in abundance. While dealing with code/system which requires you to store or produce a lot of data, it is critical for your algorithm to save the usage of memory wherever possible. For example: While storing data about people, you can save memory by storing only their age not the date of birth. You can always calculate it on the fly using their age and current date.
Examples of an Algorithm's Efficiency
Here are some examples of what learning algorithms and data structures enable you to do:
Example 1: Age Group Problem
Problems like finding the people of a certain age group can easily be solved with a little modified version of the binary search algorithm (assuming that the data is sorted).
The naive algorithm which goes through all the persons one by one, and checks if it falls in the given age group is linearly scalable. Whereas, binary search claims itself to be a logarithmically scalable algorithm. This means that if the size of the problem is squared, the time taken to solve it is only doubled.
Suppose, it takes 1 second to find all the people at a certain age for a group of 1000. Then for a group of 1 million people,
- the binary search algorithm will take only 2 seconds to solve the problem
- the naive algorithm might take 1 million seconds, which is around 12 days
The same binary search algorithm is used to find the square root of a number.
Example 2: Rubik's Cube Problem
Imagine you are writing a program to find the solution of a Rubik's cube.
This cute looking puzzle has annoyingly 43,252,003,274,489,856,000 positions, and these are just positions! Imagine the number of paths one can take to reach the wrong positions.
Fortunately, the way to solve this problem can be represented by the graph data structure. There is a graph algorithm known as Dijkstra's algorithm which allows you to solve this problem in linear time. Yes, you heard it right. It means that it allows you to reach the solved position in a minimum number of states.
Example 3: DNA Problem
DNA is a molecule that carries genetic information. They are made up of smaller units which are represented by Roman characters A, C, T, and G.
Imagine yourself working in the field of bioinformatics. You are assigned the work of finding out the occurrence of a particular pattern in a DNA strand.
It is a famous problem in computer science academia. And, the simplest algorithm takes the time proportional to
(number of character in DNA strand) * (number of characters in pattern)
A typical DNA strand has millions of such units. Eh! worry not. KMP algorithm can get this done in time which is proportional to
(number of character in DNA strand) + (number of characters in pattern)
The * operator replaced by + makes a lot of change.
Considering that the pattern was of 100 characters, your algorithm is now 100 times faster. If your pattern was of 1000 characters, the KMP algorithm would be almost 1000 times faster. That is, if you were able to find the occurrence of pattern in 1 second, it will now take you just 1 ms. We can also put this in another way. Instead of matching 1 strand, you can match 1000 strands of similar length at the same time.
And there are infinite such stories…
Final Words
Generally, software development involves learning new technologies on a daily basis. You get to learn most of these technologies while using them in one of your projects. However, it is not the case with algorithms.
Si no conoce bien los algoritmos, no podrá identificar si puede optimizar el código que está escribiendo en este momento. Se espera que los conozca de antemano y los aplique siempre que sea posible y crítico.
Hablamos específicamente sobre la escalabilidad de los algoritmos. Un sistema de software consta de muchos de estos algoritmos. La optimización de cualquiera de ellos conduce a un mejor sistema.
Sin embargo, es importante tener en cuenta que esta no es la única forma de hacer que un sistema sea escalable. Por ejemplo, una técnica conocida como computación distribuida permite que partes independientes de un programa se ejecuten en varias máquinas juntas, lo que lo hace aún más escalable.
