insertion de python vs append

J'ai écrit de base de python extraits de code à insérer des valeurs dans une liste, puis de l'inverser. Je trouve qu'il y a une énorme différence de vitesse d'exécution entre l'insert et l'ajout des méthodes.

Extrait 1:

L = []
for i in range(10**5):
 L.append(i)
L.reverse()

Temps d'exécution de cette :

real    0m0.070s
user    0m0.064s
sys         0m0.008s

Extrait 2:

l = []
for i in range(10**5):
 l.insert(0,i)

Temps d'exécution:

real    0m5.645s
user    0m5.516s
sys         0m0.020s

Je m'attendais à de l'extrait 2 pour effectuer beaucoup mieux que snippet1, puisque je suis en effectuant l'opération inverse directement par l'insertion, les numéros avant de. Mais le temps passé dit le contraire. Je n'arrive pas à comprendre pourquoi cette dernière méthode prend plus de temps à s'exécuter, même si la méthode semble plus élégant. Ce que quelqu'un a une explication à cela?

source d'informationauteur Rahul | 2011-10-15

python

15

Noter que vos résultats dépendent de la précision Python de mise en œuvre. disponible (et pypy) redimensionner automatiquement votre liste et surdimensionner de l'espace pour de futures ajoute et donc d'accélérer la append en outre.

En interne, les listes sont des morceaux de mémoire avec une taille constante (sur la tas). Parfois, vous avez de la chance et peut augmenter la taille de la partie, mais dans de nombreux cas, un objet sera déjà là. Par exemple, supposons que vous avez alloué un morceau de la taille 4 pour une liste [a,b,c,d]et quelque autre morceau de code attribué un morceau de taille 6 pour un dictionnaire:
```
Memory  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
       |a b c d| | dictionary |
```
Supposons que votre liste a les 4 éléments, et un autre est ajouté. Maintenant, vous pouvez simplement redimensionner la liste taille 5:
```
Memory  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
       |a b c d e| dictionary |
```
Cependant, que faites-vous si vous avez besoin d'un autre élément maintenant?

Bien, la seule chose que vous pouvez faire est d'acquérir un nouvel espace et de copier le contenu de la liste.
```
Memory 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
                | dictionary |a  b  c  d  e  f |
```
Noter que si vous achetez de l'espace en vrac (c'est le cas surdimensionnement de), vous aurez seulement besoin de redimensionner (et, éventuellement, la copie) de la liste chaque maintenant et puis.

En revanche, lorsque vous insérez à la position 0, on a toujours besoin de la copie de votre liste. Nous allons insérer x:
```
Memory  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
orig   |a b c d| |dictionary|
after  |x a b c d|dictionary|
```
Bien qu'il y ait assez d'espace pour ajouter x à la fin, nous avons dû nous déplacer (même pas de la copie, ce qui peut être moins coûteux en mémoire) toutes les autres valeurs.
30

Voici la réponse de Duncan Stand:

Une liste est implémentée par un tableau de pointeurs vers les objets qu'il
contient.

Chaque fois que vous appelez 'insert(0, indx)', tous les pointeurs déjà dans
la liste à être déplacé vers le haut une fois de position avant que la nouvelle peut être
inséré au début.

Lorsque vous appelez " append(indx)' les pointeurs n'ont plus à être copié si
il n'y a pas assez d'espace dans le bloc alloué pour la nouvelle
de l'élément. Si il y a de l'espace, puis il n'est pas nécessaire de copier l'existant
les éléments, il suffit de placer le nouvel élément à la fin et de mettre à jour la longueur
champ. Chaque fois qu'un nouveau bloc ne doivent être attribués qu'particulier
append sera pas plus rapide qu'un insert, mais un peu d'espace supplémentaire sera
alloués au cas où vous ne souhaitez prolonger la liste encore plus.

Si vous vous attendiez à insérer pour être plus rapide, peut-être que vous avez pensé que Python
utilisé une liste liée de mise en œuvre. Il ne fait pas cela, parce que dans
pratique (pour la plupart des applications) une liste en fonction de la mise en œuvre donne
de meilleures performances.

En fait, j'ai rien d'autre à ajouter.
5

Si vous avez besoin d'un discbased qui est aussi efficace en insérant au début, car elle est en ajoutant, alors vous devriez envisager un deque.

J'ai appris un truc pour insérer le x dans le début d'une liste Python de Poche":

l[:0] = [x]

Il doit être d'une certaine façon très similaire à l'.insert(0, x), mais quand j'essaie de comparer trois options: append(x), insert(0, x) et l[:0] = [x], la dernière option effectue un peu plus rapide que la seconde.

Voici le code de test et le résultat

import time
def test():
    n = 10**5


    t0 = time.time()
    l = []
    for i in xrange(n): l.append(i)
    t1 = time.time() - t0
    print 'appending: %.5f' % t1


    t0 = time.time()
    l = []
    for i in xrange(n): l.insert(0, i)
    t2 = time.time() - t0
    print 'insert to 0: %.5f' % t2

    t0 = time.time()
    l = []
    for i in xrange(n): l[:0] = [i]
    t3 = time.time() - t0
    print 'set slice: %.5f' % t3

    return t1, t2, t3


if __name__ == '__main__':
    t = [0] * 3
    ntimes = 10

    for _ in xrange(ntimes):
        ti = test()

        for i in xrange(3):
            t[i] += ti[i]

    t = [i/ntimes for i in t]
    print 'average time:', t

temps moyen

[0.011755657196044923, 4.1943151950836182, 3.3254094839096071]

Pourquoi il est environ 25% plus rapide que l'insert(0, x)? J'ai essayé d'intervertir le bloc de code de l'estimation de t1, t2, t3, mais le résultat est le même, donc il n'est pas sur la mise en cache de la liste.

Iciil indique que le réglage de tranche prend O(k + n)

-1

Méthode d'insertion de manière appropriée de mettre en place dans la File d'attente .
FIFO opération, s'insère sur la face de la liste.
ex :. éléments.insert(0 point)

Méthode Append de façon appropriée la mise en œuvre de la pile .
Ce PRINCIPE de fonctionnement, insère à la fin de la liste.
ex :. éléments.append(élément)

Lorsque nous sommes à l'aide de l'insertion de données thru méthode INSERT assurez-vous que tous les index sont re-séquencé.

Vous devez vous connecter pour publier un commentaire.