éléments - tableau python




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

J'écrivais une fonction python qui ressemblait à 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'index d'accès aux listes était O(1) , mais j'ai été surpris de constater que cela était beaucoup plus lent pour les grandes listes que ce à quoi je m'attendais.

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: list[x]
  • Popping depuis la fin: list.pop()
  • Popping depuis le début: list.pop(0)
  • Extension de la liste: list.append(x)

Pour un crédit supplémentaire, des épissures ou des bruits arbitraires.


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

Cependant, dans votre exemple particulier, vous devriez utiliser enumerate pour obtenir un index d'un itérable dans une boucle. ainsi:

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

Je ne peux pas encore commenter, alors

si vous avez besoin d’index et de value, utilisez enumerate:

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

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 pourraient vous intéresser.

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)

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 d'éléments, vous créerez une nouvelle liste d'un million d'éléments immédiatement. Ce comportement change dans python3 (la plage est un itérateur), pour lequel l'équivalent xrange est xrange , ou même mieux pour votre cas, enumerate





complexity-theory