J'ai testé deux manières différentes d'inverser une liste dans Python. Fait intéressant, la 2e méthode qui insère la valeur au premier élément est presque plus lente que la première. P> 20.4851300716
73.5116429329
3 Réponses :
La complexité temporelle de ces méthodes est documentée ici .
Je cite:
interne, une liste est représentée comme une matrice; Les coûts les plus importants proviennent de grandir au-delà de la taille de l'allocation actuelle (parce que tout doit bouger) ou de l'insertion ou de la suppression quelque part près du début (parce que tout après cela doit se déplacer).
maintenant, retour à votre code, nous pouvons voir que Insérer est un fonctionnement O (n) car il nécessite tous les éléments à ou après que la position d'insertion soit modifiée par une. Ajoutez , d'autre part, est généralement O (1) (et O (n) dans le pire des cas, quand plus d'espace doit être alloué). Cela explique la différence de temps substantielle.
rev1 () est une implémentation o (n) tandis que rev2 () est en fait O (n 2 ) , il est donc logique que rev2 () sera beaucoup plus lent.
Dans Python, les listes sont implémentées comme des tableaux. Si vous appendez un élément à un tableau, l'espace réservé pour un tableau est simplement élargi. Si vous préparez un élément, tous les éléments sont déplacés par 1 et cela coûte très cher.
Vous pouvez confirmer cela en lisant des listes Python en ligne. Python implémente une liste sous forme de tableau, où la taille de la matrice est généralement généralement supérieure à la taille de votre liste actuelle. Les éléments inutilisés sont à la fin de la matrice et représentent de nouveaux éléments pouvant être ajoutés à la fin de la liste, et non le début. Python utilise une approche de coûts amortise classique de sorte que, en moyenne, l'adjuvtion à la fin de la liste prend o (1) heure si vous faites un tas d'appouens, bien que parfois une seule annexe entraînera une nouvelle matrice de plus grande taille. doit être créé et toutes les données copiées sur la nouvelle matrice. D'autre part, si vous insérez toujours à l'avant de la liste, alors dans la matrice sous-jacente, tous les éléments doivent être déplacés sur un index pour faire de la place pour le nouvel élément au début de la matrice. Donc, pour résumer, si vous créez une liste en faisant n insertions, le temps d'exécution total sera O (n) si vous annoncez toujours de nouveaux éléments à la fin de la liste, et ce sera O (n ^ 2) si Vous appendez toujours à l'avant de la liste.
Utilisez une delle si vous avez besoin d'une liste liée comme DataStructure: docs.python .org / 2 / bibliothèque / collections.html # Collections.deque