¿Por qué utilizar un conjunto para las comparaciones de listas?

Question

Acabo de leer otra pregunta de los usuarios mientras busco la forma de calcular las diferencias en dos listas.

Python, compute list difference

Mi pregunta es ¿por qué habría de hacerlo

def diff(a,b): 
    b = set(b) 
    return [aa for aa in a if aa not in b] 

en lugar de hacer

def diff(a,b): 
    tmp = [] 
    for i in a: 
     if(i not in b): 
      tmp.append(i) 
return tmp 

edición: simplemente se dio cuenta de la segunda función diff realmente devuelto las similitudes. Debería ser correcto ahora.

Answer 1

Sólo a partir de una perspectiva algorítmica, se necesita O(n) para construir el conjunto y O(n) para hacer la lista por comprensión (ya que las pruebas de si un elemento está contenida en un conjunto es O(1)). Sin embargo, en el segundo ejemplo, tomaría O(n^2) recorrer ambas listas. Entonces, independientemente del lenguaje de programación, el primer enfoque es superior.

Además, las listas de comprensión en python son intrínsecamente más rápidas que un ciclo for. Esto reduce el factor constante aún más (y significativamente también). La razón por la cual se puede resumir en this post que cito aquí:

El hecho de que las listas por comprensión sólo pueden estar compuestos de expresiones, no declaraciones, es un factor considerable, ya que se requiere mucho menos trabajo detrás de las escenas para cada iteración. Otro factor es que el mecanismo de iteración subyacente para las comprensiones de listas es mucho más cerca de un bucle C que la ejecución de un bucle for.

Answer 2

La comprensión de listas generalmente se considera más eficiente que el uso de operaciones de listas regulares al crear una lista. Si la memoria es una preocupación, es posible que desee utilizar un generador en su lugar.

This proporciona un poco de información sobre las prestaciones de for -ops, map y list comprehension. @benhoyt también proporcionó un útil link que compara bucles versus comprensión de listas.

Sin embargo, tenga en cuenta que si el rendimiento es una preocupación específica, podría valer la pena tomarse el tiempo/comparar sus diversas opciones para seleccionar la mejor opción para sus requisitos específicos.

Answer 3

Utilizando el conjunto es generalmente más rápido, ya que sólo tiene que repetir b una vez, mientras que su ejemplo tiene que recorrer b una vez para cada elemento en a.

Answer 4

La principal diferencia entre las dos opciones es que la que usa set es asintóticamente mucho más eficiente.

En condiciones razonablemente favorables, al buscar un elemento en un conjunto se puede hacer en O(1) vez; buscar un elemento en una lista requiere O(n) vez.

La segunda diferencia, menos significativa, es que una versión usa una lista de comprensión mientras que la otra usa un ciclo for. Las listas de comprensión tienden a producir un código más compacto. También tienden a ser más eficientes (aunque si el rendimiento es una preocupación, la única forma de obtener una imagen precisa es mediante la ejecución de puntos de referencia).

Answer 5

he hecho algunas pruebas:

test_lists.py

a = range(1, 1000) 
b = range(2, 1002) 

tmp = [] 
for i in a: 
    if(i not in b): 
     tmp.append(i) 

test_set_list_comprehensions.py

a = range(1, 1000) 
b = range(2, 1002) 

b = set(b) 
[aa for aa in a if aa not in b] 

test_set.py

a = range(1, 1000) 
b = range(2, 1002) 
list(set(a).difference(set(b))) 

Y eso es lo timeit dice:

~$ python -m timeit 'import test_lists' 
1000000 loops, best of 3: 0.671 usec per loop 
~$ python -m timeit 'import test_set_list_comprehension' 
1000000 loops, best of 3: 0.766 usec per loop 
~$ python -m timeit 'import test_set' 
1000000 loops, best of 3: 0.656 usec per loop 

Así que la mejor opción parece ser:

test_set.py

a = range(1, 1000) 
b = range(2, 1002) 
list(set(a).difference(set(b)))