Quelle est la complexité temporelle et la complexité spatiale de array [:: - 1]

Lorsque inverser une liste en Python, j'utilise habituellement le tableau [:: - 1] pour inverser et je sais qu'un moyen plus courant pourrait être deux côtés de la liste. Mais je ne suis pas sûr de la différence entre ces deux solutions telles que la complexité temporelle et la complexité de l'espace.Quelle est la complexité temporelle et la complexité spatiale de array [:: - 1]

Code pour ces deux méthodes suivantes:

def reverse(array): 
    array[:] = array[::-1] 


def reverse(array): 
    start, end = 0, len(array)-1 
    while start < end: 
     array[start], array[end] = array[end], array[start] 
     start += 1 
     end -= 1

Source

2017-07-26 JoshuaW1990

Hors sujet mais vous pouvez utiliser les fonctions intégrées ['reverse()'] (https://docs.python.org/2/library/functions.html#reversed) plutôt que '[:: - 1 ] 'itérer sur la liste inversée. –

Vous pouvez tester quelle méthode est la plus rapide en utilisant ['timeit'] (https://docs.python.org/2/library/timeit.html) et vous pouvez utiliser [' dis'] (https: // docs. python.org/2/library/dis.html) pour voir le bytecode de chaque fonction que vous avez créée. En règle générale, utilisez 'array [:: - 1]' ou 'list (inverse (array))' pour inverser le tableau plutôt que la fonction personnalisée. Parce que les fonctions intégrées sont implémentées en utilisant 'CPython' et donc très optimisées. Vous pouvez trouver les sources ici: [fonction intégrée github CPython] (https://github.com/python/cpython) –

Merci. Peut-être que je ne l'ai pas expliqué très clairement. Oui, je peux utiliser la fonction 'reverse' pour inverser la liste, mais parfois j'ai aussi besoin d'inverser quelque chose comme une chaîne et la fonction' reverse' ne fonctionne pas pour la chaîne. Dans cette situation, j'utilise habituellement 'string [:: - 1]', mais je ne sais pas comment cela fonctionne et ses performances. – JoshuaW1990

En python C, un tableau en supposant une liste, l'expression array[::-1] déclenche l'algorithme suivant trouvé en fonction list_subscript() dans le fichier source listobject.c

 result = PyList_New(slicelength); 
     if (!result) return NULL; 

     src = self->ob_item; 
     dest = ((PyListObject *)result)->ob_item; 
     for (cur = start, i = 0; i < slicelength; 
      cur += (size_t)step, i++) { 
      it = src[cur]; 
      Py_INCREF(it); 
      dest[i] = it; 
     }

La complexité temporelle et spatiale de cette partie du code est O(n) où n est la longueur de la liste. Bien sûr, il n'y a pas de surprise ici.

Votre fonction reverse() a également O(n) complexité de temps, la différence est qu'elle n'utilise pas une liste temporaire.

La fonction C intégrée est beaucoup plus rapide que la pure boucle python (environ 10 fois sur mon ordinateur pour une liste de 100 éléments).

Source

2017-07-26 15:00:48 Gribouillis

Quelle est la complexité temporelle et la complexité spatiale de array [:: - 1]

Répondre

Questions connexes