Caso real

El vector le gana a la lista

En una charla de 2012, Bjarne Stroustrup midió insertar números en orden en una secuencia (buscando su sitio y luego insertando) con un vector y con una lista. Esperaba que la lista ganara con muchos elementos. El vector ganó en todos los tamaños probados, por mucho.

Después hubo un contrapunto: la medición mezcla buscar e insertar, y la búsqueda domina. Es un buen ejemplo de por qué hay que preguntar qué se mide.

Antes de aplicar su conclusión, pregúntate qué se midió: una medición distinta puede dar otro resultado.

Alguien repite el experimento de Stroustrup, pero ahora le da a la lista el nodo exacto donde insertar cada número, sin buscar. ¿Qué espera medir con 100 000 números?La lista gana: sin la búsqueda solo queda insertar, O(1) en la lista y desplazar valores en el vectorEl vector gana igual: la caché favorece al vector incluso cuando inserta sin buscar nada antes de insertarEmpatan: las dos hacen un O(n) por inserción, con o sin búsqueda previa, así que miden lo mismoEl vector gana por más: sin la búsqueda, el vector no necesita desplazar ningún valor al insertar