Ensembles Python vs listes

En Python, quelle structure de données est la plus efficace / rapide? En supposant que l'ordre n'est pas important pour moi et que je vérifierais de toute façon les doublons, est-ce qu'un ensemble Python est plus lent qu'une liste Python?

Cela dépend de ce que vous comptez en faire.

Les ensembles sont beaucoup plus rapides lorsqu'il s'agit de déterminer si un objet est présent dans l'ensemble (comme dans x in s), mais sont plus lents que les listes lorsqu'il s'agit d'itérer leur contenu.

Vous pouvez utiliser le module timeit pour voir ce qui est le plus rapide pour votre situation.

Les listes sont légèrement plus rapides que les ensembles lorsque vous souhaitez simplement parcourir les valeurs.

Les ensembles, cependant, sont beaucoup plus rapides que les listes si vous souhaitez vérifier si un élément y est contenu. Cependant, ils ne peuvent contenir que des éléments uniques.

Il s'avère que les tuples fonctionnent presque exactement de la même manière que les listes, à l'exception de leur immuabilité.

Itérer

>>> 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

Déterminer si un objet est présent

>>> 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

Liste des performances:

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

Définir les performances:

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

Vous voudrez peut-être considérer les tuples car ils sont similaires aux listes mais ne peuvent pas être modifiés. Ils prennent un peu moins de mémoire et sont plus rapides d'accès. Elles ne sont pas aussi flexibles mais sont plus efficaces que les listes. Leur utilisation normale est de servir de clés de dictionnaire.

Les ensembles sont également des structures de séquence, mais avec deux différences par rapport aux listes et aux tuples. Bien que les ensembles aient un ordre, cet ordre est arbitraire et n'est pas sous le contrôle du programmeur. La deuxième différence est que les éléments d'un ensemble doivent être uniques.

setpar définition. [ python | wiki ].

>>> x = set([1, 1, 2, 2, 3, 3])
>>> x
{1, 2, 3}

Setgagne en raison de vérifications quasi instantanées `` contient '': https://en.wikipedia.org/wiki/Hash_table

Implémentation de liste : généralement un tableau, de bas niveau proche du métal, bon pour l'itération et l'accès aléatoire par index d'élément.

Définir l' implémentation: https://en.wikipedia.org/wiki/Hash_table , il n'itère pas sur une liste, mais trouve l'élément en calculant un hachage à partir de la clé, donc cela dépend de la nature des éléments clés et du hachage fonction. Similaire à ce qui est utilisé pour dict. Je suppose que cela listpourrait être plus rapide si vous avez très peu d'éléments (<5), plus le nombre d'éléments est grand, meilleure setsera la performance d'une vérification de contenu. Il est également rapide pour l'ajout et le retrait d'éléments. Gardez toujours à l'esprit que la construction d'un ensemble a un coût!

REMARQUE : si le listest déjà trié, la recherche de listpeut être assez rapide, mais dans les cas habituels, a setest plus rapide et plus simple pour les vérifications de contenu.

tl; dr

Les structures de données (DS) sont importantes car elles sont utilisées pour effectuer des opérations sur des données, ce qui implique essentiellement: prendre une entrée , la traiter et rendre la sortie .

Certaines structures de données sont plus utiles que d'autres dans certains cas particuliers. Par conséquent, il est tout à fait injuste de demander quelle (DS) est la plus efficace / la plus rapide. C'est comme demander quel outil est le plus efficace entre un couteau et une fourchette. Je veux dire, tout dépend de la situation.

Listes

Une liste est une séquence modifiable , généralement utilisée pour stocker des collections d'éléments homogènes .

Ensembles

Un objet set est une collection non ordonnée d'objets hachables distincts . Il est couramment utilisé pour tester l'appartenance, supprimer les doublons d'une séquence et calculer des opérations mathématiques telles que l'intersection, l'union, la différence et la différence symétrique.

Usage

D'après certaines réponses, il est clair qu'une liste est bien plus rapide qu'un ensemble lors de l'itération sur les valeurs. D'un autre côté, un ensemble est plus rapide qu'une liste lors de la vérification si un élément y est contenu. Par conséquent, la seule chose que vous puissiez dire est qu'une liste est meilleure qu'un ensemble pour certaines opérations particulières et vice-versa.

J'étais intéressé par les résultats lors de la vérification, avec CPython, si une valeur est l'un d'un petit nombre de littéraux. setgagne en Python 3 vs tuple, listet 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))

Production:

tuple
4.735646052286029
list
4.7308746771886945
set
3.5755991376936436
or
4.687681658193469

Pour 3 à 5 littéraux, setgagne toujours par une large marge et ordevient le plus lent.

En Python 2, setc'est toujours le plus lent. orest le plus rapide pour 2 à 3 littéraux tupleet listest plus rapide avec 4 littéraux ou plus. Je ne pouvais pas distinguer la vitesse de tuplevs list.

Lorsque les valeurs à tester étaient mises en cache dans une variable globale hors de la fonction, plutôt que de créer le littéral dans la boucle, setgagnait à chaque fois, même en Python 2.

Ces résultats s'appliquent à CPython 64 bits sur un Core i7.

Je recommanderais une implémentation Set où le cas d'utilisation est limité au référencement ou à la recherche d'existence et à l'implémentation Tuple où le cas d'utilisation vous oblige à effectuer une itération. Une liste est une implémentation de bas niveau et nécessite une surcharge de mémoire importante.

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)

Sortie après comparaison de 10 itérations pour les 3: comparaison

Les ensembles sont plus rapides, de plus vous obtenez plus de fonctions avec des ensembles, comme disons que vous avez deux ensembles:

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

On peut facilement joindre deux ensembles:

set3 = set1.union(set2)

Découvrez ce qui est commun aux deux:

set3 = set1.intersection(set2)

Découvrez ce qui est différent dans les deux:

set3 = set1.difference(set2)

Et beaucoup plus! Essayez-les, ils sont amusants! De plus, si vous devez travailler sur des valeurs différentes dans 2 listes ou des valeurs communes dans 2 listes, je préfère convertir vos listes en ensembles, et de nombreux programmeurs le font de cette manière. J'espère que cela vous aidera :-)