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

Question

J'écrivais une fonction python qui ressemblait à quelque chose comme ceci

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

pour qu'il soit appelé avec

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

J'avais supposé que l'accès par index aux listes était O (1) , mais j'ai été surpris de constater que cela était nettement plus lent que prévu pour les grandes listes.

Ma question est donc de savoir comment les listes python sont implémentées et quelle est la complexité d'exécution des éléments suivants

• Indexation: liste [x]
• À partir de la fin: list.pop ()
• À partir du début: list.pop (0)
• Extension de la liste: list.append (x)

Pour obtenir un crédit supplémentaire, des coupures épissées ou arbitraires.

Answer 1

il existe un tableau très détaillé sur le wiki python qui répond à votre question.

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

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

Answer 2

La réponse est "non définie". Le langage Python ne définit pas l'implémentation sous-jacente. Voici quelques liens vers un fil de liste de diffusion qui pourrait vous intéresser.

• Il est vrai que les listes de Python ont été mis en œuvre comme contiguë vecteurs dans les implémentations C de Python jusqu'à présent.

• Je ne dis pas que le O ( ) les comportements de ces choses devraient être gardé un secret ou quoi que ce soit. Mais toi besoin de les interpréter dans le contexte de la manière dont Python fonctionne en général.

En outre, la manière la plus pythonique d’écrire votre boucle serait la suivante:

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

Answer 3

Les listes sont en effet des O (1) à indexer - elles sont implémentées comme un vecteur avec une surallocation proportionnelle, alors effectuez les tâches 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. Ainsi, si some_list contient 1 000 000 éléments, vous créerez une nouvelle liste d'un million d'éléments immédiatement. Ce comportement change dans python3 (range est un itérateur), auquel l'équivalent python2 est xrange énumérer

Answer 4

Je ne peux pas encore commenter, donc

si vous avez besoin d'un index et d'une valeur, utilisez enumerate:

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

Answer 5

La liste Python ne contient en réalité que des tableaux. Ainsi,

l'indexation prend O (1)

pour pop et ajouter à nouveau il devrait être O (1) selon les docs

Consultez le lien suivant pour plus de détails:

http://dustycodes.wordpress.com / 2012/03/31 / pythons-data-structures-complex-analysis /