Diagnóstico

El importador que se volvió lento

Un programa importa 100 000 pedidos y los guarda en un array. Con 1000 pedidos tardaba un instante; con 100 000 tarda segundos, y con un millón, minutos. El autor sospecha del disco.

El código, simplificado:

Texto

para cada pedido p en archivo:    insertar(pedidos, 0, p)    # el más nuevo primero

Razona antes de responder: ¿qué hipótesis explica que el tiempo crezca mucho más que el número de pedidos? ¿Qué evidencia la separa de la del disco?

Un importador inserta cada pedido en la posición 0 de un array. Con 1000 pedidos tarda un instante y con 100 000 tarda segundos. ¿Qué hipótesis explica que el tiempo crezca mucho más que el número de pedidos?Insertar en 0 desplaza todos los pedidos: el total crece como n²; si al duplicarlos el tiempo se cuadruplica, es estoEl array se llena y crece de vez en cuando copiando todo; si el tiempo salta solo en ciertos tamaños, es estoLeer el archivo es lo lento, porque cada línea relee las anteriores; si quitar la inserción no cambia el tiempo, es estoEl disco lee más bytes con más pedidos; si al duplicarlos el tiempo solo se duplica, es el disco y no el array