Diagnóstico

La carga que tarda veinte minutos

Un proceso nocturno construye un índice de 2 millones de productos en un array ordenado. Con 100 000 productos tardaba 3 segundos; ahora tarda unos 20 minutos. La memoria no cambió de forma notable.

Texto

para cada producto p en catálogo:    insertar(índice, p.código, p)

Un proceso nocturno construye un índice de 2 millones de productos en un array ordenado, insertando cada uno con insertar(índice, código, p); el catálogo llega en cualquier orden. Con 100 000 productos tardaba 3 segundos y ahora unos 20 minutos. ¿Qué hipótesis explica el salto y qué arreglo propones?Insertar uno a uno es O(n²): 20 veces más productos, unas 400 veces más trabajo; cargar todo y ordenar una vezLa búsqueda binaria se vuelve lenta con 2 millones de claves; cambiar a una búsqueda lineal que no dependa del ordenFalta memoria y el sistema empieza a usar el disco en lugar de la memoria principal; ampliar la memoriaEl array se llena y crece copiando todo cada vez que se agota; reservar la capacidad antes de cargar