Conjuntos de Python vs Listas

187

No Python, qual estrutura de dados é mais eficiente / rápida? Supondo que essa ordem não seja importante para mim e eu estaria procurando duplicatas de qualquer maneira, um conjunto de Python é mais lento que uma lista de Python?

Mantas Vidutis
fonte

Respostas:

231

Depende do que você pretende fazer com isso.

Os conjuntos são significativamente mais rápidos quando se trata de determinar se um objeto está presente no conjunto (como em x in s), mas são mais lentos que as listas quando se trata de iterar sobre seu conteúdo.

Você pode usar o módulo timeit para ver qual é mais rápido para sua situação.

Michael Aaron Safyan
fonte
4
Para seu argumento: "Os conjuntos são significativamente mais rápidos", qual é a implementação subjacente que o torna mais rápido?
overexchange
As linguagens de script gostam de ocultar as implementações subjacentes, mas essa aparente simplicidade nem sempre é uma coisa boa, você precisa de algum conhecimento da 'estrutura de dados' ao projetar um software.
Christophe Roussy
4
O conjunto não é significativamente mais lento que a lista durante a iteração.
Omerfarukdogan 23/01
39
Conjuntos e listas têm iteração de tempo linear. Dizer que um é "mais lento" que o outro é equivocado e confundiu novos programadores que leram esta resposta.
habnabit
@habnabit, se você está dizendo que os dois têm iteração de tempo linear. Isso significa que eles têm o mesmo tempo de iteração? Qual é a diferença então?
Mohammed Noureldin
153

As listas são um pouco mais rápidas que as configurações quando você deseja iterar sobre os valores.

Os conjuntos, no entanto, são significativamente mais rápidos que as listas, se você deseja verificar se um item está contido nele. Eles podem conter apenas itens exclusivos.

Acontece que as tuplas funcionam quase exatamente da mesma maneira que as listas, exceto por sua imutabilidade.

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 se um 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
fonte
6
Descobri que (Inicializando conjunto -> 5.5300979614257812) (Inicializando lista -> 1.8846848011016846) (Inicializando tupla -> 1.8730108737945557) Itens de tamanho 10.000 no meu intel core i5 quad core com 12 GB de RAM. Isso deve ser levado em consideração também.
ThePracticalOne
4
Atualizei o código para remover a criação do objeto agora. A fase de configuração dos loops timeit é chamada apenas uma vez ( docs.python.org/2/library/timeit.html#timeit.Timer.timeit ).
Ellis Percival
7

Lista de desempenho:

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

Definir desempenho:

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

Você pode considerar as Tuplas , pois são semelhantes às listas, mas não podem ser modificadas. Eles ocupam um pouco menos de memória e são mais rápidos de acessar. Eles não são tão flexíveis, mas são mais eficientes que as listas. Seu uso normal é servir como chaves de dicionário.

Os conjuntos também são estruturas de sequência, mas com duas diferenças entre listas e tuplas. Embora os conjuntos tenham uma ordem, essa ordem é arbitrária e não está sob o controle do programador. A segunda diferença é que os elementos em um conjunto devem ser exclusivos.

setpor definição. [ python | wiki ].

>>> x = set([1, 1, 2, 2, 3, 3])
>>> x
{1, 2, 3}
user2601995
fonte
4
Primeiro, você deve atualizar para o setlink de tipo interno ( docs.python.org/2/library/stdtypes.html#set ) e não a setsbiblioteca descontinuada . Segundo, "Conjuntos também são estruturas de sequência", leia o seguinte no link de tipo interno: "Sendo uma coleção não ordenada, os conjuntos não registram a posição do elemento ou a ordem de inserção. Dessa forma, os conjuntos não suportam indexação, fatia ou outras comportamento de sequência ".
Seaux
7
rangenão é list. rangeé uma classe especial com __contains__método mágico personalizado .
Ryne Wang
@RyneWang isso é verdade, mas apenas para Python3. Em python2 gama retorna uma lista normal (é por isso que existe coisas horríveis como xrange)
Manoel Vilela
7

Setvitórias devido a verificações quase instantâneas 'contém': https://en.wikipedia.org/wiki/Hash_table

Implementação da lista : geralmente uma matriz, baixo nível próximo ao metal, bom para iteração e acesso aleatório pelo índice de elementos.

Defina a implementação: https://en.wikipedia.org/wiki/Hash_table , não itera em uma lista, mas localiza o elemento calculando um hash da chave, portanto depende da natureza dos elementos-chave e do hash função. Semelhante ao que é usado para dict. Eu suspeito que listpoderia ser mais rápido se você tiver muito poucos elementos (<5), quanto maior a contagem de elementos, melhor setserá o desempenho para uma verificação de contenção. Também é rápido para adição e remoção de elementos. Também tenha sempre em mente que construir um conjunto tem um custo!

NOTA : Se o listjá estiver classificado, a pesquisa no listpode ser bastante rápida, mas, nos casos habituais, a seté mais rápido e mais simples para as verificações.

Christophe Roussy
fonte
8
Perto do metal? O que isso significa no contexto do Python? Como uma lista está mais próxima do metal que um conjunto?
roganjosh
@roganjosh, o python ainda roda em uma máquina e algumas implementações como list como 'array' estão mais próximas do que o hardware é bom: stackoverflow.com/questions/176011/… , mas sempre depende do que você deseja alcançar. é bom saber um pouco sobre as implementações, não apenas as abstrações.
Christophe Roussy
2

tl; dr

As estruturas de dados (DS) são importantes porque são usadas para executar operações nos dados, o que basicamente implica: pegar alguma entrada , processá-la e devolver a saída .

Algumas estruturas de dados são mais úteis que outras em alguns casos específicos. Portanto, é bastante injusto perguntar qual (DS) é mais eficiente / rápido. É como perguntar qual ferramenta é mais eficiente entre uma faca e um garfo. Quero dizer, tudo depende da situação.

Listas

Uma lista é uma sequência mutável , normalmente usada para armazenar coleções de itens homogêneos .

Conjuntos

Um objeto definido é uma coleção não ordenada de objetos hash distintos . É comumente usado para testar a associação, remover duplicatas de uma sequência e calcular operações matemáticas como interseção, união, diferença e diferença simétrica.

Uso

De algumas das respostas, fica claro que uma lista é muito mais rápida que um conjunto ao iterar sobre os valores. Por outro lado, um conjunto é mais rápido que uma lista ao verificar se um item está contido nele. Portanto, a única coisa que você pode dizer é que uma lista é melhor que um conjunto para algumas operações específicas e vice-versa.

lmiguelvargasf
fonte
2

Eu estava interessado nos resultados ao verificar, com CPython, se um valor é um dentre um pequeno número de literais. setvence em Python 3 vs tuple, liste 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))

Resultado:

tuple
4.735646052286029
list
4.7308746771886945
set
3.5755991376936436
or
4.687681658193469

Para 3 a 5 literais, setainda vence por uma ampla margem e orse torna o mais lento.

No Python 2, seté sempre o mais lento. oré o mais rápido para 2 a 3 literais tuplee listé mais rápido com 4 ou mais literais. Eu não conseguia distinguir a velocidade do tuplecontra list.

Quando os valores a serem testados foram armazenados em cache em uma variável global fora da função, em vez de criar o literal dentro do loop, setsempre foram ganhos, mesmo no Python 2.

Esses resultados se aplicam ao CPython de 64 bits em um Core i7.

Pedro Gimeno
fonte
0

Eu recomendaria uma implementação de conjunto em que o caso de uso seja o limite para referenciar ou procurar a existência e a implementação de tupla em que o caso de uso exige que você execute a iteração. Uma lista é uma implementação de baixo nível e requer sobrecarga significativa de memória.


fonte
1
De fato, a distinção adequada entre quando usar Conjuntos e quando usar Tupla é de extrema importância. Eu não ficaria preocupado com as sobrecargas de memória envolvidas, pegadas, a menos que esteja criando uma API de nível 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)

Saída após comparar 10 iterações para todos os 3: Comparação

Harshal SG
fonte
0

Os conjuntos são mais rápidos; além disso, você obtém mais funções com conjuntos, como digamos que você tenha dois conjuntos:

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

Podemos facilmente juntar dois conjuntos:

set3 = set1.union(set2)

Descubra o que é comum em ambos:

set3 = set1.intersection(set2)

Descubra o que é diferente em ambos:

set3 = set1.difference(set2)

E muito mais! Basta experimentá-los, eles são divertidos! Além disso, se você precisar trabalhar com os diferentes valores dentro de 2 listas ou valores comuns dentro de 2 listas, eu prefiro converter suas listas em conjuntos, e muitos programadores fazem dessa maneira. Espero que ajude você :-)

Shakhyar Gogoi
fonte