Python Sets vs Listas

187

En Python, ¿qué estructura de datos es más eficiente / rápida? Suponiendo que el orden no es importante para mí y estaría buscando duplicados de todos modos, ¿es un Python más lento que una lista de Python?

Mantas Vidutis
fuente

Respuestas:

231

Depende de lo que pretendas hacer con él.

Los conjuntos son significativamente más rápidos cuando se trata de determinar si un objeto está presente en el conjunto (como en x in s), pero son más lentos que las listas cuando se trata de iterar sobre su contenido.

Puede usar el módulo timeit para ver cuál es más rápido para su situación.

Michael Aaron Safyan
fuente
44
Para su punto: "Los conjuntos son significativamente más rápidos", ¿cuál es la implementación subyacente que lo hace más rápido?
sobre
A los lenguajes de secuencias de comandos les gusta ocultar las implementaciones subyacentes, pero esta aparente simplicidad no siempre es algo bueno, es necesario tener un poco de conciencia de 'estructura de datos' cuando diseñas una pieza de software.
Christophe Roussy el
44
El conjunto no es significativamente más lento que la lista mientras se itera.
omerfarukdogan
39
Los conjuntos y las listas tienen iteración de tiempo lineal. Decir que uno es "más lento" que el otro está equivocado y ha confundido a los nuevos programadores que leen esta respuesta.
habnabit
@habnabit si está diciendo que ambos tienen iteración de tiempo lineal. ¿Esto significa que tienen el mismo tiempo de iteración? ¿Cuál es la diferencia entonces?
Mohammed Noureldin
153

Las listas son un poco más rápidas que los conjuntos cuando solo desea iterar sobre los valores.

Sin embargo, los conjuntos son significativamente más rápidos que las listas si desea verificar si un elemento está contenido en él. Sin embargo, solo pueden contener elementos únicos.

Resulta que las tuplas funcionan casi exactamente de la misma manera que las listas, excepto por su inmutabilidad.

Iterando

>>> def iter_test(iterable):
...     for i in iterable:
...         pass
...
>>> from timeit import timeit
>>> timeit(
...     "iter_test(iterable)",
...     setup="from __main__ import iter_test; iterable = set(range(10000))",
...     number=100000)
12.666952133178711
>>> timeit(
...     "iter_test(iterable)",
...     setup="from __main__ import iter_test; iterable = list(range(10000))",
...     number=100000)
9.917098999023438
>>> timeit(
...     "iter_test(iterable)",
...     setup="from __main__ import iter_test; iterable = tuple(range(10000))",
...     number=100000)
9.865639209747314

Determinar si un objeto está presente

>>> def in_test(iterable):
...     for i in range(1000):
...         if i in iterable:
...             pass
...
>>> from timeit import timeit
>>> timeit(
...     "in_test(iterable)",
...     setup="from __main__ import in_test; iterable = set(range(1000))",
...     number=10000)
0.5591847896575928
>>> timeit(
...     "in_test(iterable)",
...     setup="from __main__ import in_test; iterable = list(range(1000))",
...     number=10000)
50.18339991569519
>>> timeit(
...     "in_test(iterable)",
...     setup="from __main__ import in_test; iterable = tuple(range(1000))",
...     number=10000)
51.597304821014404
Ellis Percival
fuente
66
He encontrado que (Conjunto de inicialización -> 5.5300979614257812) (Lista de inicialización -> 1.8846848011016846) (Tupla de inicialización -> 1.8730108737945557) Elementos de tamaño 10,000 en mi Intel Core i5 quad core con 12GB RAM. Esto también debe tenerse en cuenta.
ThePracticalOne
44
He actualizado el código para eliminar la creación del objeto ahora. La fase de configuración de los bucles timeit solo se llama una vez ( docs.python.org/2/library/timeit.html#timeit.Timer.timeit ).
Ellis Percival
7

Lista de rendimiento:

>>> import timeit
>>> timeit.timeit(stmt='10**6 in a', setup='a = range(10**6)', number=100000)
0.008128150348026608

Establecer rendimiento:

>>> timeit.timeit(stmt='10**6 in a', setup='a = set(range(10**6))', number=100000)
0.005674857488571661

Es posible que desee considerar las tuplas, ya que son similares a las listas, pero no se pueden modificar. Ocupan un poco menos de memoria y son más rápidos de acceder. No son tan flexibles pero son más eficientes que las listas. Su uso normal es servir como teclas de diccionario.

Los conjuntos también son estructuras de secuencia pero con dos diferencias de listas y tuplas. Aunque los conjuntos tienen un orden, ese orden es arbitrario y no está bajo el control del programador. La segunda diferencia es que los elementos en un conjunto deben ser únicos.

setpor definición. [ pitón | wiki ].

>>> x = set([1, 1, 2, 2, 3, 3])
>>> x
{1, 2, 3}
user2601995
fuente
44
En primer lugar, debe actualizar el setenlace de tipo incorporado ( docs.python.org/2/library/stdtypes.html#set ), no la setsbiblioteca en desuso . Segundo, "Los conjuntos también son estructuras de secuencia", lea lo siguiente desde el enlace de tipo incorporado: "Al ser una colección desordenada, los conjuntos no registran la posición del elemento ni el orden de inserción. Por consiguiente, los conjuntos no admiten indexación, segmentación u otros comportamiento similar a la secuencia ".
Seaux
77
rangeno es list. rangees una clase especial con __contains__método mágico personalizado .
Ryne Wang
@RyneWang esto es cierto, pero solo para Python3. En Python2 el rango devuelve una lista normal (por eso existen cosas horribles como xrange)
Manoel Vilela
7

Setgana debido a comprobaciones 'contiene' casi instantáneas: https://en.wikipedia.org/wiki/Hash_table

Implementación de la lista : generalmente una matriz, de bajo nivel cerca del metal, buena para iteración y acceso aleatorio por índice de elemento.

Establecer implementación: https://en.wikipedia.org/wiki/Hash_table , no itera en una lista, pero encuentra el elemento calculando un hash de la clave, por lo que depende de la naturaleza de los elementos clave y el hash función. Similar a lo que se usa para dict. Sospecho que listpodría ser más rápido si tiene muy pocos elementos (<5), cuanto mayor sea el recuento de elementos, mejor setfuncionará para una verificación de contenido. También es rápido para la adición y eliminación de elementos. ¡También ten en cuenta que construir un set tiene un costo!

NOTA : Si listya está ordenado, la búsqueda listpodría ser bastante rápida, pero en los casos habituales a setes más rápido y sencillo para verificaciones de contenido.

Christophe Roussy
fuente
8
¿Cerca del metal? ¿Qué significa eso en el contexto de Python? ¿Cómo es una lista más cercana al metal que un conjunto?
roganjosh
@roganjosh, python todavía se ejecuta en una máquina y algunas implementaciones como list como 'array' están más cerca de lo que el hardware es bueno en: stackoverflow.com/questions/176011/… , pero siempre depende de lo que quieras lograr, Es bueno saber un poco sobre las implementaciones, no solo las abstracciones.
Christophe Roussy
2

tl; dr

Las estructuras de datos (DS) son importantes porque se utilizan para realizar operaciones en los datos, lo que básicamente implica: tomar alguna entrada , procesarla y devolver la salida .

Algunas estructuras de datos son más útiles que otras en algunos casos particulares. Por lo tanto, es bastante injusto preguntar qué (DS) es más eficiente / rápido. Es como preguntar qué herramienta es más eficiente entre un cuchillo y un tenedor. Quiero decir que todo depende de la situación.

Liza

Una lista es una secuencia mutable , que generalmente se usa para almacenar colecciones de artículos homogéneos .

Conjuntos

Un objeto conjunto es una colección desordenada de objetos hashables distintos . Se usa comúnmente para probar la membresía, eliminar duplicados de una secuencia y calcular operaciones matemáticas como intersección, unión, diferencia y diferencia simétrica.

Uso

De algunas de las respuestas, está claro que una lista es bastante más rápida que un conjunto al iterar sobre los valores. Por otro lado, un conjunto es más rápido que una lista cuando se verifica si un elemento está contenido dentro de él. Por lo tanto, lo único que puede decir es que una lista es mejor que un conjunto para algunas operaciones particulares y viceversa.

lmiguelvargasf
fuente
2

Estaba interesado en los resultados al verificar, con CPython, si un valor es uno de un pequeño número de literales. setgana en Python 3 vs tuple, listy or:

from timeit import timeit

def in_test1():
  for i in range(1000):
    if i in (314, 628):
      pass

def in_test2():
  for i in range(1000):
    if i in [314, 628]:
      pass

def in_test3():
  for i in range(1000):
    if i in {314, 628}:
      pass

def in_test4():
  for i in range(1000):
    if i == 314 or i == 628:
      pass

print("tuple")
print(timeit("in_test1()", setup="from __main__ import in_test1", number=100000))
print("list")
print(timeit("in_test2()", setup="from __main__ import in_test2", number=100000))
print("set")
print(timeit("in_test3()", setup="from __main__ import in_test3", number=100000))
print("or")
print(timeit("in_test4()", setup="from __main__ import in_test4", number=100000))

Salida:

tuple
4.735646052286029
list
4.7308746771886945
set
3.5755991376936436
or
4.687681658193469

Para 3 a 5 literales, setaún gana por un amplio margen, y se orconvierte en el más lento.

En Python 2, setsiempre es el más lento. ores el más rápido para 2 a 3 literales, tupley listes más rápido con 4 o más literales. No podía distinguir la velocidad del tuplefrente list.

Cuando los valores a probar se almacenaron en caché en una variable global fuera de la función, en lugar de crear el literal dentro del bucle, setganó cada vez, incluso en Python 2.

Estos resultados se aplican a CPython de 64 bits en un Core i7.

Pedro Gimeno
fuente
0

Recomendaría una implementación de Set donde el caso de uso se limita a hacer referencia o buscar la existencia y la implementación de Tuple donde el caso de uso requiere que realice la iteración. Una lista es una implementación de bajo nivel y requiere una sobrecarga de memoria significativa.


fuente
1
De hecho, la distinción adecuada entre cuándo usar Conjuntos y cuándo usar Tuple es de suma importancia. No estaría preocupado por los gastos generales de memoria involucrados, huellas a menos que esté escribiendo una API de nivel inferior.
0
from datetime import datetime
listA = range(10000000)
setA = set(listA)
tupA = tuple(listA)
#Source Code

def calc(data, type):
start = datetime.now()
if data in type:
print ""
end = datetime.now()
print end-start

calc(9999, listA)
calc(9999, tupA)
calc(9999, setA)

Salida después de comparar 10 iteraciones para las 3: Comparación

Harshal SG
fuente
0

Los conjuntos son más rápidos, además obtienes más funciones con conjuntos, como digamos que tienes dos conjuntos:

set1 = {"Harry Potter", "James Bond", "Iron Man"}
set2 = {"Captain America", "Black Widow", "Hulk", "Harry Potter", "James Bond"}

Podemos unir fácilmente dos conjuntos:

set3 = set1.union(set2)

Descubra lo que es común en ambos:

set3 = set1.intersection(set2)

Descubre qué es diferente en ambos:

set3 = set1.difference(set2)

¡Y mucho más! ¡Pruébalos, son divertidos! Además, si tiene que trabajar en los diferentes valores dentro de 2 listas o valores comunes dentro de 2 listas, prefiero convertir sus listas en conjuntos, y muchos programadores lo hacen de esa manera. Espero que te ayude :-)

Shakhyar Gogoi
fuente