Pourquoi la copie d'une liste aléatoire est-elle beaucoup plus lente?

Copier une range(10**6)liste aléatoire dix fois me prend environ 0,18 seconde: (ce sont cinq essais)

0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451

La copie de la liste non mélangée dix fois me prend environ 0,05 seconde:

0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184

Voici mon code de test:

from timeit import timeit
import random

a = range(10**6)
random.shuffle(a)    # Remove this for the second test.
a = list(a)          # Just an attempt to "normalize" the list.
for _ in range(5):
    print timeit(lambda: list(a), number=10)

J'ai aussi essayé de copier avec a[:], les résultats étaient similaires (c'est-à-dire une grande différence de vitesse)

Pourquoi la grande différence de vitesse? Je connais et comprends la différence de vitesse dans le célèbre Pourquoi est-il plus rapide de traiter un tableau trié qu'un tableau non trié? exemple, mais ici mon traitement n'a pas de décisions. C'est juste copier aveuglément les références à l'intérieur de la liste, non?

J'utilise Python 2.7.12 sur Windows 10.

Edit: J'ai également essayé Python 3.5.2 maintenant, les résultats étaient presque les mêmes (mélangés de manière cohérente autour de 0,17 seconde, non mélangés de manière cohérente autour de 0,05 seconde). Voici le code pour cela:

a = list(range(10**6))
random.shuffle(a)
a = list(a)
for _ in range(5):
    print(timeit(lambda: list(a), number=10))

Le bit intéressant est que cela dépend de l'ordre dans lequel les entiers sont créés pour la première fois. Par exemple au lieu de shufflecréer une séquence aléatoire avec random.randint:

from timeit import timeit
import random

a = [random.randint(0, 10**6) for _ in range(10**6)]
for _ in range(5):
    print(timeit(lambda: list(a), number=10))

C'est aussi rapide que de copier votre list(range(10**6))(premier et rapide exemple).

Cependant, lorsque vous mélangez - vos entiers ne sont plus dans l'ordre où ils ont été créés pour la première fois, c'est ce qui le ralentit.

Un rapide intermezzo:

• Tous les objets Python sont sur le tas, donc chaque objet est un pointeur.
• La copie d'une liste est une opération superficielle.
• Cependant, Python utilise le comptage de références, donc lorsqu'un objet est placé dans un nouveau conteneur, le nombre de références doit être incrémenté ( Py_INCREFinlist_slice ), donc Python a vraiment besoin d'aller là où se trouve l'objet. Il ne peut pas simplement copier la référence.

Ainsi, lorsque vous copiez votre liste, vous obtenez chaque élément de cette liste et le mettez «tel quel» dans la nouvelle liste. Lorsque votre prochain élément a été créé peu de temps après celui en cours, il y a de fortes chances (aucune garantie!) Qu'il soit enregistré à côté de celui-ci sur le tas.

Supposons que chaque fois que votre ordinateur charge un élément dans le cache, il charge également les éléments xsuivants en mémoire (localité du cache). Ensuite, votre ordinateur peut effectuer l'incrément de comptage de référence pour les x+1éléments sur le même cache!

Avec la séquence mélangée, il charge toujours les éléments suivants en mémoire, mais ce ne sont pas les suivants dans la liste. Il ne peut donc pas effectuer l'incrément du nombre de références sans rechercher "vraiment" l'élément suivant.

TL; DR: La vitesse réelle dépend de ce qui s'est passé avant la copie: dans quel ordre ces éléments ont-ils été créés et dans quel ordre sont-ils dans la liste.

Vous pouvez le vérifier en regardant le id:

Détail de l'implémentation CPython: il s'agit de l'adresse de l'objet en mémoire.

a = list(range(10**6, 10**6+100))
for item in a:
    print(id(item))

Juste pour montrer un court extrait:

1496489995888
1496489995920  # +32
1496489995952  # +32
1496489995984  # +32
1496489996016  # +32
1496489996048  # +32
1496489996080  # +32
1496489996112
1496489996144
1496489996176
1496489996208
1496489996240
1496507297840
1496507297872
1496507297904
1496507297936
1496507297968
1496507298000
1496507298032
1496507298064
1496507298096
1496507298128
1496507298160
1496507298192

Donc, ces objets sont vraiment "côte à côte sur le tas". Avec shuffleils ne sont pas:

import random
a = list(range(10**6, 100+10**6))
random.shuffle(a)
last = None
for item in a:
    if last is not None:
        print('diff', id(item) - id(last))
    last = item

Ce qui montre que ceux-ci ne sont pas vraiment côte à côte dans la mémoire:

diff 736
diff -64
diff -17291008
diff -128
diff 288
diff -224
diff 17292032
diff -1312
diff 1088
diff -17292384
diff 17291072
diff 608
diff -17290848
diff 17289856
diff 928
diff -672
diff 864
diff -17290816
diff -128
diff -96
diff 17291552
diff -192
diff 96
diff -17291904
diff 17291680
diff -1152
diff 896
diff -17290528
diff 17290816
diff -992
diff 448

Note importante:

Je n'y ai pas pensé moi-même. La plupart des informations se trouvent dans le blog de Ricky Stewart .

Cette réponse est basée sur l'implémentation CPython "officielle" de Python. Les détails dans d'autres implémentations (Jython, PyPy, IronPython, ...) peuvent être différents. Merci @ JörgWMittag pour l'avoir signalé .

Lorsque vous mélangez les éléments de la liste, leur localité de référence est moins bonne, ce qui entraîne de moins bonnes performances du cache.

Vous pourriez penser que la copie de la liste ne fait que copier les références, pas les objets, de sorte que leur emplacement sur le tas ne devrait pas avoir d'importance. Cependant, la copie implique toujours d'accéder à chaque objet afin de modifier le refcount.

Comme expliqué par d' autres, ce n'est pas simplement copier les références , mais augmente également les comptes de référence à l' intérieur des objets et ainsi les objets sont accessibles et le cache joue un rôle.

Ici, je veux juste ajouter plus d'expériences. Pas tellement à propos de shuffled vs unshuffled (où accéder à un élément peut manquer le cache mais obtenir les éléments suivants dans le cache afin qu'ils soient touchés). Mais à propos des éléments répétitifs, où les accès ultérieurs du même élément peuvent atteindre le cache car l'élément est toujours dans le cache.

Test d'une plage normale:

>>> from timeit import timeit
>>> a = range(10**7)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[5.1915339142808925, 5.1436351868889645, 5.18055115701749]

Une liste de la même taille mais avec un seul élément répété encore et encore est plus rapide car elle atteint le cache tout le temps:

>>> a = [0] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.125743135926939, 4.128927210087596, 4.0941229388550795]

Et peu importe de quel numéro il s'agit:

>>> a = [1234567] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.124106479141709, 4.156590225249886, 4.219242600790949]

Fait intéressant, cela devient encore plus rapide lorsque je répète à la place les mêmes deux ou quatre éléments:

>>> a = [0, 1] * (10**7 / 2)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.130586101607932, 3.1001001764957294, 3.1318465707127814]

>>> a = [0, 1, 2, 3] * (10**7 / 4)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.096105435911994, 3.127148431279352, 3.132872673690855]

Je suppose que quelque chose n'aime pas que le même compteur unique augmente tout le temps. Peut-être que certains pipelines se bloquent parce que chaque augmentation doit attendre le résultat de l'augmentation précédente, mais c'est une supposition sauvage.

Quoi qu'il en soit, essayez ceci pour un nombre encore plus grand d'éléments répétés:

from timeit import timeit
for e in range(26):
    n = 2**e
    a = range(n) * (2**25 / n)
    times = [timeit(lambda: list(a), number=20) for _ in range(3)]
    print '%8d ' % n, '  '.join('%.3f' % t for t in times), ' => ', sum(times) / 3

La sortie (la première colonne est le nombre d'éléments différents, pour chaque je teste trois fois puis je prends la moyenne):

       1  2.871  2.828  2.835  =>  2.84446732686
       2  2.144  2.097  2.157  =>  2.13275338734
       4  2.129  2.297  2.247  =>  2.22436720645
       8  2.151  2.174  2.170  =>  2.16477771575
      16  2.164  2.159  2.167  =>  2.16328197911
      32  2.102  2.117  2.154  =>  2.12437970598
      64  2.145  2.133  2.126  =>  2.13462250728
     128  2.135  2.122  2.137  =>  2.13145065221
     256  2.136  2.124  2.140  =>  2.13336283943
     512  2.140  2.188  2.179  =>  2.1688431668
    1024  2.162  2.158  2.167  =>  2.16208440826
    2048  2.207  2.176  2.213  =>  2.19829998424
    4096  2.180  2.196  2.202  =>  2.19291917834
    8192  2.173  2.215  2.188  =>  2.19207065277
   16384  2.258  2.232  2.249  =>  2.24609975704
   32768  2.262  2.251  2.274  =>  2.26239771771
   65536  2.298  2.264  2.246  =>  2.26917420394
  131072  2.285  2.266  2.313  =>  2.28767871168
  262144  2.351  2.333  2.366  =>  2.35030805124
  524288  2.932  2.816  2.834  =>  2.86047313113
 1048576  3.312  3.343  3.326  =>  3.32721167007
 2097152  3.461  3.451  3.547  =>  3.48622758473
 4194304  3.479  3.503  3.547  =>  3.50964316455
 8388608  3.733  3.496  3.532  =>  3.58716466865
16777216  3.583  3.522  3.569  =>  3.55790996695
33554432  3.550  3.556  3.512  =>  3.53952594744

Donc, à partir d'environ 2,8 secondes pour un seul élément (répété), il tombe à environ 2,2 secondes pour 2, 4, 8, 16, ... éléments différents et reste à environ 2,2 secondes jusqu'à la centaine de milliers. Je pense que cela utilise mon cache L2 (4 × 256 Ko, j'ai un i7-6700 ).

Puis en quelques étapes, les temps passent à 3,5 secondes. Je pense que cela utilise un mélange de mon cache L2 et de mon cache L3 (8 Mo) jusqu'à ce qu'il soit également "épuisé".

À la fin, il reste à environ 3,5 secondes, je suppose que mes caches n'aident plus avec les éléments répétés.

Avant le mélange, lorsqu'ils sont alloués dans le tas, les objets d'index adjacents sont adjacents en mémoire, et le taux de réussite de la mémoire est élevé lors de l'accès; après la lecture aléatoire, l'objet de l'index adjacent de la nouvelle liste n'est pas en mémoire. Adjacent, le taux de réussite est très faible.