Los sets y diccionarios de Python pueden tener un rendimiento de tiempo cuadrático
Python sets and dictionaries can have quadratic-time performance
Aunque se suele decir que los diccionarios y sets de Python son O(1), en la práctica pueden degradarse. Con claves que colisionan, insertar y consultar pasa de lineal a cuadrático: 16.000 elementos tardan más de un segundo. Incluso sin colisiones, un dict de un millón de claves es nueve veces más lento que una estructura inmutable optimizada, porque no cabe en la caché. El artículo muestra mediciones y explica por qué el modelo de tiempo constante es una simplificación.
La lección es siempre la misma. Algunos modelos son útiles, pero ninguno es la realidad. Sé consciente de los sesgos cognitivos.
- ot
O(1) no significa constante, significa acotado por una constante. Un algoritmo puede ser más rápido con n pequeña y converger a una asíntota horizontal cuando n tiende a infinito, y aún así sería O(1).
En una máquina real no existe el infinito, pero cientos de GB de memoria son "suficientemente infinitos" comparados con el tamaño de la caché [1]. Así que el análisis asintótico sigue siendo un modelo decente.
Me sorprende que incluso un profesor de CS confunda esto.
[1] Ok, si queremos ser pedantes, el acceso a memoria es logarítmico debido al recorrido de las tablas de páginas, pero puedes usar huge pages.
- juancn
Eso suele ser cierto en todas las implementaciones comunes de tablas hash (cuando los objetos no tienen un orden definido, si lo tienen puedes obtener O(1) promedio y O(log N) en el peor caso), independientemente del lenguaje.
El O(1) es el caso promedio esperado, que normalmente se cumple.
Sí, O(N^2) es teóricamente posible, pero a menos que te estés defendiendo de algún tipo de ataque de denegación de servicio, en la práctica rara vez importa.
Aun así, si puedes adivinar un tamaño inicial sensato para una tabla hash, puedes evitar gran parte de la sobrecarga del rehashing.
- northisup
Raymond Hettinger tiene una charla genial sobre cuánto ha mejorado el dict de Python a lo largo de los años. Así que esto es súper interesante y probablemente hará que el dict incorporado sea mejor con el tiempo.
La lección de la charla es que si eres idiomático, te beneficiarás a medida que el lenguaje mejore.