Caso real

Un experimento de Bjarne Stroustrup

La documentación de la biblioteca estándar de Rust dice que Vec y HashMap cubren la mayoría de los casos. Vec es un array que crece, y el vector de la biblioteca estándar de C++ es su equivalente. Bjarne Stroustrup, creador de C++, midió en 2012 qué pasa al insertar números en orden, buscando antes su lugar, en un vector y en una lista enlazada.

Antes de ver su resultado, predícelo.

Mantienes 50 000 números ordenados. Por cada número nuevo recorres hasta encontrar su lugar y lo insertas. En una lista enlazada insertar es cambiar enlaces; en un array hay que desplazar. ¿Qué esperas al medir ambas?La lista más rápida: con 50 000 números el array se llena y copia todo en cada inserciónLa lista más rápida: insertar es cambiar enlaces, mientras que el array desplaza hasta n valores cada vezExactamente igual: con el mismo O por inserción, el tiempo medido en las dos es prácticamente el mismoEl array igual o más rápido: ambas recorren hasta el lugar, y el array lo hace en memoria contigua