python contare - Perché copiare una lista mescolata è molto più lenta?




come sommare (5)

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

È veloce come copiare l' list(range(10**6)) (primo e veloce esempio).

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

Un intermezzo veloce:

  • Tutti gli oggetti Python sono nell'heap, quindi ogni oggetto è un puntatore.
  • Copiare una lista è un'operazione superficiale.
  • Comunque Python usa il conteggio dei riferimenti così quando un oggetto viene messo in un nuovo contenitore il suo conteggio di riferimento deve essere incrementato ( Py_INCREF in list_slice ), quindi Python ha davvero bisogno di 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 lo metti "così com'è" nella nuova lista. Quando il tuo prossimo oggetto è stato creato poco dopo quello attuale, c'è una buona probabilità (nessuna garanzia!) Di essere salvato accanto ad esso sullo heap.

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

Con la sequenza mescolata, carica ancora gli elementi della memoria successiva, ma questi non sono quelli nella lista successiva. Quindi non può eseguire l'incremento del conteggio di riferimento senza "veramente" cercare l'elemento successivo.

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

Puoi verificarlo guardando l' id :

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

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

Solo 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 sull'heap". Con shuffle non lo 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 nella 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 l'ho pensato da solo. La maggior parte delle informazioni può essere trovata nel blogpost di Ricky Stewart .

Questa risposta è basata sull'implementazione CPython "ufficiale" di Python. I dettagli in altre implementazioni (Jython, PyPy, IronPython, ...) potrebbero essere diversi. Grazie a JörgWMittag per averlo indicato .

La copia di un range(10**6) riproduzione casuale range(10**6) richiede dieci volte circa 0,18 secondi: (sono cinque corse)

0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451

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

0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184

Ecco il mio codice di prova:

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 capisco la differenza di velocità nel famoso Perché è più veloce elaborare una matrice ordinata rispetto ad una matrice non ordinata? esempio, ma qui la mia elaborazione non ha decisioni. Sta solo copiando alla cieca i riferimenti all'interno della lista, no?

Sto usando Python 2.7.12 su Windows 10.

Modifica: provato Python 3.5.2 ora, i risultati erano quasi gli stessi (mescolati in modo costante intorno a 0,17 secondi, non mescolati 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))

Quando si mischiano gli elementi dell'elenco, hanno una località di riferimento peggiore, con conseguente peggioramento delle prestazioni della cache.

Si potrebbe pensare che copiare l'elenco copia solo i riferimenti, non gli oggetti, quindi le loro posizioni sull'heap non dovrebbero avere importanza. Tuttavia, la copia implica ancora l'accesso a ciascun oggetto per modificare il conto.


Prima dello shuffle, quando allocati nell'heap, gli oggetti indice adiacenti sono adiacenti in memoria e il tasso di hit della memoria è alto quando si accede; dopo shuffle, l'oggetto dell'indice adiacente del nuovo elenco non è in memoria. Adiacente, il tasso di successo è molto scarso.


Come spiegato da altri, non si limitano a copiare i riferimenti, ma si aumentano anche i conteggi di riferimento all'interno degli oggetti e quindi si accede agli oggetti e la cache svolge un ruolo.

Qui voglio solo aggiungere altri esperimenti. Non tanto per mischiare contro non shuffled (dove l'accesso a un elemento potrebbe perdere la cache ma ottenere i seguenti elementi nella cache in modo che vengano colpiti). Ma riguardo agli elementi ripetuti, dove gli 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ù e più volte è più veloce perché colpisce sempre 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 quale 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 invece 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 di continuo. Forse alcuni stalli della pipeline perché ogni aumento deve attendere il risultato del precedente aumento, ma questa è una supposizione 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 ciascun test tre volte e poi 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 elemento singolo (ripetuto) scende a circa 2,2 secondi per 2, 4, 8, 16, ... elementi diversi e rimane a circa 2,2 secondi fino a centinaia di migliaia. Penso che questo usi la mia cache L2 (4 × 256 KB, ho un i7-6700 ).

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

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


Se si desidera unire i due elenchi in forma ordinata, è possibile utilizzare la funzione di unione dalla libreria heapq.

from heapq import merge

a = [1,2,4]
b = [2,4,6,7]

print list(merge(a,b))




python python-internals