Estructuras de datos y algoritmos es uno de los temas más importantes. Otros incluyen: Diseño y análisis de algoritmos, lenguajes de programación, sistemas operativos, matemática discreta y álgebra lineal.
Desde entonces, trabajo en el campo de los sistemas operativos y compiladores. Le mostraré la importancia de las estructuras de datos y los algoritmos utilizando algunos ejemplos del mundo real de proyectos populares de código abierto como Linux Kernel, GNU C Compiler, etc.
- Procesos en el kernel de Linux: un ejemplo muy simple (pero muy importante en términos de rendimiento y seguridad) para mostrar la relevancia de las matrices y los diferentes tipos de listas vinculadas en el kernel de Linux. Supongamos que está diseñando un sistema operativo y desea mantener la colección de procesos actualmente en ejecución o en espera. ¿Cómo guardas esa colección? Hay dos maneras:
- Asigne una matriz de punteros y establezca el elemento de cada matriz en el puntero a un objeto de proceso. ¿Suena bien verdad? Pero, ¿puede la matriz crecer dinámicamente? No. Entonces, puede usar el concepto de vector en C ++, es decir, primero asignar una matriz de tamaño fijo, luego crecer 2 veces cada vez que la matriz se llena. Parece bueno ¿verdad?
Pero, aquí hay dos problemas: (i) cada vez que reasigne la matriz, debe copiar todos los elementos de la matriz previamente asignada a una nueva matriz, y (ii) tomar el punto cuando ha crecido la matriz dos veces, casi la mitad de el espacio recién asignado está vacío, lo que puede usarse para otros fines. Por lo tanto, el punto (i) usa ciclos adicionales y el punto (ii) usa memoria adicional, cualquiera de los cuales no está disponible para un Kernel. - Ahora veamos los requisitos de la colección de procesos: (i) ¿dónde vamos a insertar un proceso recién creado en la colección? al final de la lista porque solo necesitamos una colección de todos los procesos; (ii) ¿necesitamos acceder a un proceso en un índice específico? No, solo necesitamos acceder al primer objeto de la lista y mantener la lista; (iii) queremos que se elimine un proceso en O (1) no en O (N). Entonces, ¿qué estructura de datos podemos usar con las condiciones anteriores? Una lista parece ser una mejor opción. Porque, no está tomando memoria adicional (de acuerdo, hay un puntero de 4 bytes (u 8 bytes), pero cuando se compara con el espacio adicional del vector, todavía es menor), y no hay cálculos adicionales. Entonces, una Lista es una mejor opción. Pero, para eliminar un elemento de una lista, necesitamos tener un puntero al elemento anterior. Entonces, incluso en la lista, la eliminación sería O (N), no O (1).
- Podemos usar la Lista Doblemente Vinculada para resolver el problema anterior, la eliminación es O (1) y no se desperdician ciclos de CPU adicionales. Recuerde que una Lista Doblemente Vinculada tiene una cabeza y una cola, y para insertar en la cabeza / cola, necesitamos realizar una comprobación de puntero NULL (recuerde, un nodo es una cola si el siguiente elemento en la lista es un puntero NULL). Espero que sepas lo que podría pasar si un puntero NULL es desreferenciado (Respuesta: Falla de segmentación o podría ser explotado por un atacante). Pero en una Lista Circular Doblemente Vinculada no hay cabeza ni cola, por lo tanto, se usa para eliminar el dolor de la comprobación de puntero NULL. Esto no solo aumentó la robustez del código escrito en Linux Kernel sino también la seguridad.
- El ejemplo anterior muestra cómo el Kernel de Linux realiza un seguimiento de todos los procesos. El kernel de Linux no utiliza un programador Round Robin, sino que utiliza un programador completamente justo (CFS). Este planificador funciona asignando una métrica a cada proceso, que se basa en el tiempo que ha pasado en ejecución y espera. CFS ejecuta un proceso que tiene el valor mínimo (o máximo, depende de cómo implemente esa métrica) de esta métrica. Entonces, ¿cómo se asegura de obtener el valor mínimo de la métrica en el menor tiempo posible? La respuesta es un árbol binario equilibrado. ¿Pero cual? AVL o Red Black Tree? Linux Kernel usa un Red Black Tree porque es más rápido que AVL (aunque la complejidad de cada operación es la misma, pero más rápido aquí significa, una implementación rápida y el Red Black Tree atraviesa el árbol solo una vez en la inserción o eliminación, mientras que AVL puede hacerlo 2 veces). También podemos usar Heap en este caso, pero Linux Kernel usa esta estructura de árbol para otras cosas también, lo que Heap no puede hacer de manera eficiente.
- La tabla de símbolos en GCC (o cualquier compilador) almacena el tipo de símbolo (nombre de variable, nombre de clase, etc.). Hay varias formas de implementar una tabla de símbolos y la forma ingenua sería crear dos matrices: s ymbol_array y type_array . Para cada índice i , type_array [ i ] representa el tipo del símbolo en symbol_array [ i ]. Esta implementación ingenua es demasiado lenta, porque busca en O (N), lo que definitivamente puede mejorarse. Una forma simple y más efectiva es usar una tabla hash, que puede devolver el tipo de un símbolo básicamente en el tiempo O (1).
Entonces, puede ver por qué es tan importante estudiar estructuras de datos y algoritmos. No creo que una persona deba estar haciendo programación competitiva todo el día para comprender qué DS y Algos usar en qué lugar. Pero esto también puede entenderse participando en el desarrollo de software y aprendiendo sobre prácticas populares de diseño de software.
- Los electrones son extraños. ¿Cómo conocen el camino más corto al suelo? ¿No tendrían que 'mirar' hacia adelante?
- ¿Existe un algoritmo informático para detectar 'noticias falsas'?
- ¿Qué es el algoritmo Google Panda?
- ¿Por qué mi profesor sugiere que usemos bucles en lugar de recurrencia en el código de producción?
- ¿Qué 'palabras' debo saber para resolver problemas de programación o problemas matemáticos relacionados?
