Quelle est la complexité d'exécution des fonctions de liste Python?

je en train d'écrire une fonction de python qui avait l'air quelque chose comme çaQuelle est la complexité d'exécution des fonctions de liste Python?

def foo(some_list): 
    for i in range(0, len(some_list)): 
     bar(some_list[i], i)

de sorte qu'il a été appelé avec

x = [0, 1, 2, 3, ... ] 
foo(x)

J'avais supposé que l'accès à l'index des listes était O(1), mais a été surpris de constater que pour les grandes listes, c'était beaucoup plus lent que prévu.

Ma question est donc comment les listes Python sont mises en œuvre, et quelle est la complexité d'exécution des opérations suivantes

indexation: list[x]
Popping de la fin: list.pop()
Popping de la Début: list.pop(0)
Extension de la liste: list.append(x)

Pour un crédit supplémentaire, un épissage ou des pops arbitraires.

Source

2009-06-17 Marquis Wang

il y a a very detailed table on python wiki qui répond à votre question.

Toutefois, dans votre exemple particulier, vous devez utiliser enumerate pour obtenir un index d'un itérable dans une boucle. comme ceci:

for i, item in enumerate(some_seq): 
    bar(item, i)

Source

2009-06-17 07:57:35 SilentGhost

Pardonnez mon ignorance, mais où est la complexité de 'pop()' sur cette page? – Zaz

@Zaz, pop() sans index est O (1), avec index, par ex. le premier sur la liste, c'est O (n). puisque vous devez obtenir l'élément O (1), puis le supprimer. Ce dernier prend le temps O (n) pour organiser tous les autres éléments de la liste. Plus sur cela ici: https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt –

La réponse est "indéfini". Le langage Python ne définit pas l'implémentation sous-jacente. Voici quelques liens vers une liste de diffusion fil que vous pourriez être intéressé par

De plus, la façon plus Pythonic d'écrire votre boucle serait-ce.:

def foo(some_list): 
    for item in some_list: 
     bar(item)

Source

2009-06-17 07:37:59 anthony

Oups, je suis conscient que ma méthode était un peu moins que Pythonic. Pour ma boucle, j'avais besoin de l'item, ainsi que de l'index. Y a-t-il un bon moyen de le faire? (Éditer ma question) –

use- for i, item dans enumerate (some_lits): ... –

Impossible de faire un commentaire, donc

si vous avez besoin index et la valeur puis utilisez enumerate:

for idx, item in enumerate(range(10, 100, 10)): 
    print idx, item

Source

2009-06-17 07:53:01

listes sont en effet O (1) à l'index - ils sont mis en œuvre en tant que vecteur avec surutilisation proportionnel, donc effectuer autant que vous attendez. La raison probable pour laquelle vous avez trouvé ce code plus lent que prévu est l'appel à "range(0, len(some_list))".

range() crée une nouvelle liste de la taille spécifiée, donc si some_list contient 1 000 000 d'éléments, vous créez une nouvelle liste d'éléments million à l'avant. Ce comportement change dans python3 (range est un itérateur), auquel l'équivalent python2 est xrange, ou mieux encore pour votre cas, enumerate

Source

2009-06-17 08:49:57 Brian