una - sommare elementi lista python



Perché la copia di un elenco casuale è molto più lenta? (3)

Come spiegato da altri, non si tratta solo di copiare i riferimenti, ma aumenta anche il conteggio dei riferimenti all'interno degli oggetti e quindi gli oggetti sono accessibili e la cache gioca un ruolo.

Qui voglio solo aggiungere altri esperimenti. Non tanto per quanto riguarda il riordino o il non mescolato (in cui l'accesso a un elemento potrebbe perdere la cache ma ottenere i seguenti elementi nella cache in modo che vengano colpiti). Ma riguardo alla ripetizione di elementi, in cui accessi successivi dello stesso elemento potrebbero colpire la cache perché l'elemento è ancora nella cache.

Test di un intervallo 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]

Un elenco delle stesse dimensioni ma con un solo elemento ripetuto più volte è più veloce perché colpisce continuamente la cache:

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

E non sembra importare che numero sia:

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

È interessante notare che diventa ancora più veloce quando ripeto gli stessi due o quattro elementi:

>>> 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]

Immagino che a qualcosa non piaccia lo stesso contatore singolo aumentato continuamente. Forse un po 'di stallo della pipeline perché ogni aumento deve attendere il risultato dell'aumento precedente, ma questa è un'ipotesi selvaggia.

Ad ogni modo, provando questo per un numero ancora maggiore di elementi ripetuti:

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

L'output (la prima colonna è il numero di elementi diversi, per ogni test tre volte e poi prendo la media):

       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

Quindi da circa 2,8 secondi per un singolo elemento (ripetuto) scende a circa 2,2 secondi per 2, 4, 8, 16, ... elementi diversi e rimane a circa 2,2 secondi fino alle centinaia di migliaia. Penso che questo usi la mia cache L2 (4 × 256 KB, ho un i7-6700 ).

Quindi, in pochi passaggi, i tempi aumentano fino a 3,5 secondi. Penso che questo usi un mix della mia cache L2 e della mia cache L3 (8 MB) fino a quando non è "esaurito".

Alla fine rimane circa 3,5 secondi, suppongo perché le mie cache non aiutano più con gli elementi ripetuti.

https://code.i-harness.com

Copiare un elenco di un range(10**6) mischiato range(10**6) dieci volte mi richiede circa 0,18 secondi: (queste sono cinque esecuzioni)

0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451

Copiare l'elenco non mischiato dieci volte mi richiede circa 0,05 secondi:

0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184

Ecco il mio codice di 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)

Ho anche provato a copiare con a[:] , i risultati erano simili (cioè, grande differenza di velocità)

Perché la grande differenza di velocità? Conosco e comprendo la differenza di velocità nel famoso Perché è più veloce elaborare un array ordinato rispetto a un array non ordinato? esempio, ma qui la mia elaborazione non ha decisioni. Sta solo copiando ciecamente i riferimenti all'interno dell'elenco, no?

Sto usando Python 2.7.12 su Windows 10.

Modifica: ho provato anche Python 3.5.2 ora, i risultati erano quasi gli stessi (mischiato costantemente intorno a 0,17 secondi, non mischiato costantemente intorno a 0,05 secondi). Ecco il codice per questo:

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

Il bit interessante è che dipende dall'ordine in cui gli interi vengono creati per la prima volta. Ad esempio, invece di shuffle crea una sequenza casuale con 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))

Questo è veloce come copiare la tua list(range(10**6)) (primo e veloce esempio).

Tuttavia, quando mescoli - quindi i tuoi numeri interi non sono più nell'ordine in cui sono stati creati per la prima volta, questo è ciò che lo rende lento.

Un veloce intermezzo:

  • Tutti gli oggetti Python sono nell'heap, quindi ogni oggetto è un puntatore.
  • La copia di un elenco è un'operazione superficiale.
  • Tuttavia Python utilizza il conteggio dei riferimenti, quindi quando un oggetto viene inserito in un nuovo contenitore, il conteggio dei riferimenti deve essere incrementato ( Py_INCREF in list_slice ), quindi Python deve davvero andare dove si trova l'oggetto. Non può semplicemente copiare il riferimento.

Quindi quando copi la tua lista ottieni ogni elemento di quella lista e la metti "così com'è" nella nuova lista. Quando il tuo prossimo oggetto è stato creato poco dopo quello attuale, c'è una buona possibilità (nessuna garanzia!) Che venga salvato accanto ad esso nell'heap.

Supponiamo che ogni volta che il tuo computer carica un elemento nella cache carica anche gli elementi x next-in-memory (località cache). Quindi il tuo computer può eseguire l'incremento del conteggio dei riferimenti per x+1 elementi nella stessa cache!

Con la sequenza mescolata carica ancora gli elementi successivi in ​​memoria, ma questi non sono quelli successivi nella lista. Quindi non può eseguire l'incremento del conteggio dei riferimenti senza "davvero" cercare l'elemento successivo.

TL; DR: la velocità effettiva dipende da ciò che è accaduto prima della copia: in quale ordine sono stati creati questi elementi e in quale ordine sono questi nell'elenco.

Puoi verificarlo guardando l' id :

Dettagli dell'implementazione di CPython: questo è l'indirizzo dell'oggetto in memoria.

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

Giusto per mostrare un breve estratto:

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

Quindi questi oggetti sono davvero "uno accanto all'altro sul mucchio". Con shuffle non sono:

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

Il che dimostra che questi non sono realmente uno accanto all'altro in memoria:

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

Nota importante:

Non ho pensato a me stesso. La maggior parte delle informazioni sono reperibili nel post di Ricky Stewart .

Questa risposta si basa sull'implementazione "ufficiale" di CPython di Python. I dettagli in altre implementazioni (Jython, PyPy, IronPython, ...) potrebbero essere diversi. Grazie @ JörgWMittag per averlo segnalato .


Quando si mescolano gli elementi dell'elenco, questi hanno una località di riferimento peggiore, con conseguenti peggiori prestazioni della cache.

Potresti pensare che la copia dell'elenco copi solo i riferimenti, non gli oggetti, quindi le loro posizioni nell'heap non dovrebbero importare. Tuttavia, la copia implica comunque l'accesso a ciascun oggetto al fine di modificare il refcount.





python-internals