Me asignaron una tarea similar a principios de los 80 para crear una forma más rápida de encontrar variables en una tabla de símbolos durante la depuración de un sistema operativo en tiempo real para un analizador de gases en sangre.
Primero hice el método de tabla hash y funcionó bien.
Luego pensé en las pestañas de un diccionario y utilicé una idea de indexación que dividió la lista en 26 piezas basadas en el primer carácter.
- Cómo hacer un método que devuelva un arrayList que ha ordenado el número de Strings en cada fila del archivo
- ¿Es un mal hábito ejecutar algoritmos solo en un papel?
- ¿El mismo algoritmo pertenece a algo, incluyendo política, mecánica cuántica, arte, deportes e ingeniería?
- ¿Es un nodo raíz un nodo interno en una estructura de datos de árbol?
- Quiero aprender la estructura de datos y Java, ¿cuál debería aprender primero?
Esto equivalía al tiempo utilizado por el método de tabla hash.
Cuando lo modifiqué nuevamente para usar 676 piezas, la mejora de velocidad resultante fue enorme.
Esto eventualmente se convirtió en lo que yo llamo un bosque alfabético con 676 árboles con cada árbol basado en las primeras 2 letras del símbolo.
Los enlaces a los árboles se almacenan en una matriz con los primeros caracteres reducidos a los índices utilizando valores ASCII y restando el valor de A para obtener un índice de matriz basado en cero.
Este es también el método que utilicé para ordenar la lista que resultó en una mejora de la velocidad sobre la clasificación rápida por un factor de 6 a 10 para las mismas tablas de símbolos.
Tener en cuenta que los árboles ya contienen los primeros caracteres también puede generar ahorros de memoria al no almacenar los primeros en letras de cada elemento del árbol.
