En python, quand je convertis mon ensemble en liste, quelle est la complexité algorithmique d'une telle tâche? S'agit-il simplement de transtyper la collection ou doit-il copier des éléments dans une structure de données différente? Que se passe-t-il?
J'adorerais apprendre que la complexité était constante, comme tant de choses en Python.
3 Réponses :
Vous pouvez facilement voir cela avec un test simple:
import matplotlib.pyplot as plt
x = list(range(10, 20000, 20))
y = []
for n in x:
s = set(range(n))
res = %timeit -r2 -n2 -q -o list(s)
y.append(res.best)
plt.plot(x, y)
Ce qui montre clairement une relation linéaire - modulo certains bruit.
(MODIFIE car la première version comparait quelque chose de différent).
Alors, que se passe-t-il à 1000 et 6000? Je comprends que la forme générale indique O (N), je suis juste curieux de savoir quel détail de mise en œuvre est montré par ces étapes.
Je pense que les sauts sont dus au fait que la mise en œuvre de la liste alloue un espace supplémentaire à la croissance, mais doit réallouer la liste lorsqu'elle atteint la limite.
Ce n'est pas une façon de mesurer la complexité temporelle d'une opération; la complexité en temps est théorique, et elle ne s'applique que pour n "suffisamment grand", où 20 000 peuvent ne pas être "suffisamment grand". Ce graphique donne des preuves de ce que la complexité temporelle pourrait être, mais vous ne pouvez pas mesurer la complexité temporelle d'un algorithme en l'exécutant réellement et en mesurant avec une minuterie.
@ kaya3 Bien sûr. Je trouve toujours cette approche heuristique utile pour comprendre à quel type de comportement nous devons nous attendre dans les applications du monde réel. D'ailleurs, la question est plutôt pratique. Il existe plusieurs approches pour définir un conteneur comme set () et un comme list () qui peuvent varier dans l'implémentation future, et cette heuristique simple donnera des informations sans connaître les éléments internes.
@AndrewJaffe C'est la taille interne de l'ensemble, qui quadruple à ces points.
@AndrewJaffe Voir le graphique de temps par rapport à la taille définie .
La complexité est linéaire car toutes les références sont copiées dans le nouveau conteneur. Mais seulement des références et sont et non des objets - cela peut avoir de l'importance pour les gros objets.
La complexité temporelle dans la plupart des cas sera O ( n ) où n est la taille de l'ensemble, car:
Cependant, il y a une mise en garde à ceci, qui est que les ensembles de Python ont des tailles de tableau sous-jacentes basées sur la plus grande taille de l'objet d'ensemble, pas nécessairement basée sur sa taille actuelle; cela est dû au fait que le tableau sous-jacent n'est pas réaffecté à une taille plus petite lorsque des éléments sont supprimés de l'ensemble. Si un ensemble est petit mais était beaucoup plus grand, l'itération peut être plus lente que O ( n ).