Quelle est la durée de la complexité de la liste python fonctions?

J'ai écrit 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)

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

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

J'avais supposé que l'indice de l'accès des listes a été O(1), mais a été surpris de constater que pour les grandes listes cela a été nettement plus lente que ce que j'attendais.

Ma question, alors, est de savoir comment python, les listes sont mises en œuvre, et quelle est la durée de la complexité de la suite

Indexation: list[x]
Pans de la fin: list.pop()
Popping depuis le début: list.pop(0)
L'élargissement de la liste: list.append(x)

Pour le crédit supplémentaire, l'épissage ou arbitraire de la pop.

InformationsquelleAutor Marquis Wang | 2009-06-17

complexity-theory python

35

il est une très détaillé tableau de python wiki qui répond à votre question.

Cependant, dans votre exemple, vous devez utiliser enumerate pour obtenir un indice d'un objet iterable l'intérieur d'une boucle. comme:
```
for i, item in enumerate(some_seq):
    bar(item, i)
```
- Pardonnez mon ignorance, mais où est la complexité de pop() sur cette page?
- pop() avec n l'indice de O(1), avec index, par exemple, le premier sur la liste, il est O(n). puisque vous avez besoin pour obtenir le point O(1), puis le supprimer. Ce dernier prend O(n) dans le temps afin d'organiser tous les autres éléments de la liste. Plus à ce sujet ici: ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt
InformationsquelleAutor SilentGhost
8

La réponse est "undefined". Le langage Python n'est pas de définir l'implémentation sous-jacente. Voici quelques liens vers une liste de diffusion fil, vous pourriez être intéressé par.
- Il est vrai que Python, pour les listes
  été mis en œuvre comme contigus
  vecteurs dans les implémentations de C
  Python jusqu'à présent.
- Je ne dis pas que le O()
  les comportements de ces choses devraient être
  gardé secret ou quoi que ce soit. Mais vous
  besoin de les interpréter dans le contexte
  de façon Python fonctionne généralement.
Aussi, le plus Pythonic l'écriture de vos boucle serait celui-ci:
```
def foo(some_list):
   for item in some_list:
       bar(item)
```
- Oups, je suis consciente que ma méthode était un peu moins que Pythonic. Pour ma boucle, j'avais besoin de l'élément, ainsi que l'index. Est-il une bonne façon de le faire? (L'édition de ma question)
- utilisation - pour i, point à énumérer(some_lits): ...
InformationsquelleAutor anthony
6

Listes sont en effet en O(1) à l'indice - ils sont mis en œuvre comme un vecteur proportionnel surutilisation, afin d'effectuer beaucoup comme vous le souhaitez. Probablement la raison vous avez été de trouver ce code plus lentement que prévu, c'est l'appel à "range(0, len(some_list))".

range() crée une nouvelle liste de la taille spécifiée, donc si some_list a 1 000 000 d'articles, vous allez créer un million de nouveaux élément de la liste à l'avant. Ce changement de comportement dans python3 (la plage est un itérateur), à qui l'python2 équivalent est xrange, ou encore mieux pour votre cas, énumérer

InformationsquelleAutor Brian
3

Ne peux pas commenter, de sorte que

si vous avez besoin d'indice et la valeur puis utilisez les énumère:
```
for idx, item in enumerate(range(10, 100, 10)):
    print idx, item
```
InformationsquelleAutor Maxim Kim
1

Liste Python en fait rien mais les tableaux. Ainsi,

indexation prend O(1)

pour la pop et ajouter de nouveau, il devrait être en O(1) selon les docs

Découvrez lien suivant pour les détails:

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

InformationsquelleAutor codersofthedark

Vous devez vous connecter pour publier un commentaire.