Clasificación : encuentro que la clasificación de Radix es la más interesante porque puede clasificarse en un tiempo casi lineal. En los días anteriores a los algoritmos de clasificación enlatados que ahora puede obtener en varias bibliotecas, y antes del advenimiento de las bases de datos, tuve que ordenar los archivos llenos de datos de fila en lo que sería para nuestros estándares una máquina muy lenta.
Inicialmente, utilicé el tipo de burbuja que era el más fácil de implementar, pero también uno de los algoritmos de clasificación más lentos posibles. A veces tomaba media hora hacer el tipo.
Entonces se me ocurrió cómo acelerar las cosas tremendamente: creando “cubos” para las entradas indexadas por el primer carácter en la línea para ordenar esas cadenas. Luego, para aquellos cubos con múltiples cadenas, cree subgrupos y divídalos usando el segundo carácter como índice, etc.
- ¿Qué algoritmo es mejor para datos no estructurados?
- ¿Cuánta codificación necesito saber antes de comenzar con los algoritmos?
- Cómo demostrar que este gráfico todavía puede estar fuertemente conectado
- ¿Cómo funciona el retroceso en el caso de encontrar un subconjunto de una suma particular?
- No sé nada sobre algoritmos. Por donde puedo empezar
El tiempo de clasificación pasó de 30 minutos a menos de 30 segundos. Todos estaban asombrados de cómo logré acelerar las cosas tanto. No estoy seguro de si lo leí en alguna parte o lo reinventé de la nada, pero luego descubrí que había hecho una variante del tipo Radix , el más rápido de todos.
Los datos eran ASCII en aquel entonces. El mundo UTF-8 de hoy requeriría algunas modificaciones para lidiar con los diversos problemas de secuencia de clasificación. Pero hoy, simplemente usarías algo de una biblioteca y ni siquiera pensarías mucho en ello. O incluso más fácil: simplemente canalice el archivo a través del comando de clasificación en Linux. Hecho.
Estructuras de datos : hay todo tipo de estructuras de datos. Por desgracia, los idiomas de nivel superior de hoy en día han eliminado la diversión de crear algunos de los más elaborados.
Depende de la naturaleza del problema que esté tratando de resolver qué estructura de datos utiliza. El más común, prácticamente invisible en estos días, es la pila . (Casi) todas las computadoras modernas usan pilas para manejar funciones que llaman a otras funciones, y en ese caso, esas pilas tendrán marcos de pila para que la función pueda pegar variables en las que está trabajando allí temporalmente. Somos poco conscientes de ello utilizando lenguajes de alto nivel que ocultan todos los detalles finos. Si está utilizando C , es mucho más consciente de ello.
Los árboles siempre son divertidos, y atraviesan los árboles aún más. El análisis generalmente usa árboles para analizar las declaraciones. XML y HTML tienen básicamente estructuras de árbol implícitas en su sintaxis. Los compiladores usan árboles de análisis todo el tiempo. Es posible que haya oído hablar del árbol de sintaxis abstracta , por ejemplo.
En mis días en C , implementaba listas doblemente vinculadas todo el tiempo, y enfoques muy inteligentes para hacer las inserciones y eliminaciones en dicha lista. Si se hace correctamente, dependiendo de la arquitectura, estos enfoques podrían incluso funcionar con múltiples hilos sin bloqueo, pero eso fue en máquinas de un solo núcleo. No estoy tan seguro de que esos trucos funcionen hoy en plataformas multinúcleo sin un pequeño bloqueo.
Lo que he descrito aquí es bastante básico y ubicuo . Los encuentro interesantes porque se usan prácticamente todo el tiempo . Puede, por supuesto, tener estructuras de datos más “esotéricas”, pero luego está hablando de espacios de problemas altamente especializados. Si está haciendo un tablero de juego para, por ejemplo, algún tipo de juego estratégico o de tipo RPG , tendría una estructura de datos de cuadrícula que modelaría, por ejemplo, un diseño hexagonal . Y hay trucos inteligentes que también puedes jugar allí. Podría salirse con la suya, por ejemplo, utilizando un diseño de cuadrícula cartesiana normal. Pero lo dejaré como un ejercicio para el estudiante.
