Cómo elegir una estructura de datos

Entre 1023 claves, una búsqueda lineal de una clave ausente hace 1023 comparaciones, la búsqueda binaria hace 10 y una tabla hash con 1023 cubetas hizo 6 como máximo en el laboratorio.

Empieza por las preguntas que vas a hacer

Ninguna estructura es la mejor para todo. Cada una abarata algunas operaciones encareciendo otras, así que la forma de elegir es enumerar lo que tu programa hará con más frecuencia. El 6.006 del MIT divide las posibilidades en dos interfaces. Una secuencia guarda los elementos en un orden que tú decides (primero, segundo, tercero), y los pides por posición. Un conjunto (set) guarda los elementos por clave, y preguntas si una clave está, o cuál es la más pequeña, o cuál sigue después de una clave dada. Un conjunto sin las preguntas de orden se llama diccionario.

Algunas situaciones comunes y la respuesta habitual:

• Leer elementos por posición, agregar al final: un arreglo dinámico (un arreglo de JavaScript).
• Historial de deshacer, emparejar paréntesis, búsqueda en profundidad: una pila, que es un arreglo que solo se usa por el final.
• Trabajos atendidos en orden de llegada, búsqueda en anchura: una cola, con un índice head o un búfer circular en lugar de shift sobre un arreglo largo.
• Buscar cosas por nombre o id: una tabla hash, que en JavaScript significa Map o Set.
• Mantener las claves ordenadas mientras se insertan y eliminan, pedir la clave siguiente: un árbol binario de búsqueda equilibrado.
• Muchas inserciones y eliminaciones en un lugar que ya tienes ubicado: una lista enlazada.

La misma búsqueda en cinco estructuras

El laboratorio de abajo guarda las mismas claves de cinco maneras y cuenta las comparaciones necesarias para encontrar una de ellas. Las claves son 15, 127 o 1023 números enteros al azar. El arreglo sin ordenar usa búsqueda lineal. El arreglo ordenado usa búsqueda binaria. El árbol equilibrado se construyó insertando primero las claves del medio, así que es lo más bajo posible. El otro árbol se construyó con las claves en orden, así que es una cadena. La tabla hash tiene tantas cubetas como claves y cuenta 1 por calcular h(k).

Con 15 claves las diferencias son pequeñas: la búsqueda lineal necesita 8 comparaciones en promedio y la binaria, unas 3.3. Con 1023 claves ya no lo son. La búsqueda lineal promedia 512 y necesita 1023 para una clave ausente, mientras que la búsqueda binaria y el árbol equilibrado nunca necesitan más de 10. El árbol en cadena es tan malo como la búsqueda lineal. La tabla hash se mantiene entre 2.3 y 2.5 en promedio en todos los tamaños porque sus cadenas siguen cortas, y en este laboratorio su peor caso con 1023 claves fue 6. Por eso Map es la opción predeterminada para las búsquedas, y por eso las estructuras ordenadas solo valen la pena cuando también necesitas el orden.

Cada celda de estas dos tablas es la tasa de crecimiento del costo para n elementos, según las tablas de las notas de clase 2, 4 y 7 del MIT. Las tablas hash y los árboles de búsqueda solo aparecen en la segunda tabla porque trabajan por clave, no por posición. En un arreglo sin ordenar o en una lista, insertar una clave cuesta n porque primero hay que comprobar que no esté ya. El arreglo ordenado encuentra rápido, pero tiene que mover valores para hacer sitio a una clave nueva.

¿Map u objeto?

Los programas de JavaScript suelen usar un objeto normal como diccionario, escribiendo prices["apple"]. MDN da razones para preferir Map cuando las claves vienen de los datos: un objeto tiene un prototipo, así que contiene claves predeterminadas que podrían chocar con las tuyas; un Map puede usar cualquier valor como clave, no solo cadenas y símbolos; su tamaño es una sola propiedad, map.size; y se recorre en orden de inserción. Los objetos siguen siendo la opción natural para registros con un conjunto fijo de campos con nombre.