Diagnóstico

«Es O(n), no puede ser tan lento»

Un servicio recorre una lista enlazada de 10 millones de eventos cada minuto. Tras pasar de array a lista «para insertar más rápido», el recorrido tarda cinco veces más. El autor insiste en que los dos son O(n).

Un servicio recorre una lista enlazada de 10 millones de eventos cada minuto. Tras pasar de array a lista «para insertar más rápido», el recorrido tarda cinco veces más, y el autor insiste en que los dos son O(n). ¿Qué hipótesis explica el cambio y cómo la verificas?El servicio tiene menos memoria que antes del cambio; se verifica ejecutándolo en otra máquina con más memoriaEl recorrido de la lista es O(n²) y no O(n); se verifica duplicando los eventos y viendo si el tiempo se cuadruplicaLa lista recorre algunos nodos dos veces por un error de enlaces; se verifica contando los nodos que visita el recorridoLa lista pierde la localidad: cada nodo es un viaje a memoria; medir fallos de caché o recorrer los mismos datos en un array