¿Por qué es más rápido convertir una lista en un conjunto que usar solo lista para calcular una diferencia de lista?

Digamos que deseo calcular la diferencia de dos listas C = A - B :

 A = [1,2,3,4,5,6,7,8,9] B = [1,3,5,8,9] C = [2,4,6,7] #Result 

A y B están ordenados con enteros únicos (no estoy seguro si hay una manera de decirle a Python sobre esta propiedad de la lista) . Necesito preservar el orden de los elementos. AFAIK hay dos formas posibles de hacerlo.

Método 1 : Convierta B en un conjunto y use la comprensión de lista para generar C:

 s = set(B) C = [x for x in A if x not in s] 

Método 2 : utilizar directamente la comprensión de la lista:

 C = [x for x in A if x not in B] 

¿Por qué es #1 más eficiente que #2 ? ¿No hay una sobrecarga para convertir a un conjunto? ¿Que me estoy perdiendo aqui?

Algunos puntos de referencia de rendimiento se dan en esta respuesta.

ACTUALIZACIÓN: soy consciente de que el tiempo de búsqueda O(1) promedio de un conjunto supera al de O(n) de una lista, pero si la lista original A contiene aproximadamente un millón o más de enteros, ¿la creación del conjunto no tardaría más?

Hay una sobrecarga para convertir una lista en un conjunto, pero un conjunto es sustancialmente más rápido que una lista para aquellos in pruebas.

Puede ver instantáneamente si el elemento x está en conjunto y porque hay una tabla hash que se está utilizando debajo. No importa qué tan grande sea su conjunto, el tiempo de búsqueda es el mismo (básicamente instantáneo); esto se conoce en notación Big-O como O (1). Para obtener una lista, debe verificar individualmente cada elemento para ver si el elemento x está en la lista z . A medida que su lista crezca, la verificación tomará más tiempo, esto es O (n), lo que significa que la duración de la operación está directamente relacionada con la duración de la lista.

Esa mayor velocidad puede compensar la sobrecarga de creación del conjunto, que es la forma en que su verificación de conjunto termina siendo más rápida.

EDITAR: para responder a esa otra pregunta, Python no tiene forma de determinar si su lista está ordenada, no si está utilizando un objeto de list estándar, de todos modos. Por lo tanto, no puede alcanzar el rendimiento O (log n) con una lista de comprensión. Si desea escribir su propio método de búsqueda binario que asume que la lista está ordenada, puede hacerlo, pero O (1) vence a O (log n) cualquier día.

El tiempo promedio de complejidad para la búsqueda (x en S) en un conjunto es O (1), mientras que el mismo para una lista es O (n).

Puede consultar los detalles en https://wiki.python.org/moin/TimeComplexity

Según la documentación de Python sobre la complejidad del tiempo.

  • La lista de miembros x in s es una operación de tiempo lineal promedio, o O(n) .
  • Establecer la pertenencia x in s es una operación de tiempo constante promedio, o O(1) .

La construcción de un conjunto es una operación de tiempo lineal en el peor de los casos, ya que uno tendría que escanear todos los elementos en una lista para construir una tabla hash, por lo que O(n) . n es el número de elementos en una colección.

La observación clave es que, en el Método 1 , la construcción de un conjunto, s = set(B) es solo una operación de una sola vez, luego, a continuación, solo tenemos n número total de pruebas de membresía de set como en x not in B , así que en total O(n) + n * O(1) , o O(n) complejidad de tiempo.

Mientras que en el Método 2 , la prueba de la lista de miembros x not in B se lleva a cabo para cada elemento en A , por lo que en total n * O(n) = O(n^2) complejidad de tiempo.