¿Qué hace que los conjuntos sean más rápidos que las listas?

La wiki de python dice: “La prueba de membresía con conjuntos y diccionarios es mucho más rápida, O (1), que las secuencias de búsqueda, O (n). Al probar” a en b “, b debe ser un conjunto o diccionario en lugar de una lista o tupla “.

He estado usando conjuntos en lugar de listas siempre que la velocidad es importante en mi código, pero últimamente me pregunto por qué los conjuntos son mucho más rápidos que las listas. ¿Alguien podría explicar, o señalarme a una fuente que explique, qué es exactamente lo que está sucediendo detrás de escena en Python para hacer que los sets sean más rápidos?

Los conjuntos se implementan utilizando tablas hash . Siempre que agregue un objeto a un conjunto, la posición dentro de la memoria del objeto set se determina utilizando el hash del objeto que se agregará. Cuando se prueba la membresía, todo lo que debe hacerse es básicamente observar si el objeto está en la posición determinada por su hash, por lo que la velocidad de esta operación no depende del tamaño del conjunto. Para las listas, por el contrario, se debe buscar en toda la lista, que se volverá más lenta a medida que la lista crezca.

Esta es también la razón por la que los conjuntos no conservan el orden de los objetos que agrega.

Tenga en cuenta que los conjuntos no son más rápidos que las listas en general: la prueba de pertenencia es más rápida para los conjuntos, y también lo es la eliminación de un elemento. Mientras no necesite estas operaciones, las listas a menudo son más rápidas.

list : imagina que estás buscando tus calcetines en tu armario, pero no sabes en qué cajón están tus calcetines, por lo que debes buscar cajón por cajón hasta que los encuentres (o tal vez nunca lo hagas). Eso es lo que llamamos O(n) , porque en el peor de los casos, buscará en todos sus cajones (donde n es el número de cajones).

set : Ahora, imagina que todavía estás buscando tus calcetines en tu armario, pero ahora sabes en qué cajón están tus calcetines, por ejemplo, en el tercer cajón. Por lo tanto, solo buscará en el tercer cajón, en lugar de buscar en todos los cajones. Eso es lo que llamamos O(1) , porque en el peor de los casos se verá en un solo cajón.

Creo que necesitas echar un buen vistazo a un libro sobre estructuras de datos. Básicamente, las listas de Python se implementan como matrices dinámicas y los conjuntos se implementan como tablas hash .

La implementación de estas estructuras de datos les da características radicalmente diferentes. Por ejemplo, una tabla hash tiene un tiempo de búsqueda muy rápido pero no puede conservar el orden de inserción.

Python usa tablas hash , que tienen búsqueda O (1).

Aunque hasta ahora no he medido nada relacionado con el rendimiento en python, todavía me gustaría señalar que las listas suelen ser más rápidas.

Sí, tienes O (1) vs. O (n). Pero siempre recuerda que esto proporciona información solo sobre el comportamiento asintótico de algo. Eso significa que si tu n es muy alta O (1) siempre será más rápido, en teoría. En la práctica, sin embargo, a menudo debe ser mucho más grande de lo que será su conjunto de datos habitual.

Por lo tanto, los conjuntos no son más rápidos que las listas per se, pero solo si tienes que manejar muchos elementos.

Una lista debe buscarse una por una, donde un conjunto o diccionario tiene un índice para una búsqueda más rápida.